Итерация 5. Осуществим приведение матрицы по строкам и столбцам:
2
3
hi
5
0
да
0
6 да 21 21
hi = 21
Константа приведения матрицы h = 21+ 0 = 21, поэтому оценка концевой вершины по правой ветви будет равна 92 (рис. 3.9).
На каждой итерации осуществляется ветвление концевой вершины с наименьшей оценкой (так как определяется маршрут с наименьшей стоимостью). Среди концевых вершин (см. рис. 3.9) наименьшую оценку имеет вершина по левой ветке с оценкой 80: min {80; 83; 96; 115; 92} = 80, поэтому на следующей итерации следует ветвить именно эту вершину. Для этого вернемся к матрице, «породившей» ветвление на подмножества, содержащие дугу (1;6) и не содержащие эту дугу, и повторим все рассуждения. Матрица, «породившая» это ветвление, есть матрица размерности 6*6. Следует брать неприведенную матрицу и запретить в ней движение по дуге (1;6).
