Реферат Єдина транспортна система і географія транспорту

Тема: Новые рефераты

розбиваємо G3.1.

Вибираємо пари міст - претендентів на розгалуження:

С16, С36, С12, С61.

Р61=87 + 90=177 max Р12=90

Р36=87 Р16=0

Максимальну оцінку має пара Р61.

Зробимо розгалуження й обчислимо оцінку G4.2:

G4.2=G3.1 + P61=3144 + 177=3321

Побудуємо следующею матрицю, для цього викреслимо в попередній матриці шосту сходинку і перший стовпець і виконаємо процес приведення. Щоб уникнути утворення замкнутих підциклів, заборонимо проїзд з міста 1 в місто 6.

26Hi10Х03Х00Hj00

Визначаємо оцінку для G4.1:

G4.1=G3.1 +? Hi +? Hj=3144

Так як G4.1 < G4.2, то на наступному кроці розбиваємо G4.1.

Вибираємо пари міст - претендентів на розгалуження:

С12, С36.

Р12=0 Р36=0

Зробимо розгалуження й обчислимо оцінку G5.1 і G6.1.:

51=3144 G6.1=3144

В результаті отримуємо цикл t1={53, 24, 45, 61, 12, 36} довжина якого дорівнює 3144. Послідовність об'їзду міст можна представити таким чином 5 ® 3 ® 6 ® 1 ® 2 ® 4 ® 5.

Підмножина G12=2946 < G6.1=3144 може призвести до утворення циклу з меншою оцінкою, тому воно має бути піддано аналізу. Для аналізу необхідно відновити вихідну матрицю, заборонити переїзд з міста 5 в місто 3 та виконати аналогічні кроки розрахунків.

123456Hi1Х493102962409002123Х61001870387387Х6981510046100393Х4963405285285Х292Х283283605831261052529Х01234561Х49310296240902123Х6100187387387Х698151046100393Х49634522Х9Х0605831261052529ХHj0061000

123456Hi1Х49341962409002123Х0001870387387Х6981510046100332Х496340522Х9Х028360583651052529Х0Hj0061000

Визначаємо оцінку для G2:

G12=G0 +? Hi +? Hj=2946

На наступному кроці розбиваємо G2.

Вибираємо пари міст - претендентів на розгалуження:

С16, С24, С25, С36, С42, ??С61, С23, С56.

Р42=51 Р16=41 Р36=87 max Р23=41

Р61=67 Р25=49 Р24=9 Р56=2

Максимальну оцінку має пара Р36.

Зробимо розгалуження й обчислимо оцінку G2.2:

G7.2=G12 + P36=2946 + 87=3033

Побудуємо следующею матрицю, для цього викреслимо в попередній матриці третю сходинку і шостий стовпець і виконаємо процес приведення.