Дерево решений теперь может быть изображено так, как это показано на рис. 1.10.

Рисунок 1.10 - Редуцированная матрица расстояний на 2 - м шаге алгоритма

Рисунок 1.11 - Дерево решений на 2-м шаге алгоритма

По редуцированной матрице расстояний далее определяем минимальные ненулевые значения ее строк и столбцов, которые записываем соответственно в виде вектора - столбца и вектора - строки . Матрица вместе с этими векторами показана на рис. 1.12.

Рисунок 1.12 - Редуцированная матрица и значения минимальных ненулевых элементов для 2-го шага алгоритма

Соответствующие элементам векторов и значения вторичных штрафов для различных звеньев или пар вершин с нулевыми значениями расстояний между ними приведены в табл. 1.2.

Таблица 1.2 - Вторичные штрафы на 2 - м шаге алгоритма

Как видно из табл. 1.2, максимальное значение равно . Выбирая звено , можно получить выигрыш в расстоянии, равный , т, е. больший, чем при выборе любого другого звена, за исключением звена, , . Следовательно, в качестве базового звена на 2 - м шаге ветвления выбирается звено, а , Нижней границей длин маршрутов из подмножества на следующем (3 - м шаге) является величина =.

Модифицированная матрица расстояний после вычеркивания 1 -й строки и 2 -го столбца имеет вид, приведенный на рис. 1.13.

Рисунок 1.13 - Текущая матрица расстояний для 3-го шага алгоритма

3 - й шаг. Выполняем сначала редукцию строк текущей матрицы расстояний. Для этого в каждой строке определяем минимальный элемент и найденное значение вычитаем из элементов соответствующей строки. Результаты выполнения редукции строк в виде матрицы приведены на рис. 1.14, где дополнительный вектор - столбец содержит вычитаемые при редукции константы.

Рисунок 1.14 - Редуцированная по строкам матрица расстояний на 3 - м шаге алгоритма

Затем выполняем редукцию столбцов, результаты которой в виде матрицы приведены на рис. 1.15, где дополнительный вектор - строка содержит вычитаемые при редукции константы. Значение элемента, расположенного на пересечении вектора - столбца и вектора - строки , равно сумме всех вычитаемых констант: = 2. Это значение позволяет определить новую нижнюю границу длин всех маршрутов на данном шаге: = 300.

Дерево решений теперь может быть изображено так, как это показано на рис. 1.16.

Рисунок 1.15 - Редуцированная матрица расстояний на 3 - м шаге алгоритма

Рисунок 1.16 - Дерево решений на 3 - м шаге алгоритма

По редуцированной матрице расстояний далее определяем минимальные ненулевые значения ее строк и столбцов, которые записываем соответственно в виде вектора - столбца и вектора - строки . Матрица вместе с этими векторами показана на рис. 1.17.

Рисунок 1.17 - Редуцированная матрица и значения минимальных ненулевых элементов для 3-го шага алгоритма

Соответствующие элементам векторов и значения вторичных штрафов для различных звеньев или пар вершин с нулевыми значениями расстояний между ними приведены в табл. 1.3.