Минимальный путь в нагруженном орграфе

1) Найти минимальный путь в нагруженном орграфе из вершины в вершину по алгоритму Форда–Беллмана.

Рассмотрим сначала общую задачу – нахождения минимального пути из вершины v_нач в v_кон.

Пусть D = (V,X) – нагруженный орграф, V = {v₁,…,v_n}, n > 1. Введем величины , где i = 1,…,n, k = 0,1,2,…,n – 1.

Для каждого фиксированного i и k величина равна длине минимального пути среди путей из v_нач в v_i, содержащих не более k дуг. Если путей нет, то .

Положим также .

Составляем матрицу длин дуг C(D) = [c_ij] порядка n:

& Утверждение 8

При i = 2,…,n, k  0 выполняется равенство

Алгоритм Форда–Беллмана

записываем в виде матрицы, i – строка, k – столбец.

1. Составляем таблицу , i = 1,…,n, k = 0,…,n – 1. Если , то пути из v_нач в v_кон нет. Конец алгоритма.

2. Если то это число выражает длину любого минимального пути из v_нач в v_кон. Найдем минимальное k₁  1, при котором . По определению получим, что k₁ – минимальное число дуг в пути среди всех минимальных путей из v_начв v_кон.

3. Затем определяем номера i₂,…, такие, что

т.е. восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из v_нач в v_кон.

Заметим, что алгоритм Форда–Беллмана позволяет найти минимальные пути из заданной вершины во все остальные.

Пример

v Найдем минимальный путь из вершины v₂ в v₆ в нагруженном орграфе D (рис.2.84). n = 7, следовательно, матрица длин дуг графа D будет иметь размерность 7×7.

Рис. 2.84. Пример нагруженного орграфа для алгоритма Форда–Беллмана

Матрица длин дуг для данного графа:

Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v₂ в вершину v_i не более чем за k шагов, k = 0,…n – 1 (n = 7, следовательно, k = 0,…6).

Как было определено выше, , и для всех остальных вершин v_i ≠ v₂, т.е. первый столбец таблицы состоит из элементов, равных , кроме элемента .

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

В конечном итоге получаем следующую таблицу:

Теперь необходимо по построенной таблице и по матрице C(D) восстановить минимальный путь из вершины v₂ в v₆, который будет строиться с конца, т.е., начиная с вершины v₆. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v₆ в таблице. Это число 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4.

В вершину v₆ можно попасть за один шаг из вершин v₁ и v₇ (длины соответствующих дуг 8 и 5, соответственно, – данные из матрицы C(D)). Выбираем минимальную по длине из этих дуг. Далее, в вершину v₇ можно попасть из v₄ и v₅ (длины соответствующих дуг 7 и 3, соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v₂ в v₆:

v₂ v₃ v₅ v₇ v₆.

2) Найти все минимальные пути из вершины нагруженного орграфа по алгоритму Дейкстры.

Алгоритм Дейкстры в отличие от алгоритма Форда–Беллмана не допускает ребра с отрицательным весом и также решает задачу о кратчайших путях из одной вершины v_нач во все оставшиеся для нагруженного орграфа D = (V,X), V = {v₁,…,v_n}, n > 1. Пусть в общем случае необходимо определить минимальный путь из v_нач в v_z.

Алгоритм Дейкстры

1. Каждой вершине из множества V в ходе реализации алгоритма присваивается число d(v_i), равное длине кратчайшего пути из вершины v_нач в вершину v_i и включающем только пройденные вершины. Полагается d(v_нач) = 0 и d(v_i) = ∞ для всех остальных вершин графа. Проходится вершина v_нач и полагается v_j = v_нач, где v_j – последняя пройденная вершина.

2. Для каждой непройденной вершины v_i пересчитывается величина d(v_i) по формуле:

d (v_i) = min{d(v_i); d(v_j) + }.

