Структура такой сети представлена на рис. 1.2.

Рисунок 1.2 - Структура КСД

Выберем 5 городов, из нашей матрицы и составим для нее матрицу расстояний, перенумеровав города снова.

1. Кировоград

2. Новомиргород

3. Знаменка

4. Каменка

5. Чигирин

Рисунок 1.3 - Матрица расстояний графа

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

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

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

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

Рисунок 1.6 - Начальный узел дерева решений

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

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

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

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

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

Следовательно, модифицированная матрица расстояний после вычеркивания 4 -й строки и 5 -го столбца, а также замены элемента на пересечении 5 -й строки и 4 -го столбца матрицы на имеет вид, приведенный на рис. 1.8.

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

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

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

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