3.6. Задача коммивояжера. Её решение методом ветвей и границ.

Задача. Имеется взвешенный неориентированный связный граф. Необходимо найти гамильтонов цикл наименьшей длины, т.е. нужно обойти все вершины графа, побывав в каждой из них по одному разу, затратив как можно меньше денег.

Оценим трудоемкость методом прямого перебора.

Имеем n! всевозможных маршрутов. Стоимость каждого маршрута – сумма n ребер. Следовательно,

T(n) = n!·n

n! можно заменить (n-1)!, т.к. маршрут проходит через все вершины, и поэтому в качестве стартовой мы можем взять вершину v_i, располагая оставшиеся вершины (n-1) произвольным образом.

T(n) = (n-1)!·n = n! – неполиномиальная.

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

Идея метода ветвей и границ. Пусть нам необходимо найти минимум некоторой функции f(x), xD. Предположим, что у нас есть:

а) Алгоритм дробления множества D на всё уменьшающиеся части (вплоть до одноэлементных множеств).

б) Для каждой части D_i, полученной в результате дробления, имеется некоторая оценка H(D_i) ≤ f(x), x D_i. Эта величина оценивает значение функции f на интервале D_i снизу, причем на одноэлементных множествах эта оценка совпадает со значением функции f.

Тогда для нахождения минимума поступаем следующим образом.

Возьмем точку х из множества D (желательно, что бы f(x) была как можно меньше). Объявим f(x) рекордом r. Делим множество D на части:

где f – функция-оценка минимума.

Для множества D⁽¹⁾₂ справедливо:

