8.4 Задания для самостоятельной работы

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

9 Метод ветвей и границ решения задачи о кратчайшем пути

Рассмотрим задачу о кратчайшем пути в направленном ациклическом графе.

Пусть имеем направленный ациклический граф , где- не пустое конечное множество вершин;- множество направленных (ориентированных) дуг:, каждой дугеграфа поставлен в соответствие неотрицательный вес (длина) .

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

Обозначим длину дуги, которая соединяет вершины графа и, .

Длина пути - сумма длин дуг, которые входят в него.

Найти кратчайший путь, который соединяет вершины графа и

Например, имеем следующий направленный ациклический граф (рисунок 9.1).

Рисунок 9.1 – Ациклический граф

Найти для него кратчайший путь из вершины А () к вершинеК ().

Определим стратегию метода ветвей и границ для решения данной задачи, то есть определим:

• правило ветвления;

• способ оценивания получаемых подмножеств;

• правило выбора вершины для ветвления;

• тест.

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

Каждой вершине дерева поиска (подмножеству решений) отвечает частичный подпуть, которым начинаются все пути этого подмножества.

Нижняя граница (оценка) каждого подмножества решений – длина известного частичного пути из вершины А к некоторой вершине , которая отвечает этому подмножеству.

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

Рекордным решением на текущем шаге является тот полный путь из вершины (А) к вершине(К), который имеет наименьшую из всех известных на это время путей длину.Рекорд - длина рекордного пути.

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

В нашем примере на первой итерации все множество путей разбивается на три подмножества:

–подмножество путей из А к К, в которых АВ – начальный подпуть;

–подмножество путей из А к К, в которых АСС – начальный подпуть;

–подмножество путей из А к К, в которых АD – начальный подпуть.

Так, все пути подмножества имеют длину , не меньше 2 (2 – длина дугиа1, которая соединяет вершины А и В), то есть . Аналогично, . Полученные подмножества и их нижние оценки будем изображать следующим образом (рисунок 9.2).

Рисунок 9.2 – Ветвление исходного множества путей

На каждой итерации выполняется ветвление той вершины, которая имеет наименьшую на текущий момент нижнюю границу. Значит, следующим разветвлять надо множество , которое имеет оценку 2 (оценки множестваиравняются соответственно 3 и 4). Поскольку из вершиныB выходят три дуги (см. рис. 19), множество разбивается на три подмножества. Эти подмножества имеют такие оценки:

, равняется длине частичного пути ABC ;

, равняется длине частичного пути ABE;

, равняется длине частичного пути ABF.

После ветвления множества дерево поиска примет такой вид, как показан на рисунке 9.3.

Рисунок 9.3 – Продолжение ветвления

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

• –получим вершины и;

• –получим вершины и;

• –получим вершину ;

• (с начальным подпутем a1–b2–f2) – получим вершины и;

• –получим вершины и;

• (с начальным подпутем a2–с2) – получим вершины и;

• (с начальным подпутем a1–b2–f2–g2)– получим вершину и допустимое решениес длиной 8, которое помечаем как рекордное; .

Согласно тесту исключаем их списка подмножества, которые отвечают вершинам,,,,,.

Дальнейший порядок ветвления такой:

• (с начальным подпутем a2–с2–g2) – получим вершину и второе допустимое решениес длиной, равной рекорду; исключаем из спискаполученную вершину;

• –получим вершины и; исключаем из спискаполученную вершину;

• –получим вершины ии сразу отбросим соответствующие подмножества ;

• –получим допустимое решение худшее, чем текущее рекордное;

• –получим вершину и допустимое решениехудший, чем текущее рекордное; исключаем из спискаполученную вершину.

Список пустой. На текущий момент имеем два рекордных решения.

Рисунок 9.4 – Окончательное дерево поиска решений

Итак, граф имеет два кратчайших пути : A-B-F-G-J-K ; A-C-G-J-K. Их длина – 8.