Задача о коммивояжере (перебор вариантов)

Постановка задачи. Классическая формулировка задачи известна уже более 200 лет : имеются n городов, расстояния между которыми заданы ; коммивояжеру необходимо выйти из какого-то города, посетить остальные n-1 городов точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).

Задача коммивояжера принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.

Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном классическом методе.

Структуры данных.

Const Мах-100;

Var A:array[l..Max,l..Max] of integer;{Матрица расстояний между городами}

B:array[l..Max,l..Max] of byte; {Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А }

Way, BestWay:array[1... Max] of byte; {Хранится текущее решение и лучшее решение}

Nnew:array[l..Max] of boolean;{Значение элемента массива false говорит о том, что в соответствующем городе коммивояжер уже побывал}

BestCostinteger; {Стоимость лучшего решения}

Идея решения. Пусть мы находимся в городе с номером v. Наши действия.

Шаг1. Если расстояние (стоимость), пройденное коммивояжером до города с номером v, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора.

Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего из ранее найденных. Если результат сравнения положительный, то значения BestCost и Вest Way следует изменить и выйти из этой ветви дерева перебора.

Шаг 3. Пометить город с номером v как рассмотренный, записать этот номер по значению Count в массив Way .

Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost, иначе на следующий шаг.

Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.

Пример. Ниже приведены матрицы А и В (после сортировки элементов каждой строки матрицы А).

Примечание.

Можно использовать любой из методов сортировки, но авторы предпочитают использовать метод Хоара[1] из-за определенного изящества в его реализации. Рекурсивная логика плюс смена направления изменения индекса в одной циклической конструкции.

Примечание. Символом @ обозначено бесконечное расстояние.

Прежде чем перейти к обсуждению логики, целесообразно разобрать этот перебор на примере. На рисунке приведен пример и порядок просмотра городов. В кружках указаны номера городов, рядом с кружками - суммарная стоимость проезда до этого города из первого.

Итак, запись логики.

procedure Solve(v,Count:byte;Cost:integer);

{v - номер текущего города; Count - счетчик числа пройденных городов; Cost - стоимость текущего решения}

var i: integer;

begin

if Cost>BestCost then exit; {Стоимость текущего решения превышает стоимость лучшего из ранее полученных }

if Count=N then begin Cost:=Cost+A[v,l];Way[N]:=v;{Последний город пути. Доформировываем решение и сравниваем его с лучшим из ранее полученных.}

if CosKBestCost then begin .

BestCost:=Cost;BestWay:=Way;

end;

exit;

end;

Nnew[v]:=false;

Way [Count] :=v; {Город с номером v пройден, записываем его номер в путь коммивояжер}

for i:=l to N do if Nnew[B[v,i]] then

Solve(B[v,i], Count+l,Cost+A[v,B[v,i]]); {Поиск города, в который коммивояжер может пойти из города с номером v}

Nnew[v]:=true; {Возвращаем город с номером v в число непройденных}

end;

Первый вызов - Solve (1,1,0).

Разработка по данному "шаблону" работоспособной программы - техническая работа. Если Вы решитесь на это, то есть смысл проверить ее работоспособность на следующем примере (матрица А приведена ниже). Решение имеет вид 189251067431, его стоимость 158.

Оцените время работы программы. Если у Вас мощный компьютер, то создайте матрицу А[1..50,1..50] и попытайтесь найти наилучшее решение с помощью разобранного метода. Заметим, что набор 2500 чисел утомительное занятие и разумная лень - "двигатель прогресса".