Домашнее задание по информатике №3
1 Задача о коммивояжере (перебор вариантов)
Классическая формулировка задачи известна уже более 200 лет:
имеются n городов, расстояния между которыми заданы; коммивояжеру (бродячему торговцу) необходимо выйти из какого-то города, посетить остальные n-1 городов точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).
Задача коммивояжера [1] принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.
Методы решения задачи
Существует множество методов решения задачи коммивояжера, но классическими стали такие известные методы, как:
1) поиск в глубину [2, 3];
2) поиск в ширину [4];
3) метод грубой силы или полного перебора (самый долгий) [5].
2 Постановка задачи коммивояжера на графах
Пусть имеется n городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i≠j. Если прямого маршрута сообщения между городами не существует, а также для всех i=j полагаем, что dij=∞. На этом основании расстояния между городами удобно представить в виде матрицы 
.
Рис. 1. Неориентированный граф задачи коммивояжера
Если городам поставить в соответствие вершины графа (см. рис. 1), а соединяющим их дорогам дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной, а длина контура определяется суммой длин всех дуг, входящих в контур. Таким образом, необходимо построить кольцевой маршрут проезда всех городов минимальной длины, начиная с любого пункта и в любую сторону.
Поскольку всего городов n, то коммивояжер, выехав из заданного города, должен побывать в остальных (n-1) городах только один раз. Следовательно, всего существует (n-1)! возможных маршрутов, среди которых один или несколько – оптимальные. В большинстве случаев можно предположить, что расстояние между городами i и j является симметричным и равно расстоянию от города j до города i, т. е. 
. Расстояния между городами запишем в виде соответствующей матрицы и обозначим ее через D. Если в задаче n городов, то D является матрицей размером 
с неотрицательными элементами 
, которые отображают длины дуг в сети городов. При n=5 количество возможных, вариантов маршрутов равно 
. Расстояния между городами заданы матрицей в табл. 1.
Таблица 1
i j | 1 | 2 | 3 | 4 | 5 |
1 | ∞ | 90 | 80 | 40 | 100 |
2 | 60 | ∞ | 40 | 50 | 70 |
3 | 50 | 30 | ∞ | 60 | 20 |
4 | 10 | 70 | 20 | ∞ | 50 |
5 | 20 | 40 | 50 | 20 | ∞ |
Маршрут можно представить в виде замкнутого контура, представляющего собой кольцевой маршрут, например, для графа, изображенного на рис. 1. Возможный вариант можно записать в виде совокупности соответствующих пар дуг:
Длина 
маршрута равна сумме соответствующих длин дуг матрицы расстояний, тогда целевую функцию можно записать так:
Для любого допустимого маршрута каждая строка и каждый столбец матрицы расстояний D содержат только по одному элементу. Решением задачи является определение кольцевого маршрута минимальной длины.
3 Задание на самостоятельную проработку
Разработать программу решения задачи коммивояжера одним из трёх методов, перечисленных в разделе 1.
В качестве подсказки используйте информацию приведённую из списка использованных источников.
Проверить работоспособность программы на приведённом ниже примере (матрица А приведена ниже).
@ | 32 | 19 | 33 | 22 | 41 | 18 | 15 | 16 | 31 |
32 | @ | 51 | 58 | 27 | 42 | 35 | 18 | 17 | 34 |
19 | 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 8 9 2 5 10 6 7 4 3 1, его стоимость 158. Оцените время работы программы.
Если у Вас мощный компьютер, то создайте матрицу А[1..50,1..50] и попытайтесь найти наилучшее решение с помощью разобранного метода.
Список использованных источников
1 http://ru. wikipedia. org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0
2 http://kvodo. ru/dfs. html
3 http://ru. wikipedia. org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83
4 http://kvodo. ru/search-width. html
5 http://ru. wikipedia. org/wiki/%D0%9F%D0%BE%D0%BB%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D0%B1%D0%BE%D1%80