H(D⁽¹⁾₂) > r, тогда для всех yD⁽¹⁾₂ выполняется f(y) ≥ H(D⁽¹⁾₂) > r, следовательно, на этом множестве мы минимума не достигнем, поэтому данное множество отбрасываем. Таким образом, ветвь мы отрубаем тогда и только тогда, когда функция-оценка минимума на этом множестве больше либо равна рекорда. Далее работаем с множествами D⁽¹⁾₁ и D⁽¹⁾₄, и , не смотря на то, что множество D⁽¹⁾₁ кажется более перспективным, может случится так, что реальное значение минимума будет достигнуто на D⁽¹⁾₄ (так как мы не требовали, чтобы выполнялось H(D⁽ⁱ⁾_k = min f(x), а H(D⁽ⁱ⁾_k является лишь некоторой оценкой этого минимума снизу).

H(D⁽ⁱ⁾_k) ≤ min f(x), x D⁽ⁱ⁾_k.

Множество D⁽¹⁾₃ мы можем в процессе работы не рассматривать, если нам достаточно найти хотя бы одну точку, в которой достигается минимум, если же нам наобходимо найти все точки, то множество D⁽¹⁾₃ считаем перспективным.

Замечание. Подобное дробление множества D продолжаем до тех пор, пока не доберемся до одноэлементных множеств (нижнего этажа дерева).

Рисунок 3.9. – Дробление множества, где

перспективное множество

неперспективное множество

При этом возможны два вариант дробления.

Схема одновременного ветвления.

На каждом шаге мы работает со всеми перспективными множествами:

нижний этаж – одноэлементные множества

Рисунок 3.10 – Одновременное дробление

Схема одностороннего ветвления.

Отличие этой схемы от предыдущей заключается в том, что на каждом шаге мы работает только с одним перспективным множеством, а не со всеми сразу, как в схеме одновременного ветвления (см.рис.3.11).

Здесь

перспективное множество;

неперспективное множество;

? отложенное перспективное множество;

? ветвь, ставшая неперспективно после обновления рекорда.

Рисунок 3.11 – Одностороннее дробление

По ходу дробления на каждом шаге из всех множеств выбирается самое перспективное – то, на котором меньшего всего оценка f. С ним и будем работать дальше. Рассмотрение остальных перспективных множеств пока отложим. Эта схема предпочтительнее, т.к. при ее применении мы быстрее доберемся до нижнего этажа, где сможем обновить рекорд, а после его обновления многие множества, ранее перспективные, при новом рекорде могут перейти в разряд неперспективных, и их мы рассматривать вообще не будем. Таким образом трудоемкость схемы одностороннего ветвления существенно меньше схемы одновременного ветвлении.

Алгоритм одностороннего ветвления

На каждом шаге оставляем в работе только одно, самое перспективное множество. Таким образом доходим до нижнего этажа дерева, при этом все находящиеся на нем множества станут одноэлементными. Обновляем рекорд. Выкидываем уже неперспективные отложенные ветви. Среди оставшихся перспективных ветвей выбираем самую перспективную (либо оценке f, либо по уровню, на котором расположена в дереве – чем ближе к нижнему этажу, тем перспективнее отложенная ветвь).

Подобную процедуру подъема и спуска продолжаем до тех пор, пока не останется ни одной перспективной ветви.

Применение метода ветвей и границ для решения задачи коммивояжера.

В нашем случае исходное множество D – множество всевозможных маршрутов, проходящих по всем вершинам графа (так называемых гамильтоновых циклов), для определенности стартующих из точки 0. Напомним, что Гамильтонов цикл должен содержать все вершины графа, причем. Переходя по его ребрам, можно обойти все вершины, побывав в каждой только по одному разу.

В предложенной схеме дробления буду возникать подмножества D следующего вида:

Множество состоит из всевозможных маршрутов, у которыхv₁, v₂, … ,v_k – первоначальный участок, а следующий переход из вершины v_k мы можем совершить в любую вершину, кроме указанной в фигурных скобках вершин u₁, …,u _l.. Также мы не можем идти в вершины v₁, v₂, … ,v_k, так как тогда маршрут будет уже не гамильтонов.

Составим оценку f для множества следующего вида:

где

(u) – стоимость выхода (выезда) из вершины u (т.е. минимально возможная цена, за которую мы можем выехать в какую-либо другую допустимую вершину),

(w) – минимально возможная стоимость въезда в вершину w после уже уплаченных стоимостей выездов.

Пример. Пусть у нас имеется гамильтонов цикл в ориентированном графе (для орграфа матрица стоимости ребер не симметрична относительна своей главной диагонали). По главной диагонали расположены бесконечности, а не нули, потому что в гамильтонов цикле петли запрещены.

Имеем первоначальный маршрут: D = [(2, 5, 0), {1}].

Таким образом, из вершины 0 мы можем идти в любую, кроме 1 (так как она запрещенная), 2 и 5 (так как уже прошли).

Вычисляем оценку Н. Для этого:

1. Вычеркиваем из имеющейся матрицы 2 и 5 строки, так как стоимости ребер, по которым можно попасть во 2 и 5 вершины, нам не понадобятся, в эти вершины мы уже въезжали и больше туда не собираемся.

2. Вычеркиваем 5 и 0 столбцы, так как уже въезжали в вершины 5 и 0.

3. Получилась матрица:

Стоимость переезда из 0 в 1полагаем равно бесконечности, так как он запрещен. В каждой строке находим минимальных элемент (минимальную стоимость выезда из вершин 0, 1, 3 и 4, ), т.е. находим :

«Уплачиваем» найденные стоимости выездов, т.к. вычитаем из каждого элемента строки минимальный элемент данной строки. Стоимости выездов «уплачены», однако мы еще должна заехать в вершины 1, 2, 3, 4. Находим для них оценку .

Итак, оценка

H (D) = C(2,5) + C(5,0) + ((0) + (1) + (3) + (4)) + ((0) + (2) + (3) + (4)) =

из первоначальной матрицы

= 3 + 3 + (6 + 3 + 4 + 2) + (0 + 0 + 1 + 0) = 22.

То есть, проехав по любому маршруту из множества D [(2, 5, 0), {1}], мы не можем потратить менее 22 долларов. Осталось записать схему возможных вариантов дробления маршрутов В. Рассмотрим два варианта схемы на примере пятиэлементного множества:

Первый вариант

Рисунок 3.12

Тут не возникает запретных вершин.

Второй вариант

При этой схеме дробления на каждом этапе ветка делится на две новые ветви, но также возникают и запретные вершины.

Рисунок 3.13

и т.д.

Замечание. Обычно метод ветвей и границ позволяет существенно уменьшить объем перебора. Однако это справедливо не для каждой задачи, например для задачи коммивояжера до сих пор неизвестен алгоритм, который гарантированно бы решал ее за полиномиальное время. Впрочем. Для большинства графов он дает существенный выигрыш по сравнению с прямым перебором.

Домашнее задание №5 (А, Б, В)

А) Найти остов минимального веса для связанного взвешенного неориентированного графа, заданного матрицей стоимостей переездов из одной вершины в другую:

Б) Найти кратчайшее расстояние от третьей до всех остальных вершин графа, заданного матрицей стоимостей переездов из одной вершины в другую

Б1) с помощью алгоритма Форд-Беллмана

Б2) с помощью алгоритма Дейкстры

Матрица стоимостей:

В) Определить оценку Н, если первоначальный маршрут (0,3) {1,5}.

Матрица стоимостей переездов: