Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов
 Скачать 1.41 Mb.
|
|
Вариант алгоритма Дейкстры Рассмотрим другой вариант представления и реализации алгоритма Дейкстры. Пусть l(v i ) пометка вершины v i ; p v ≡ − начальная (базовая) вершина. 1. Положим l(p) = 0. Далее будем считать эту пометку постоянной. Для всех остальных вершин пометка l(v i ) ∞ = , считаем эти пометки временными. 2. Обновление пометок. Для всех вершин из образа вершины p } ) , ( : { ) ( E w p V w p O v i ∈ ∈ = ∈ (вершин, в которые можно попасть непосредственно из p), не имеющих постоянной пометки, ( ) ( ) ( ) ( ) { } i i i v p c p l v l v l , , min + = , где ( ) i v v c , − вес дуги из p в v i 3. Найдем ∗ i v с минимальной временной пометкой, обозначим ее как p v i ≡ ∗ , пометка ( ) ( ) p l v l i = ∗ становится постоянной (при этом ( ) p l есть длина кратчайшего пути из v в ∗ i v ). 4. Если вершина p совпадает с конечной вершиной (если требуется найти путь из v в w) или пометки всех вершин постоянные, то работа алгоритма завершена. Иначе возврат к шагу 2. Пример Пусть дан нагруженный орграф с матрицей длин дуг С(D). Необходимо найти минимальный путь из v 1 в v 9 , используя алгоритм Дейкстры. 58 ( ) ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ = 9 5 15 4 10 14 12 2 1 11 8 9 6 4 10 5 3 7 1 * 9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 v v v v v v v v v v v v v v v v v v D C 1. Метка вершины v 1 постоянна, равна 0. 2. Из вершины v 1 можно попасть в вершины v 3 (за 1) и v 6 (за 7), т. е. теперь временные метки вершин v 3 и v 6 становятся равными 1 и 7 соответственно: v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ 7 ∞ ∞ ∞ 3. Минимальная из временных пометок – 1, поэтому v 3 принимает статус начальной и ее метка становится постоянной. Снова меняем метки оставшихся вершин. Из v 3 можно попасть в v 1 (нам туда не надо) и v 6 (за 4), тогда метка v 6 будет равна ( ) { } 5 4 1 , 7 min 6 = + = v l v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ 4. Поскольку в последней строке одна временная метка ∞ ≠ , то она автоматически становится постоянной. Продолжаем процесс: 59 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 1 шаг→ 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 шаг→ ∞ 1 ∞ ∞ 7 ∞ ∞ ∞ 3 шаг→ ∞ ∞ ∞ 5 ∞ ∞ ∞ 4 шаг→ 7 ∞ ∞ 17 ∞ ∞ 5 шаг→ ∞ 10 17 12 ∞ 6 шаг→ 18 17 12 ∞ 7 шаг→ 18 17 27 8 шаг→ 18 27 9 шаг→ 27 Таким образом, путь из v 1 в v 9 имеет вес 27. Восстановим этот путь начиная с конца. По столбцу v 9 поднимаемся до строки, в которой получено конечное значение (7-й шаг). В тот момент времени роль вершины с постоянной меткой играла v 8 . В столбце v 8 число 12 появляется на 5-м шаге, чему соответствует v 2 . Продолжая, доберемся до v 1 . Восстановленный путь: v 1 → v 3 → v 6 → v 2 → v 8 → v 9 (общий вес = 1 + 4 + 2 + 5 + 15 = 27). 2.7.4. Метод ветвей и границ Метод ветвей и границ(англ. branch and bound) – общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации. Метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Общая идея метода может быть описана на примере поиска минимума функции f(x) на множестве допустимых значений переменной x. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ). Процедура ветвления состоит в разбиении множества допустимых значений переменной x на подмножества меньших размеров. Процедуру можно рекурсивно применять к подмножествам. Полученные подмножества образуют дерево, называемое деревом ветвей и границ. Вершинамиэтого дерева являются построенные подмножества множества значений переменной x. 60 Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной x. В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подмножестве А дерева поиска больше, чем верхняя граница на каком-либо ранее просмотренном подмножестве B, то А может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную m; любая вершина дерева поиска, нижняя граница которой больше значения m, может быть исключена из дальнейшего рассмотрения. Если нижняя граница для вершины дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующем подмножестве. Задача коммивояжера Одна из самых известных и важных задач теории графов, представляющая собой целый класс задач оптимизации, – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается под названием «задача о бродячем торговце». Суть задачи сводится к поиску пути наименьшей стоимости, проходящего через все вершины графа по одному разу с возвратом в конце в исходную вершину. Решим задачу методом ветвей и границ. Введем следующие обозначения: пусть D = (V, X) – полный орграф и f: X → R – весовая функция, V = {v 1 ,v 2 ,…,v n } – множество вершин, X – множество дуг, C = {c ij }, i, j = 1,2…n – матрица длин дуг данного орграфа, т. е. с ij = f(v i ,v j ), причем для любого i справедливо c ii = ∞. Требуется найти простой остовной контур (или контур коммивояжера) минимального веса. Следует заметить, что требование полноты орграфа можно опустить. Однако в этом случае гамильтонов контур может и не существовать (для его существования достаточна полнота орграфа). Следовательно, описываемый метод ветвей и границ приведет к полному перебору всех вариантов незаконченных контуров прежде, чем станет очевиден факт отсутствия решения. Очевидно, что вычитая любую константу из всех элементов любой строки или столбца матрицы C, минимальный путь останется минимальным. 61 В этой связи введем следующие термины. Пусть имеется некоторая числовая матрица. Привести строку этой матрицы означает выделить в строке минимальный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте минимального элемента окажется нуль, а все остальные элементы будут неотрицательными. Аналогичный смысл имеет фраза «привести столбец матрицы». Привести матрицу по строкам означает, что все строки приводятся. Аналогичный смысл имеет фраза «привести матрицу по столбцам». Приведение матрицы означает сначала приведение этой матрицы по строкам, а затем по столбцам. Если с помощью приведенной матрицы удастся построить такую последовательность переходов по вершинам графа, которым соответствует последовательность нулевых элементов приведенной матрицы, то ясно, что для этой матрицы получим минимальный путь. Но он же будет минимальным и для исходной матрицы длин дуг С, только для того, чтобы получить правильную стоимость пути, нужно будет прибавить все константы приведения. Таким образом, сумма констант приведения играет роль оценки снизу для стоимости всех путей. Весом элемента матрицы называют сумму констант приведения матрицы. Следовательно, слова «самый тяжелый нуль в матрице» означают, что в матрице подсчитан вес каждого нулевого элемента, и зафиксирован нуль с максимальным весом. Пример Пусть дан нагруженный орграф с матрицей длин дуг С(D). ( ) ∞ ∞ ∞ ∞ = 15 6 12 8 14 7 7 8 10 9 11 5 D C 62 Найдем константу приведения в каждой строке и выпишем ее в отдельный столбец min r. v 1 v 2 v 3 v 4 min r v 1 ∞ 5 11 9 5 v 2 10 ∞ 8 7 7 v 3 7 14 ∞ 8 7 v 4 12 6 15 ∞ 6 Из каждого элемента в строке вычитаем соответствующее значение константы приведения (min r). v 1 v 2 v 3 v 4 min r v 1 ∞ 0 6 4 5 v 2 3 ∞ 1 0 7 v 3 0 7 ∞ 1 7 v 4 6 0 9 ∞ 6 В итоге в каждой строке будет хотя бы одно нулевое значение. Далее повторяем процедуру для каждого столбца и выписываем константы приведения в отдельную строку min c. v 1 v 2 v 3 v 4 min r v 1 ∞ 0 6 4 5 v 2 3 ∞ 1 0 7 v 3 0 7 ∞ 1 7 v 4 6 0 9 ∞ 6 min c 0 0 1 0 Вычитаем из каждого элемента матрицы соответствующее ему min c. В итоге и в каждом столбце будет хотя бы одно нулевое значение. v 1 v 2 v 3 v 4 min r v 1 ∞ 0 5 4 5 v 2 3 ∞ 0 0 7 v 3 0 7 ∞ 1 7 v 4 6 0 8 ∞ 6 min c 0 0 1 0 63 Обозначим за Г множество всех обходов коммивояжера (т. е. всех простых ориентированных остовных контуров). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число ϕ(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы длин дуг графа и является оценкой снизу для стоимости минимального пути коммивояжера. Начальную матрицу длин дуг данного графа обозначим через С 1 Подсчитаем ϕ(Г) = 5 + 7 + 7 + 6 + 1 = 26. Таким образом, нижняя оценка искомого пути найдена: 26 ≥ l . Для получения верхней оценки выберем один из существующих в графе гамильтоновых контуров и его стоимость возьмем за максимально возможную. Построим этот контур, пользуясь принципом «ближайшего соседа» (начинаем с произвольной вершины, например с v 3 , ищем дугу минимального веса из нее, это дуга в вершину v 1 , и т. д., исключая переходы в уже пройденные вершины, только на последнем, четвертом шаге возвращаемся в v 3 ): v 3 v 1 v 2 v 4 v 3 , 34 15 7 5 7 = + + + = l Окончательно определенные границы для оптимального пути: 34 26 ≤ ≤ l Для каждого нулевого значения получившейся матрицы находим вес: сумму заново посчитанных констант приведения по строке и столбцу, в которых размещено данное нулевое значение. Само оно при этом не учитывается. Полученный вес записываем рядом с нулем, в скобках. v 1 v 2 v 3 v 4 v 1 ∞ 0 (4) 5 4 v 2 3 ∞ 0 (5) 0 (1) v 3 0 (4) 7 ∞ 1 v 4 6 0 (6) 8 ∞ Далее выбираем нулевое значение с наибольшим весом. Это значение 6 в ячейке v 4 v 2 . Разобьем множество Г на две части: множество ( ) { } 2 , 4 Γ (все контуры, проходящие через дугу v 4 v 2 ) и ( ) { } 2 , 4 Γ (все контуры, не проходящие через дугу v 4 v 2 ). Такое ветвление определяет необходимость выбора одного из этих вариантов. 64 Множеству ( ) { } 2 , 4 Γ соответствует матрица С 1,1 , полученная вычеркиванием соответствующих строки (v 4 ) и столбца (v 2 ). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычеркиванием строки и столбца, в матрице надо заменить на ∞ числа в определенных ячейках так, чтобы исключить возврат в уже пройденные вершины, т. е. чтобы не получалось коротких контуров длиной меньше n. В данном случае из v 2 уже нельзя попасть в v 4 , поэтому в ячейке v 2 v 4 ставим ∞. Найденные веса нулей удаляются. v 1 v 3 v 4 v 1 ∞ 5 4 v 2 3 0 ∞ v 3 0 ∞ 1 После приведения матрица С 1,1 (приводим только строку v 1 с константой приведения 4). v 1 v 3 v 4 v 1 ∞ 1 0 v 2 3 0 ∞ v 3 0 ∞ 1 Сумма констант приведения матрицы С 1,1 здесь равна 4, поэтому ϕ(Г {(4,2)} ) = ϕ {4,2} = 26 + 4 = 30. Множеству ( ) { } 2 , 4 Γ , в свою очередь, соответствует другая матрица – С 1,2 , полученная заменой на ∞ элемент с 4,2 в матрице С 1 : v 1 v 2 v 3 v 4 v 1 ∞ 0 5 4 v 2 3 ∞ 0 0 v 3 0 7 ∞ 1 v 4 6 ∞ 8 ∞ Сумма констант последнего приведения равна весу замененного нуля, т. е. 6, так что ( ) { } ( ) 32 6 26 2 , 4 = + = Γ ϕ 65 Теперь выберем между множествами ( ) { } j i, Γ и ( ) { } j i, Γ то, на котором минимальна функция ϕ. Поэтому дальнейшей разработке подвергнется множество Г {(4,2)} Таким образом найдена первая дуга пути: v 4 v 2 , построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдет в искомый гамильтонов контур (контур коммивояжера), который будет иметь минимальный вес. В матрице С 1,1 вычислим веса нулевых ячеек: v 1 v 3 v 4 v 1 ∞ 1 0 (2) v 2 3 0 (4) ∞ v 3 0 (4) ∞ 1 Выбираем нулевое значение с наибольшим весом. В данном случае это 4 и таких значений два, выбирается любое из них, пусть это будет ячейка v 2 v 3 . Теперь следует рассматривать множества ( ) ( ) { } 3 , 2 ; 2 , 4 Γ и ( ) ( ) { } 3 , 2 ; 2 , 4 Γ . Ясно, что ( ) ( ) { } ( ) 34 4 30 3 , 2 ; 2 , 4 = + = Γ ϕ Вычеркнем строку v 2 и столбец v 3 в матрице С 1,1 и избавимся от короткого цикла, заменив 1 в ячейке v 3 v 4 на ∞. Получим матрицу С 1,1,1 , которая после приведения будет следующей: v 1 v 4 v 1 ∞ 0 v 3 0 ∞ При этом ( ) ( ) { } ( ) 30 0 30 3 , 2 ; 2 , 4 = + = Γ ϕ , следовательно, в дальнейшем разрабатываем ( ) ( ) { } 3 , 2 ; 2 , 4 Γ . Таким образом найдена вторая дуга пути: v 2 v 3 Приведем матрицу С 1,1,1 и подсчитаем веса нулевых ячеек. v 1 v 4 v 1 ∞ 0 (∞) v 3 0 ( ∞) ∞ 66 Выбираем одно из нулевых значений с весом ∞: v 3 v 1 . При этом ( ) ( ) ( ) { } ( ) ∞ = ∞ + = Γ ϕ 30 1 , 3 ; 3 , 2 ; 2 , 4 , ( ) ( ) ( ) { } ( ) 30 0 30 1 , 3 ; 3 , 2 ; 2 , 4 = + = Γ ϕ Таким образом найдена третья дуга пути: v 3 v 1 . Строку v 3 и столбец v 1 вычеркиваем. v 4 v 1 0 Очевидно, что оставшаяся последняя дуга оптимального пути – это v 1 v 4 . Теперь все отрезки пути найдены, соединяем их и вычисляем итоговую стоимость пути с помощью начальной матрицы длин дуг. Имеем следующий минимальный путь: v 4 v 2 v 3 v 1 v 4 , его стоимость: 6 + 8 + 7 + 9 = 30. Найденный путь коммивояжера является оптимальным, потому что значения оценочной функции на всех оборванных ветках (на границах) больше стоимости этого пути. Возможно, что оптимальный контур будет не единственным. При ином варианте выборов по ходу разбиений можно было получить и другой оптимальный путь коммивояжера, однако стоимость этих путей будет одинакова. |