3. Если d(v_i) = ∞ для всех непройденных вершин, то алгоритм заканчивается, так как отсутствуют пути из вершины v_нач в непройденные вершины. Иначе обозначается пройденной та вершина, для которой величина d (v_i) является минимальной. Обозначается и дуга, инцидентная этой вершине, в соответствии с формулой шага 2, и полагается v_j = v_i.

4. Если v_j = v_z, кратчайший путь из v_нач в v_z найден. Иначе переходим к шагу 2.

Пример

v Найдем все минимальные пути из вершины v₂ в нагруженном орграфе D (рис.2.85).

Рис. 2.85. Пример нагруженного орграфа для алгоритма Дейкстры

В графе 7 вершин, следовательно, матрица длин дуг будет подобна предыдущему случаю:

Согласно алгоритму зададим начальные условия: d(v₂) = 0, d(v_i) = ∞. Проходим вершину v₂, v_j = v₂. Находим ближайшую вершину к пройденной, используя формулу:

d (v_i) = min { d (v_i); d (v_j) + l(v_j, v_i)}:

d(v₁) = min{d(v₁); d(v₂) + l(v₂, v₁)} = min{∞; 0 + 1} = 1;

d(v₃) = min{d(v₃); d(v₂) + l(v₂, v₃)} = min{∞; 0 + 12} = 12;

d(v₄) = min{d(v₄); d(v₂) + l(v₂, v₄)} = min{∞; 0 + ∞} = ∞;

d(v₅) = min{d(v₅); d(v₂) + l(v₂, v₅)} = min{∞; 0 + ∞} = ∞;

d(v₆) = min{d(v₆); d(v₂) + l(v₂, v₆)} = min{∞; 0 + ∞} = ∞;

d (v₇) = min { d (v₇); d(v₂) + l(v₂, v₇)} = min{∞; 0 + ∞} = ∞.

Минимальную длину имеет путь от вершины v₂ до вершины v₁ d(v₁) = 1. Включаем вершину v₁ в текущее ориентированное дерево, а так же дугу, инцидентную этой вершине. Согласно выражению это дуга (v₂,v₁). Далее повторяем процедуру, исключая вершину v₁, теперь v_j = v₁.

d(v₃) = min{d(v₃); d(v₁) + l(v₁, v₃)} = min{12; 1 + 12} = 12;

d(v₄) = min{d(v₄); d(v₁) + l(v₁, v₄)} = min{∞; 1 + ∞} = ∞;

d(v₅) = min{d(v₅); d(v₁) + l(v₁, v₅)} = min{∞; 1 + 11} = 12;

d(v₆) = min{d(v₆); d(v₁) + l(v₁, v₆)} = min{∞; 1 + 8} = 9;

d (v₇) = min { d (v₇); d(v₁) + l(v₁, v₇)} = min{∞; 1 + ∞} = ∞.

Минимальную длину имеет путь от вершины v₁ до вершины v₆ d(v₆) = 9. Включаем вершину v₆ в текущее ориентированное дерево, а так же дугу (v₁,v₆), инцидентную этой вершине. Далее повторяем процедуру, исключая вершину v₆, теперь v_j = v₆.

d(v₃) = min{d(v₃); d(v₆) + l(v₆, v₃)} = min{12; 9 + ∞} = 12;

d(v₄) = min{d(v₄); d(v₆) + l(v₆, v₄)} = min{∞; 9 + ∞} = ∞;

d(v₅) = min{d(v₅); d(v₆) + l(v₆, v₅)} = min{12; 9 + 2} = 11;

d (v₇) = min { d (v₇); d(v₆) + l(v₆, v₇)} = min{∞; 9 + ∞} = ∞.

Подобным образом получаем, что v_j = v₅, d(v₅) = 11.

d(v₃) = min{d(v₃); d(v₅) + l(v₅, v₃)} = min{12; 11 + 2} = 12;

d(v₄) = min{d(v₄); d(v₅) + l(v₅, v₄)} = min{∞; 11 + ∞} = ∞;

d (v₇) = min { d (v₇); d(v₅) + l(v₅, v₇)} = min{∞; 11 + 3} = 14.

Теперь v_j = v₃, d(v₃) = 12.

d(v₄) = min{d(v₄); d(v₃) + l(v₃, v₄)} = min{∞; 12 + 6} = 18;

d (v₇) = min { d (v₇); d(v₃) + l(v₃, v₇)} = min{14; 12 + 3} = 14.

Далее v_j = v₇, d(v₇) = 14.

d(v₄) = min{d(v₄); d(v₇) + l(v₇, v₄)} = min{18; 14 + ∞} = 18.

И последнее v_j= v₄, d(v₄) = 18.

Мы получили ориентированное дерево кратчайших путей начинающихся в вершине v₂ для исходного графа (рис.2.86)

d(v₁) = 1, путь v₂v₁;

d(v₂) = 0, путь v₂;

d(v₃) = 12, путь v₂v₃;

d(v₄) = 18, путь v₂v₃v₄;

d(v₅) = 11, путь v₂v₁v₆v₅;

d(v₆) = 9, путь v₂v₁v₆;

d (v₇) = 14, путь v₂v₁v₆v₅v₇.

Рис. 2.86. Ориентированное дерево кратчайших путей из вершины v₂

Вариант алгоритма Дейкстры

Рассмотрим другой вариант представления и реализации алгоритма Дейкстры.

Пусть l(v _i) пометка вершины v _i; - начальная (базовая) вершина.

1. Положим l(p) = 0. Далее будем считать эту пометку постоянной. Для всех остальных вершин пометка l(v _i) , считаем эти пометки временными.

2. Обновление пометок. Для всех вершин из образа вершины p (вершин, в которые можно попасть непосредственно из p), не имеющих постоянной пометки, , где - вес дуги из p в v _i.

3. Найдем с минимальной временной пометкой, обозначим ее как , пометка становится постоянной (при этом есть длина кратчайшего пути из v в ).

4. Если вершина p совпадает с конечной вершиной (если требуется найти путь из v в w) или пометки всех вершин постоянные, то работа алгоритма завершена. Иначе возврат к шагу 2.

Пример

v Пусть дан нагруженный орграф с матрицей длин дуг С(D). Необходимо найти минимальный путь из v₁ в v₉, используя алгоритм Дейкстры.

1. Метка вершины v₁ постоянна, равна 0.

2. Из вершины v₁ можно попасть в вершины v₃ (за 1) и v₆ (за 7), т. е. теперь временные метки вершин v₃ и v₆ становятся равными 1 и 7 соответственно:

v₁	v₂	v₃	v₄	v₅	v₆	v₇	v₈	v₉
0	¥	¥	¥	¥	¥	¥	¥	¥
õ	¥	1	¥	¥	7	¥	¥	¥

3. Минимальная из временных пометок – 1, поэтому v₃ принимает статус начальной и ее метка становится постоянной. Снова меняем метки оставшихся вершин. Из v₃ можно попасть в v₁ (нам туда не надо) и v₆ (за 4), тогда метка v₆ будет равна .

v₁	v₂	v₃	v₄	v₅	v₆	v₇	v₈	v₉
0	¥	¥	¥	¥	¥	¥	¥	¥
õ	¥	1	¥	¥	7	¥	¥	¥
õ	¥	õ	¥	¥	5	¥	¥	¥

4. Поскольку в последней строке одна временная метка , то она автоматически становится постоянной. Продолжаем процесс:

	v₁	v₂	v₃	v₄	v₅	v₆	v₇	v₈	v₉
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₁ в v₉ имеет вес 27. Восстановим этот путь, начиная с конца. По столбцу v₉ поднимаемся до строки, в которой получено конечное значение (7 шаг). В тот момент времени роль вершины с постоянной меткой играла v₈. В столбце v₈ число 12 появляется на 5 шаге, чему соответствует v₂. Продолжая, доберемся до v₁. Восстановленный путь:

v₁® v₃® v₆® v₂® v₈® v₉ (общий вес = 1 + 4 + 2 + 5 + 15 = 27).

2.7.7. Метод ветвей и границ

Метод ветвей и границ(англ. branch and bound) – общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации. Метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Общая идея метода может быть описана на примере поиска минимума функции f(x) на множестве допустимых значений переменной x. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной x.

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

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

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

Одна из самых известных и важных задач теории графов, представляющая собой целый класс задач оптимизации – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается под названием «задача о бродячем торговце». Суть задачи сводится к поиску пути наименьшей стоимости, проходящего через все вершины графа по одному разу, с возвратом в конце в исходную вершину. Решим задачу методом ветвей и границ.

Введем следующие обозначения: пусть D = (V, X) – полный орграф и f: X ® R – весовая функция, V = {v₁,v₂,…,v_n} – множество вершин, X – множество дуг, C = {c_ij}, i, j = 1,2…n – матрица длин дуг данного орграфа, т. е. с _ij = f(v _i,v_j), причем для любого i справедливо c_ii = ¥. Требуется найти простой остовной контур (или контур коммивояжера) минимального веса.

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

Очевидно, что вычитая любую константу из всех элементов любой строки или столбца матрицы C, минимальный путь останется минимальным.

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

Привести матрицу по строкам означает, что все строки приводятся. Аналогичный смысл имеет фраза «привести матрицу по столбцам». Приведение матрицы означает сначала приведение этой матрицы по строкам, а затем по столбцам.

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

Весом элемента матрицы называют сумму констант приведения матрицы. Следовательно, слова «самый тяжелый нуль в матрице» означают, что в матрице подсчитан вес каждого нулевого элемента, и зафиксирован нуль с максимальным весом.

Пример

v Пусть дан нагруженный орграф с матрицей длин дуг С(D).

Найдем константу приведения в каждой строке и выпишем ее в отдельный столбец min r.

	v₁	v₂	v₃	v₄	min r
v₁	¥	5	11	9	5
v₂	10	¥	8	7	7
v₃	7	14	¥	8	7
v₄	12	6	15	¥	6

Из каждого элемента в строке вычитаем соответствующее значение константы приведения (min r).

	v₁	v₂	v₃	v₄	min r
v₁	¥	0	6	4	5
v₂	3	¥	1	0	7
v₃	0	7	¥	1	7
v₄	6	0	9	¥	6

В итоге в каждой строке будет хотя бы одно нулевое значение.

Далее повторяем процедуру для каждого столбца и выписываем константы приведения в отдельную строку min c.

	v₁	v₂	v₃	v₄	min r
v₁	¥	0	6	4	5
v₂	3	¥	1	0	7
v₃	0	7	¥	1	7
v₄	6	0	9	¥	6
min c	0	0	1	0

Вычитаем из каждого элемента матрицы соответствующее ему min c. В итоге и в каждом столбце будет хотя бы одно нулевое значение.

	v₁	v₂	v₃	v₄	min r
v₁	¥	0	5	4	5
v₂	3	¥	0	0	7
v₃	0	7	¥	1	7
v₄	6	0	8	¥	6
min c	0	0	1	0

