2.1.7. Задача о коммивояжере (перебор вариантов)
Постановка задачи. Классическая формулировка задачи известна уже более 200 лет : имеются n городов, расстояния между которыми заданы ; коммивояжеру необходимо выйти из какого-то города, посетить остальные n-1 городов точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).
Задача коммивояжера принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.
Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном классическом методе.
Структуры данных.
Const Max=100;
Var A:array[1..Max,1..Max] of integer;{Матрица расстояний между городами}
B:array[1..Max,1..Max] of byte;{Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А }
Way, BestWay:array[1..Max] of byte;{Хранится текущее решение и лучшее решение}
Nnew:array[1..Max] of boolean;{Значение элемента массива false говорит о том, что в соответствующем городе коммивояжер уже побывал}
BestCost:integer;{Стоимость лучшего решения}
Идея решения. Пусть мы находимся в городе с номером v. Наши действия.
Шаг 1. Если расстояние (стоимость), пройденное коммивояжером до города с номером v, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора.
Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего из ранее найденных. Если результат сравнения положительный, то значения BestCost и BestWay следует изменить и выйти из этой ветви дерева перебора .
Шаг 3. Пометить город с номером v как рассмотренный, записать этот номер по значению Count в массив Way .
Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost, иначе на следующий шаг.
Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.
Пример. Ниже приведены матрицы А и В (после сортировки элементов каждой строки матрицы А).
Примечание. Можно использовать любой из методов сортировки, но авторы предпочитают использовать метод Хоара[1] из-за определенного изящества в его реализации. Рекурсивная логика плюс смена направления изменения индекса в одной циклической конструкции.
A B
@ |
27 |
43 |
16 |
30 |
26 |
|||||
7 |
@ |
16 |
1 |
30 |
25 |
|||||
20 |
13 |
@ |
35 |
5 |
0 |
|||||
21 |
16 |
25 |
@ |
18 |
18 |
|||||
12 |
46 |
27 |
48 |
@ |
5 |
|||||
23 |
5 |
5 |
9 |
5 |
@ |
|||||
4 |
6 |
2 |
5 |
3 |
1 |
|||||
4 |
1 |
3 |
6 |
5 |
2 |
|||||
6 |
5 |
2 |
1 |
4 |
3 |
|||||
2 |
5 |
6 |
1 |
3 |
4 |
|||||
6 |
1 |
3 |
2 |
4 |
5 |
|||||
2 |
3 |
5 |
4 |
1 |
6 |
|||||
Примечание. Символом @ обозначено бесконечное расстояние.
Прежде чем перейти к обсуждению логики, целесообразно разобрать этот перебор на примере. На рисунке приведен пример и порядок просмотра городов. В кружках указаны номера городов, рядом с кружками - суммарная стоимость проезда до этого города из первого.
Итак, запись логики.
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,1];Way[N]:=v;{Последний город пути. Доформировываем решение и сравниваем его с лучшим из ранее полученных.}
if Cost<BestCost then begin
BestCost:=Cost;BestWay:=Way;
end;
exit;
end;
Nnew[v]:=false;Way[Count]:=v;{Город с номером v пройден, записываем его номер в путь коммивояжера}
for i:=1 to N do if Nnew[B[v,i]] then
Solve(B[v,i], Count+1,Cost+A[v,B[v,i]]); {Поиск города, в который коммивояжер может пойти из города с номером v}
Nnew[v]:=true; {Возвращаем город с номером v в число непройденных}
end;
Первый вызов - Solve(1,1,0).
Разработка по данному «шаблону» работоспособной программы - техническая работа. Если Вы решитесь на это, то есть смысл проверить ее работоспособность на следующем примере (матрица А приведена ниже). Решение имеет вид 1 8 9 2 5 10 6 7 4 3 1, его стоимость 158.
@ |
32 |
19 |
33 |
22 |
41 |
18 |
15 |
16 |
31 |
32 |
@ |
51 |
58 |
27 |
42 |
35 |
18 |
17 |
34 |
9 |
51 |
@ |
23 |
35 |
49 |
26 |
34 |
35 |
41 |
33 |
58 |
23 |
@ |
33 |
37 |
23 |
46 |
46 |
32 |
22 |
27 |
35 |
33 |
@ |
19 |
10 |
23 |
23 |
9 |
41 |
42 |
49 |
37 |
19 |
@ |
24 |
42 |
42 |
10 |
18 |
35 |
26 |
23 |
10 |
24 |
@ |
25 |
25 |
14 |
15 |
18 |
34 |
46 |
23 |
42 |
25 |
@ |
1 |
32 |
16 |
17 |
35 |
46 |
23 |
42 |
25 |
1 |
@ |
32 |
31 |
34 |
41 |
32 |
9 |
10 |
14 |
32 |
32 |
@ |
Оцените время работы программы. Если у Вас мощный компьютер, то создайте матрицу А[1..50,1..50] и попытайтесь найти наилучшее решение с помощью разобранного метода. Заметим, что набор 2500 чисел - утомительное занятие и разумная лень - «двигатель прогресса».