Задача коммивояжера

   Рассмотрим  такую задачу. Коммивояжер (агент  по сбыту), отправляясь из своего населенного  пункта, должен кратчайшим маршрутом  ровно по одному разу посетить n-1 других населенных пунктов и вернуться назад. Это оптимизационная задача, и её различные модификации возникают не только при доставке товаров на дом, но и в ситуациях иного характера. Математические модели задачи коммивояжера содержат большое количество переменных и ограничений. Поэтому для их решения общие методы линейного программирования обычно не используются. Для небольших значений n мы попробуем справиться с задачей коммивояжера, используя рекурсию и метод перебора с возвратом.

адача 7. Один маршрут  коммивояжера. Пусть имеется n пунктов, пронумерованных числами 0,1,…,n-1, и задана матрица U = (U_i,j) (i,j = 0,1,…,n-1), где U_i,j - расстояние между i и j. Написать рекурсивную программу-функцию нахождения одного решения задачи коммивояжера методом перебора с возвратом, если вояж начинается из пункта с номером kÎ{0,1,…,n}.

   Решение. Пусть матрица расстояний U определена вне программы, то есть искомые функции могут рассматривать её как глобальный параметр. Числа U_i,j и U_j,i, вообще говоря, не обязательно должны совпадать. При отсутствии дороги между пунктами i и j будем считать, что она есть, но бесконечной длины: U_i,j=¥.

   Решением  задачи могут служить пара функций  commi(n, ne, po, ot, j) и macom(n, k):

   Головная  функция macom(n, k) по заданному количеству пунктов n и номеру пункта отправления k подготавливает фактические аргументы для рекурсивной функции commi():

   Параметры функции commi(n, ne, po, ot, j) имеют следующий смысл:

Рис. 6. Опорная схема для описания рекурсии в задаче коммивояжера

   Остановимся подробнее на алгоритме, реализуемом  функцией commi(), и динамике формирования текущего маршрута ne. Прежде всего отметим, что рекурсия организована по j - порядковому номеру (от нуля и далее) подключаемого к маршруту пункта (см. рис.6). Пусть мы находимся в j-м рекурсивном вызове, то есть уже сформирован путь k®ne₀®...®ne_j-1. В каждом вызове глубины j делается попытка нарастить текущий путь за счет i-го пункта (i, j = 0, 1, …, n-1), а сам вызов соответствует переходу от работы с текущим пунктом к работе со следующим пунктом. При этом в начале вычислений и при переходах к любому последующему рекурсивному вызову параметр i меняется от нуля и далее с шагом, равным единице, пытаясь принять значение наименьшего номера пункта, допустимого для наращивания пути. При переходах к любому предыдущему рекурсивному вызову параметр i продолжает изменяться от своего текущего на данном уровне значения с шагом, равным единице, также пытаясь принять значение наименьшего номера пункта, допустимого для наращивания пути. Если в текущем рекурсивном вызове путь нарастить уже нельзя, то создавшуюся ситуацию (отрезок сформированного пути) назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему пункту и продолжению работы с ним. Иных случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии мы должны считать совокупность всех тупиков. Заметим, что в данном случае элементы базы заранее, до вычислений, неизвестны.

   После наращивания пути в последнем  рекурсивном вызове (j = n-1) завершается формирование одного из возможных маршрутов. Для него с помощью матрицы расстояний подсчитывается длина пути. Если она оказывается меньше длины ранее запомненного маршрута (ot_n+1>ne_n+1), то в векторе ot запоминается последний маршрут и его длина (ot¬ne). Затем вычисления продолжаются в текущем рекурсивном вызове и т.д., пока мы не попадаем в тупик при работе с начальным пунктом k. Здесь вычисления прекращаются и решение задачи возвращается в виде вектора ot, у которого первые n+1 компонентов задают маршрут, а последний компонент - его длину.

   Контрольный пример. Пусть рассматривается матрица расстояний U, приведенная перед функцией commi(). Найти одно из решений задачи коммивояжера для начального пункта 0 можно так:

macom(U,0)^T = [0 2 1 4 3 6 5 0 30].

   Первые  восемь компонентов полученного  вектора определяют маршрут коммивояжера: 0®2®1®4®3®6®5®0, а последняя компонента равна длине этого маршрута.

   Замечание. Некоторого улучшения быстродействия можно добиться незначительной модификацией функции commi(), если одновременно с наращиванием пути подсчитывать и его текущую длину. Именно так и устроены функции commi1() и macom1():

адача 8. Все маршруты коммивояжера. Пусть имеется n пунктов, пронумерованных числами  
0,1,…,n-1, и задана матрица U = (U_i,j) (i,j = 0,1,…,n-1), где U_i,j - расстояние между i и j. Написать рекурсивную программу-функцию нахождения всех возможных решений задачи коммивояжера методом перебора с возвратом, если вояж начинается из пункта с номером kÎ{0,1,…,n}.

   Решение. Функции commi2() и macom2() решают поставленную задачу. Их отличие от функций commi1() и macom1() состоит в следующем. Параметр ot здесь не вектор, а построчно наращиваемая матрица. К первому найденному маршруту (нулевая строка ot) в виде последующих строк подсоединяются все другие маршруты с той же самой длиной пути. Если найден маршрут с более коротким путем, то матрица ot начинает формироваться заново. Рекурсия в commi2() и commi1() устроена совершенно одинаково.

   Контрольный пример. Пусть рассматривается матрица расстояний U, приведенная перед функцией commi(). Найти все решения задачи коммивояжера для начального пункта 0 можно так:

   Каждое  из пяти решений занимает в полученной матрице одну строку, в которой  первые восемь элементов - это маршрут, а последний элемент - его длина