Обозначим за Г множество всех обходов коммивояжера (т. е. всех простых ориентированных остовных контуров). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число j(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы длин дуг графа и является оценкой снизу для стоимости минимального пути коммивояжера. Начальную матрицу длин дуг данного графа обозначим через С₁.

Подсчитаем j(Г) = 5 + 7 + 7 + 6 + 1 = 26. Таким образом, нижняя оценка искомого пути найдена: . Для получения верхней оценки выберем один из существующих в графе гамильтоновых контуров и его стоимость возьмем за максимально возможную. Построим этот контур, пользуясь принципом «ближайшего соседа» (начинаем с произвольной вершины, например, с v₃, ищем дугу минимального веса из нее, это дуга в вершину v₁, и т. д., исключая переходы в уже пройденные вершины, только на последнем, четвертом шаге возвращаемся в v₃):

v₃v₁v₂v₄v₃, .

Окончательно определенные границы для оптимального пути: .

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

	v₁	v₂	v₃	v₄
v₁	¥	0 (4)	5	4
v₂	3	¥	0 (5)	0 (1)
v₃	0 (4)	7	¥	1
v₄	6	0 (6)	8	¥

Далее выбираем нулевое значение с наибольшим весом. Это значение 6 в ячейке v₄v₂. Разобьем множество Г на две части: множество (все контуры, проходящие через дугу v₄v₂) и (все контуры, не проходящие через дугу v₄v₂). Такое ветвление определяет необходимость выбора одного из этих вариантов.

Множеству соответствует матрица С_1,1, полученная вычеркиванием соответствующих строки (v₄) и столбца (v₂). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычеркиванием строки и столбца, в матрице надо заменить на ¥ числа в определенных ячейках так, чтобы исключить возврат в уже пройденные вершины, т. е. чтобы не получалось коротких контуров длиной меньше n. В данном случае из v₂ уже нельзя попасть в v₄, поэтому в ячейке v₂v₄ ставим ¥. Найденные веса нулей удаляются.

	v₁	v₃	v₄
v₁	¥	5	4
v₂	3	0	¥
v₃	0	¥	1

После приведения матрица С_1,1 (приводим только строку v₁ с константой приведения 4).

	v₁	v₃	v₄
v₁	¥	1	0
v₂	3	0	¥
v₃	0	¥	1

Сумма констант приведения матрицы С_1,1 здесь равна 4, поэтому j(Г_{(4,2)}) = j_{4,2} = 26 + 4 = 30.

Множеству , в свою очередь, соответствует другая матрица – С_1,2, полученная заменой на ¥ элемент с_4,2 в матрице С₁:

	v₁	v₂	v₃	v₄
v₁	¥	0	5	4
v₂	3	¥	0	0
v₃	0	7	¥	1
v₄	6	¥	8	¥

Сумма констант последнего приведения равна весу замененного нуля, т. е. 6, так что .

Теперь выберем между множествами и то, на котором минимальна функция j. Поэтому дальнейшей разработке подвергнется множество Г_{(4,2)}.

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

В матрице С_1,1 вычислим веса нулевых ячеек:

	v₁	v₃	v₄
v₁	¥	1	0 (2)
v₂	3	0 (4)	¥
v₃	0 (4)	¥	1

Выбираем нулевое значение с наибольшим весом. В данном случае это 4 и таких значений два, выбирается любое из них, пусть это будет ячейка v₂v₃. Теперь следует рассматривать множества и . Ясно, что .

Вычеркнем строку v₂ и столбец v₃ в матрице С_1,1 и избавимся от короткого цикла, заменив 1 в ячейке v₃v₄ на ¥. Получим матрицу С_1,1,1, которая после приведения будет следующей:

	v₁	v₄
v₁	¥	0
v₃	0	¥

При этом , следовательно, в дальнейшем разрабатываем . Таким образом найдена вторая дуга пути: v₂v₃.

Приведем матрицу С_1,1,1 и подсчитаем веса нулевых ячеек.

	v₁	v₄
v₁	¥	0 (¥)
v₃	0 ( ¥ )	¥

Выбираем одно из нулевых значений с весом ¥: v₃v₁. При этом , . Таким образом найдена третья дуга пути: v₃v₁. Строку v₃ и столбец v₁ вычеркиваем.

	v₄
v₁	0

Очевидно, что оставшаяся последняя дуга оптимального пути – это v₁v₄. Теперь все отрезки пути найдены, соединяем их и вычисляем итоговую стоимость пути с помощью начальной матрицы длин дуг.

Имеем следующий минимальный путь: v₄v₂v₃v₁v₄, его стоимость: 6 + 8 + 7 + 9 = 30.

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

Эйлеровы циклы и цепи

Найти Эйлерову цепь в неориентированном псевдографе.

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

Дата добавления: 2021-02-10; просмотров: 719; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 6 7 8 9 10 11 121314 15 Следующая ⇒

Мы поможем в написании ваших работ!