Знаменитая задача коммивояжера, поставленная еще в 1934 г., является одной из самых важнейших задач в теории графов. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы.
Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.
Задача коммивояжера является так называемой NP-трудной задачей, т.е. задачей, точное решение которой в общем случае может быть получено только за экспоненциальное время. Следовательно, решать ее переборным алгоритмом неэффективно при большом количестве вершин графа.
Решение обобщенной задачи коммивояжера
Пусть каждой дуге (i, j) графа (I, U) поставлено в соответствие число называемое длиной дуги.
Рассмотрим задачу: определить кратчайший путь из множества А в множество В, пересекающий каждое множество разбиения один и только один раз. Очевидно, что если каждое множество разбиения состоит из одного элемента и , то имеем обычную задачу коммивояжера.
Определим функцию : положим для произвольного пути . Итак, значениями функции будут множества номеров подмножеств разбиения, которые пересекает путь . Пусть каждое множество Фi, , состоит из всевозможных подмножеств множества {1, 2, ..., p},a . Применим для решения этой задачи следующий алгоритм.
Достаточной системой функций в данном случае будут функции
Обозначим через число элементов произвольного конечного множества А.
Шаг 0. Положим . Пометим вершины признаками . Для помеченных вершин увеличим на 1. Рассмотрим одну из пометок и перейдем к шагу 1.
Шаг 1. Пусть - рассматриваемая пометка. Пометим признаками все те вершины, для которых . Для вновь помеченных вершин увеличим на 1.
Рассмотрим следующую помеченную вершину, и будем повторять помечивания до тех пор, пока не пометим некоторую вершину так, чтобы для признака пометки этой вершины выполнялось условие или пока нельзя будет сделать дальнейших пометок. В первом случае перейдем к шагу 2. а во втором к шагу 3.
Шаг 2. Строим кратчайший допустимый путь от вершины . Пусть - пометка вершины, для которой . Перейдём к вершине и рассмотрим пометку вершины,
для которой . Далее перейдем к вершине , с пометкой , для которой . Последовательность и является кратчайшим допустимым путем.
Шаг 3. Пусть - множество помеченных вершин. Рассмотрим все возможные числа при . Определим среди этих чисел наименьшее и возьмем его за новое приближение к длине искомого пути. Затем перейдем к шагу 1.
Этот алгоритм можно изменить. Если для некоторой пометки при всех j, для которых или , то путь соответствующий этой пометке, уже продленво все смежные с вершины. Следовательно, для таких пометок признаки можно стирать.