Математическая логика и теория алгоритмов. Стенюшкина В.А. - 82 стр.

буется составить замкнутый маршрут, соединяющий все пункты и проходящий
через каждый пункт ровно один раз. Дополнительное условие: сумма характе-
ристик дуг маршрута (суммарная стоимость проезда) – минимальна. Решение
задачи для небольших n может быть проведено следующим образом. Строим
последовательно перестановки из номеров пунктов и для допустимых переста-
новок запоминаем лучшие суммы. Таким образом, для n пунктов просматривае-
тся (n - 1)! маршрутов. При n = 5, (n - 1)! = 24. Для больших n (но не очень –
факториал быстро растет) применяется метод ветвей и границ.

                                                           ∞ 18 28 22 24
                                                           4 ∞ 12 ∞ 29
                                                           22 19 ∞ 8 9
        1      2      3      4      5                   A=
                                                           7 ∞ 18 ∞ 9
                                                             29 16 10 10          ∞

                                         Рисунок 4.4

         Приведем алгоритм ветвей, дающий все допустимые маршруты коммиво-
яжера.
         Пусть S – цепочка элементов. Полагаем S = ( ), i = 1.
         Шаг 1 Выбор базы. В матрице А выбираем элемент ai j ≠ ∞ (можно с ме-
ньшим j), если существует. (Если такого элемента нет, продвижение в этом на-
правлении невозможно).
         Шаг 2 Ветвление. По матрице А строим матрицы А1, А2.
         Построение А1 Полагаем S = S + ai j. Берем матрицу А, полагаем элементы
i – строки, j – столбца равными ∞. Сам элемент ai j не меняем. Предотвращаем
циклы, полагая a j i = ∞ (в общем случае для цепочки (ai j , a j к , a lm) полагаем a m i
= ∞).
         Построение А2 Полагаем ai j в матрице А (остальные элементы – без из-
менения). С каждой из матриц А1, А2 и соответствующими цепочками идем на
выполнение шага 1. При этом поиск базы производим в общем случае цепочки
(ai j , a j к , a lm) в m – строке.
         Шаги 1, 2 выполняются до достижения длины n цепочки (есть маршрут)
или цепочка имеет меньшую длину, но очередной выбор базы невозможен (ма-
ршрута с таким подмаршрутом нет). По достижении длины n – 1 вместо предо-
твращения надо провести проверку: если ami ≠ ∞, то присоединяя ami к цепочке,
получаем маршрут, если ami = ∞, маршрута с подмаршрутом, соответствующим
имеющейся цепочке, нет. Конец алгоритма.
         Для выбора маршрута с наименьшей стоимостью надо каждой цепочке
ставить в соответствие ее суммарную стоимость. С момента построения какого-
либо допустимого маршрута коммивояжера надо удерживать лишь маршруты с