На этом шаге мы приведем постановку задачи.
Проблема коммивояжера - классическая и одна из наиболее широко обсуждаемых задач во всей теории вычислений. Коммивояжер должен посетить все города на карте ровно один раз и вернуться в конце путешествия в город, с которого начал маршрут. Между любыми двумя городами существует прямая дорога, и коммивояжер может посещать города в любом порядке. Каков самый короткий маршрут для него?
Эту задачу можно представить как графовую, в которой города - это вершины, а дороги между ними - ребра. Вашим первым побуждением может быть желание найти минимальное связующее дерево, как описано в 56 шаге. К сожалению, решить задачу коммивояжера не так просто. Минимальное связующее (остовное) дерево - это кратчайший путь для соединения всех городов, но оно не обеспечивает кратчайшего пути для посещения всех городов ровно один раз.
Несмотря на то что поставленная задача кажется довольно простой, не существует алгоритма, который мог бы быстро решить ее для произвольного числа городов. Что мы подразумеваем, говоря "быстро"? Имеется в виду, что есть проблема: перед нами НП-трудная задача. НП-трудная (недетерминированная полиномиальная трудная) задача - это задача, для которой не существует алгоритма полиномиального времени. (Требуемое время является полиномиальной функцией от размера входных данных.) По мере увеличения числа городов, которые должен посетить коммивояжер, сложность задачи растет исключительно быстро. Решить задачу для 20 городов намного труднее, чем для 10. Решить задачу идеально (оптимально) для нескольких миллионов городов, за разумное время невозможно (насколько нам известно).
Наивный подход к решению задачи коммивояжера имеет сложность O(n!). Почему это так, мы разберем в следующих шагах.
На следующем шаге мы рассмотрим наивный подход к решению этой задачи.
