Задача о коммивояжере (перебор вариантов)
   Постановка задачи. Классическая формулировка задачи известна уже более 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 чисел утомительное занятие и разумная лень - "двигатель прогресса".

Закрыть