Задача коммивояжера.

Знаменитая задача коммивояжера, поставленная еще в 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, для которых или , то путь соответствующий этой пометке, уже продленво все смежные с вершины. Следовательно, для таких пометок при­знаки можно стирать.