G0 =? Hi +? Hj=241 +591 +274 +606 +551 +151 +188=2602
Виберемо пари міст - претендентів на розгалуження, тобто (I, j), для яких Сij=0: С16, С24, С25, С36, С42, ??С53, С61.
Для виділених претендентів підрахуємо оцінки за формулою:
P (ij)=minCij + minCji
Р16=102 Р36=87 +187=274 Р42=49 +285=334 Р24=292 Р25=49 Р61=126 +87=213 Р53=283 +61=344 max
Для розгалуження виберемо пару претендентів з максимальною оцінкою P (ij), тобто пару Р53.
Зробимо розгалуження й обчислимо оцінку G2:
G21=G0 + P53=2602 + 344=2946
Побудуємо следующею матрицю, для цього викреслимо в першому матриці п'яту сходинку і третій стовпець і виконаємо процес приведення. Щоб уникнути утворення замкнутих підциклів, заборонимо проїзд з міста 3 в місто 5.
12456Hi1Х493962409002123Х001870387387689Х0046100Х496340605831052529Х0Hj00000
Визначаємо оцінку для G1:
G11=G0 +? Hi +? Hj=2602
Так як G11 < G12, то на наступному кроці розбиваємо G1.
Вибираємо пари міст - претендентів на розгалуження:
С16, С24, С25, С36, С42, ??С61.
Р42=49 + 387=436 Р16=409 Р36=87
Р61=529 + 87=616 Р25=49 Р24=689 max
Максимальну оцінку має пара Р24.
Зробимо розгалуження й обчислимо оцінку G1.2:
G22=G12 + P24=2602 + 689=3291
Побудуємо следующею матрицю, для цього викреслимо в попередній матриці другу сходинку і четвертий стовпець і виконаємо процес приведення. Щоб уникнути утворення замкнутих підциклів, заборонимо проїзд з міста 4 в місто 2.
1256Hi12561Х493409001Х4934090387387Х00387387Х04610Х49634494561Х058560583529Х060583529ХHj038700
1256Hi1Х106409003870Х004561Х05854960196529Х0Hj038700
Визначаємо оцінку для G1.1:
G2.1=G1 +? Hi +? Hj=2602 + 49 + 387=3038
Так як G2.1 < G2.2, то на наступному кроці розбиваємо G1.1.
Вибираємо пари міст - претендентів на розгалуження:
С16, С36, С32, С45, С61.
Р45=561 + 409=970 max Р16=106
Р61=196 + 87=283 Р36=0 Р32=106
Максимальну оцінку має пара Р45.
Зробимо розгалуження й обчислимо оцінку G1.1.2:
G3.2=G2.1 + P45=3038 + 970=4008
Побудуємо наступну матрицю, для цього викреслимо в попередній матриці четверту сходинку і п'ятий стовпець і виконаємо процес приведення. Щоб уникнути утворення замкнутих підциклів, заборонимо проїзд з міста 3 в місто 2.
126Hi1261Х106001Х1060387Х00387Х060196Х060196ХHj01060126Hi1Х000387Х006090Х0Hj01060
Визначаємо оцінку для G3.1:
G3.1=G2.1 +? Hi +? Hj=3038 + 106=3144
Так як G3.1 < G3.2, то на наступному кроці...
