3.2.1 Решение обобщенной задачи коммивояжера

Пусть каждой дуге (i, j) графа (I, U) поставлено в соответствие число   называемое длиной дуги.

Рассмотрим задачу: определить кратчайший путь из множества А в множество В, пересекающий каждое множество разбиения один и только один раз. Очевидно, что если каждое множество разбиения состоит из одного элемента и  , то имеем обычную задачу коммивояжера.

Определим функцию  : положим для произвольного пути  . Итак, значениями функции   будут множества номеров подмножеств разбиения, которые пересекает путь  . Пусть каждое множество Ф_i,  , состоит из всевозможных подмножеств множества {1, 2,…, p}, a  . Применим для решения этой задачи следующий алгоритм.

Достаточной системой функций в данном случае будут функции

Обозначим через   число элементов произвольного конечного множества А.

Шаг 0. Положим  . Пометим вершины   признаками  . Для помеченных вершин увеличим  на 1. Рассмотрим одну из пометок и перейдем к шагу 1.

Шаг 1. Пусть   – рассматриваемая пометка. Пометим признаками   все те вершины, для которых  . Для вновь помеченных вершин увеличим   на 1.

Рассмотрим следующую помеченную вершину, и будем повторять помечивания до тех пор, пока не пометим некоторую вершину   так, чтобы для признака  пометки этой вершины выполнялось условие   или пока нельзя будет сделать дальнейших пометок. В первом случае перейдем к шагу 2. а во втором к шагу 3.

Шаг 2. Строим кратчайший допустимый путь от вершины  . Пусть   – пометка вершины, для которой . Перейдём к вершине   и рассмотрим пометку   вершины,

для которой  . Далее перейдем к вершине  , с пометкой  , для которой  . Последовательность  и является кратчайшим допустимым путем.

Шаг 3. Пусть   – множество помеченных вершин. Рассмотрим все возможные числа  при  . Определим среди этих чисел наименьшее и возьмем его за новое приближение  к длине искомого пути. Затем перейдем к шагу 1.

Этот алгоритм можно изменить. Если для некоторой пометки  при всех j, для которых   или  , то путь соответствующий этой пометке, уже продлен во все смежные с  вершины. Следовательно, для таких пометок признаки   можно стирать.

3.3 Метод ветвей и границ (мвг)

Представим, что необходимо обойти все города страны. Так как их много, то определить кратчайший путь затруднительно. Тогда можно выбрать некоторое разбиение множества городов, например, рассматривать республики, области или районы, и определить кратчайший путь, пересекающий каждое из выбранных подмножеств разбиения только один раз. Затем уже в пределах выбранных подмножеств достроить полученный путь до требуемого. Такой подход используется в методе ветвей и границ. Этот метод позволяет опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Тем не менее, удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этом методе, и родственных алгоритмов нет, хотя практика показывает, что на современных ЭВМ они иногда позволяют решить задачу коммивояжера для графов с количеством вершин, меньшим 100.

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.