Для виділених претендентів підрахуємо оцінки за формулою:
P (ij)=minCij + minCji
Р23=0 Р25=49 Р61=65 Р52=0 Р24=7 Р42=49 Р51=0 Р13=368 max
Для розгалуження виберемо пару претендентів з максимальною оцінкою P (ij), тобто пару Р13.
Зробимо розгалуження й обчислимо оцінку G8.2:
G8.2=G7.1 + P13=2989 + 368=3357
Побудуємо следующею матрицю, для цього викреслимо в першому матриці перший рядок і третій стовпець і виконаємо процес приведення. Щоб уникнути утворення замкнутих підциклів, заборонимо проїзд з міста 6 в місто 1.
1245Hi12452123Х0002123Х0046100Х49046100Х495007Х05007Х6Х58310525295296Х545230
Визначимо оцінку G8.1, обчисливши суму призводять констант:
G8.1=С7.1 +? Hi +? Hj=2989 +529=3518
Так як G8.1> G8.2, то на наступному кроці розбиваємо G8.2.
Виберемо пари міст - претендентів на розгалуження, тобто (I, j), для яких Сij=0: С25, С24, С42, ??С52, С61, С65.
Для виділених претендентів підрахуємо оцінки за формулою:
P (ij)=minCij + minCji
Р25=0 Р52=0 Р24=7
Р42=49 Р51=123 max Р65=54
Для розгалуження виберемо пару претендентів з максимальною оцінкою P (ij), тобто пару Р51.
Зробимо розгалуження й обчислимо оцінку G9.2:
G9.2=G8.2 + P51=3357 + 123=3480
245Нi2Х00040Х490654523Х542452Х0040Х4960469Х
Визначимо оцінку G9.1, обчисливши суму призводять констант:
G9.1=С8.1 +? Hi +? Hj=3357 + 54=3411
Так як G9.1 < G9.2, то на наступному кроці розбиваємо G9.1.
Виберемо пари міст - претендентів на розгалуження, тобто (I, j), для яких Сij=0: С25, С24, С42, ??С62.
Для виділених претендентів підрахуємо оцінки за формулою:
P (ij)=minCij + minCji
Р25=49 Р24=469 max
Р42=49 Р62=469
Для розгалуження виберемо пару претендентів з максимальною оцінкою P (ij), тобто пару Р24.
Зробимо розгалуження й обчислимо оцінку G10.2:
G10.2=G9.1 + P24=3411 + 469=3880
25Нi4Х494960Х0
254Х060Х Визначимо оцінку G10.1, обчисливши суму призводять констант:
G10.1=С9.1 +? Hi +? Hj=3411 + 49=3460
Так як G10.1 < G10.2, то на наступному кроці розбиваємо G10.1.
Зробимо розгалуження й обчислимо оцінку G11.1 і G12.1.:
11.1=3675 G12.1=3675
В результаті отримуємо цикл t2={53, 36, 13, 51, 24, 45, 62} довжина якого дорівнює 3621. Послідовність об'їзду міст можна представити таким чином 3 ® 6 ® 2 ® 4 ® 5 ® 1 ® 3.
Рис.1 дерево рішень
2. Вибір економічно доцільного способу поїздки комівояжера
.1 Порівняння технік...
