ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с

• Название: В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
• Дата: 12.09.2022
• Размер: 4.33 Mb.
• Имя файла: ДИСКРЕТНАЯ МАТЕМАТИКА (1).pdf
• Тип: Реферат; #673155
• страница: 17 из 25

4.13. Кратчайший путь в орграфе Рассмотрим задачу на графе. Дан взвешенный орграф (взвешены дуги, веса дуг положительные) и две его вершины — S и F. Длиной пути от вершины S до вершины F называется сумма весов всех дуг, принадлежащих этому пути. Требуется найти в орграфе путь от вершины S до вершины F минимальной длины, те. путь, длина которого не больше любого другого пути от вершины S до вершины F. Путь минимальной длины будем также называть кратчайшим, а длину этого пути — кратчайшим или минимальным расстоянием от начальной вершины пути до конечной. Многие реальные задачи сводятся к рассматриваемой задаче на графе естественным образом. Например, дано множество населенных пунктов, между некоторыми из них проложены автомобильные дороги с одно- или двусторонним движением. Известны длины дорог, соединяющих населенные пункты. Требуется найти путь минимальной длины от населенного пункта А до пункта В. Для того чтобы эту задачу свести к задаче на графе, построим граф, в котором вершины соответствуют населенным пунктам, а дуги — парам населенных пунктов, между которыми проложены дороги, направление дуги определяется направлением разрешенного движения по соответствующей дороге. Вес дуги определяется длиной соответствующей ей дороги. Сведение же других реальных задач к рассматриваемой задаче на графе не так уж очевидно. Предположим, что вам необходимо иметь в своем распоряжении автомобиль в течение нескольких лет. Имеется большой выбор автомобилей. Автомобили имеют различные сроки эксплуатации и разную стоимость. Каким образом на заданном временном интервале выбрать вариант покупок автомобилей, имеющий минимальную суммарную стоимость покупаемых автомобилей Для того, чтобы свести данную задачу к задаче на графе, представим моменты времени возможных сделок на заданном временном интервале, связанные с покупкой автомобиля, вершинами некоторого графа. Для упрощения в качестве моментов времени сделок можно рассматривать лишь первые дни каждого месяца, квартала или другого временного отрезка. Изобразим в данном графе факт приобретения автомобиля дугой, соединяющей вершину, соответствующую моменту покупки, сверши- ной, соответствующей моменту окончания срока службы автомобиля. Длина каждой дуги построенного графа совпадает со стоимостью соответствующей сделки. Чтобы выбрать вариант с минимальной суммарной стоимостью, необходимо среди всех возможных путей из вершины, соответствующей начальному моменту времени, в вершину, соответствующую конечному моменту времени, найти кратчайший путь. Задачу отыскания кратчайшего пути во взвешенном орграфе от вершины до вершины F можно решить различными способами.
1. Кратчайший путь от вершины S до вершины F представляет собой простую цепь (любой другой путь, содержащий в себе цикл, будет иметь большую длину, поэтому для отыскания кратчайшего пути достаточно выполнить полный перебор простых цепей от вершины S до вершины F и выбрать цепь минимальной длины. Для этого введем в алгоритм 4.3 нахождения простых цепей методом поиска с возвращением дополнения, позволяющие выбрать цепь минимальной длины. Цепь W представлена последовательностью вершин с вершиной S на первом месте. В процессе формирования цепи будем вычислять ее длину L. Если в цепь из i — 1 вершин длины L добавить ю вершину x, то получим цепь из i вершин длины L’ = L + длина_дуги(W
i–1
,x). Будем использовать переменную для хранения длины пути, принятого за минимальный, а переменную Wmin — для хранения этого пути. Инициализируем Lmin бесконечно большим числом. После нахождения очередной цепи W от вершины S до вершины F сравним ее длину L си, если окажется, что L меньше Lmin, запомним цепь W в переменной Wmin, а ее длину
L — в Lmin. Алгоритм 4.12 (рис) поиска кратчайшего пути от вершины S до вершины F во взвешенном орграфе G. Вход i — заполняемое место вцепи множество вершин, включенных в цепь
L — длина цепи.

195 Выход Wmin — кратчайший путь от вершины S до вершины F;
Lmin — длина кратчайшего пути.
Глобальные параметры Wmin, Lmin.
+
+ Рис. Алгоритм поиска кратчайшего пути от вершины S до вершины F
2. Для сокращения количества анализируемых простых цепей воспользуемся идеей метода ветвей и границ. Этот метод позволяет сократить число анализируемых решений, когда требуется выбрать из множества всех решений наилучшее, обладающее заданным свойством. В нашем случае множество всех решений — это множество всех простых цепей от вершины S до вершины F, а наилучшее — кратчайший путь. В методе ветвей и границ решение представляет собой ветвь, получение решения — построение ветви. Если на некотором шаге построения ветви станет ясно, что продолжение построения ветви не даст наилучшего решения, тона этом шаге получения решения ветвь ограничивается, выполняется шаг назад и делается попытка построить Путь (i,V’,L) Г
:= x
x=F Конец Путь (i+1,
V’

{x},L’
)
L’
:=L+
длина_дуги(W
i–1
,x)
L’
Wmin
:=W
Lmin:=L’

196 ветвь в другом направлении. Пусть Lmin — длина пути от вершины S до вершины F, принятого за минимальный. Если на некотором шаге добавление дуги (W
i–1
,x) дает цепь, длина которой L’

Lmin, то дальнейшее построение этой цепи прекращается и выполняется шаг назад. Алгоритм 4.13 (рис) поиска кратчайшего пути от вершины S до вершины F во взвешенном орграфе G на основе метода ветвей и границ. Вход i — заполняемое место вцепи множество вершин, включенных в цепь
L — длина цепи. Выход Wmin — кратчайший путь от вершины S до вершины F;
Lmin — длина кратчайшего пути.
Глобальные параметры Wmin, Lmin.
+
+ Рис. Алгоритм поиска кратчайшего пути от вершины S до вершины F на основе метода ветвей и границ Путь (i,V’,L) Г
:= x
x=F Конец Путь (i+1,
V’

{x},L’
)
L’
:=L+
длина_дуги(W
i–1
,x)
L’
Wmin
:=W
Lmin:=L’

197 3. Один из эффективных алгоритмов нахождения кратчайшего пути во взвешенном орграфе между двумя вершинами, при условии, что все дуги орграфа имеют положительный вес, предложил в 1959 г. Едсгер
Дейкстра. В алгоритме Дейкстры множество вершин V орграфа разбивается на два непересекающихся подмножества — V’ и V”, таких, что V’

V” = V. Множество V’ содержит вершины орграфа, до которых найдено кратчайшее расстояние (и кратчайший путь) из исходной вершины S, а множество вершины орграфа, до которых еще не найдено кратчайшее расстояние (и кратчайший путь) из исходной вершины S. Вершины, принадлежащие множеству V’, будем называть отмеченными. Каждой вершине x
i

V орграфа приписывается число d(x
i
), которое служит оценкой длины кратчайшего пути от вершины S к вершине x
i
. Если вершине приписано число d(x
i
), то это означает, что в орграфе существует путь изв, имеющий длину d(x
i
). Если вершина x
i

V’, то это означает, что d(x
i
) — кратчайшее расстояние от вершины S к вершине x
i
и кратчайший путь от вершины S к вершине x
i найден. На каждом шаге алгоритма числа d(x
i
) для вершин из множества V” пересчитываются, и среди всех вершин x
i

V” выбирается вершина x
i
, к которой приписано минимальное число d(x
i
). До этой вершины кратчайшее расстояние (и кратчайший путь) на этом шаге найдено, она исключается из множества V” (V” := V” – {x
i
}) и заносится в множество V’
(V’ := V’

{x
i
}). Алгоритм заканчивает работу, если на очередном шаге найдено кратчайшее расстояние (и путь) до конечной вершины F или если нельзя выбрать вершину с минимальным числом (ко всем вершинам из множества V” приписано бесконечно большое число, в этом случае пути от вершины S ко всем вершинам из множества V” не существует. Алгоритм Дейкстры. Вход взвешенный орграф
S — начальная вершина пути
F — конечная вершина пути Выход кратчайший путь изв и его длина d(F).
1. Начальная установка.
V’ := {S}, V” := V – {S}, d(S):= 0,

x
i

V”, d(x
i
) :=

,
y := S (y — последняя вершина, до которой найден кратчайший путь.
2. Пересчет чисел d(x
i
).

x
i

Г)

V” пересчитать d(x
i
):
d(x
i
) := min(d(x
i
), d(y) + длина_дуги(y,x
i
)).

198 Если величина d(x
i
) изменилась (уменьшилась, то это означает, что кратчайший путь в вершину x
i
, вероятно, содержит дугу
(y,x
i
), поэтому ее нужно запомнить как претендента на включение в кратчайший путь.
3. Поиск вершины x
i
, до которой найден кратчайший путь. Из всех вершин x
i

выбрать вершину x
j
c наименьшим значением. Если d(x
j
) =

, то пути от вершины S ко всем вершинам из множества V” не существует, иначе y := x
j
, V’ := V’

{y},
V” := V” – {y}, отметить дугу претендента, ведущую в вершину y.
4. Проверка на завершение. Если y = F , то конец алгоритма, кратчайший путь изв найден, его длина d(y). Если d(x
j
) =

, то пути изв нет, конец алгоритма. Иначе перейти к п . В каждую вершину из множества V’, за исключением вершины S, входит только одна отмеченная дуга. Отмеченные дуги не могут образовывать в исходном графе цикл, так как в алгоритме не может отмечаться дуга, конец которой принадлежит множеству V’. Следовательно, отмеченные дуги образуют в исходном графе ориентированное дерево скор- нем в вершине S. Такое дерево называется деревом кратчайших путей . Из дуг (необязательно из всех) дерева, складывается кратчайший путь изв. В дереве кратчайших путей только одна дуга входит в вершину F. Пусть это будет дуга (x
i
, F). Далее, только одна дуга входит в вершину x
i
и т.д. Таким образом, поднимаясь к корню, восстанавливается кратчайший путь изв (в обратном порядке. При программной реализации алгоритма Дейкстры числа d(x
i
) целесообразно хранить в массиве D, й элемент которого соответствует вершине x
i
, а его значение D
i
— числу d(x
i
). Для хранения дерева кратчайших путей можно использовать массив T, й элемент которого соответствует вершине x
i
, а его значение T
i
— вершине x
j
, предшествующей вершине x
i
на кратчайшем пути изв, таким образом пара (T
i
,i) соответствует дуге дерева кратчайших путей. Значение Т равно нулю, так как в вершину S не входит ни одна дуга дерева, она является корнем. На первом шаге алгоритма, при начальной установке, необходимо элементу
T
s
присвоить ноль, остальным — неопределенность (например, минус один. На втором шаге, если величина d(x
i
) изменилась (уменьшилась, то элементу T
i
нужно присвоить значение y, что соответствует запоминанию дуги (y,x
i
) как претендента на включение в кратчайший путь. Для хранения множеств V’ и V” можно использовать бинарный массив V, в котором й элемент соответствует вершине x
i
, V
i
= 1, если x
i

и
V
i
= 0, если x
i

V”.

199 Работу алгоритма Дейкстры при поиске кратчайшего пути от вершины до вершины v
5
во взвешенном орграфе, диаграмма которого изображена на рис, представим в табл. 4.5, отображающей изменения значений массивов V, D и T на каждом шаге выполнения алгоритма.
v
2 2 v
4 12
v
1
v
6 748 95 4
1
v
3
v
5
Рис. Диаграмма орграфа Таблица 4.5 Работа алгоритма Дейкстры Номер шага Пункт алгоритма Состояние массивов V,D и T Вершина y
1 2
3 4
1 1
V=(1, 0, 0, 0, 0, 0)
D=(0,

,

,

,

,

)
T=(0,-1,-1,-1,-1,-1)
1 2
2
V=(1, 0, 0, 0, 0, 0)
D=(0,
1
, 9,

,

,

)
T=(0, 1, 1,-1,-1,-1)
1 3
3
V=(1, 1, 0, 0, 0, 0)
D=(0,
1
, 9,

,

,

)
T=(0, 1, 1,-1,-1,-1)
2 4
4 2≠5, продолжить
2 5
2
V=(1, 1, 0, 0, 0, 0)
D=(0,
1
, 8, 3,

,

)
T=(0, 1, 2, 2,-1,-1)
2 6
3
V=(1, 1, 0, 1, 0, 0)
D=(0,
1
, 8, 3,

,

)
T=(0, 1, 2, 2,-1,-1)
4 7
4 4≠5, продолжить
4 8
2
V=(1, 1, 0, 1, 0, 0)
D=(0,
1
, 7, 3,
11
, 5)
T=(0, 1, 4, 2, 4, 4)
4

200 Окончание табл
1 2
3 4
9 3
V=(1, 1, 0, 1, 0, 1)
D=(0,
1
, 7, 3,
11
, 5)
T=(0, 1, 4, 2, 4, 4)
6 10 4
6≠5, продолжить
6 11 2
V=(1, 1, 0, 1, 0, 1)
D=(0,
1
, 7, 3,
9
, 5)
T=(0, 1, 4, 2, 5, 4)
6 12 3
V=(1, 1, 1, 1, 0, 1)
D=(0,
1
, 7, 3,
9
, 5)
T=(0, 1, 4, 2, 5, 4)
3 13 4
3≠5, продолжить
3 14 2
V=(1, 1, 1, 1, 0, 1)
D=(0,
1
, 7, 3,
8
, 5)
T=(0, 1, 4, 2, 3, 4)
3 15 3
V=(1, 1, 1, 1, 1, 1)
D=(0,
1
, 7, 3,
8
, 5)
T=(0, 1, 4, 2, 3, 4)
5 16 4
5=5, конец
5 В результате выполнения алгоритма Дейкстры при поиске кратчайшего пути от вершины v
1 до вершины v
5
построено дерево кратчайших путей (рис) с корнем v
1
. Дерево кратчайших путей покрывает все вершины орграфа и определяет кратчайшие пути от вершины v
1 не только до вершины v
5
, но и до всех остальных вершин орграфа. Длина кратчайшего пути от вершины до вершины v
i
указана в скобках рядом с вершиной v
i
на рис.
v
2
(1)
2 v
4
(3)
12
v
1
(0) v
6
(5)
4 1
v
3
(7)
v
5
(8) Рис. Дерево кратчайших путей

201
4.14. Кратчайшие пути между каждой парой вершин в орграфе Кратчайшие пути и их длины между каждой парой вершин во взвешенном орграфе будем хранить в матрице W, в которой элемент W
ij
состоит из двух частей
W
ij
.d — длина кратчайшего пути от вершины i до вершины j;
W
ij
.t — вершина, предшествующая вершине j на кратчайшем пути от вершины i до вершины j. Сформировать матрицу W по матрице весов M взвешенного орграфа можно различными способами.
1. Для нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе применим алгоритм Дейкстры. В алгоритме
Дейкстры (см. выше) изменим п
4. Проверка на завершение. Если V’ = V или d(x
j
) =

, то конец алгоритма, иначе перейти к п. В результате такого изменения после выполнения алгоритма получим кратчайшие пути (массив T) и их длины (массив D) от исходной вершины до всех достижимых из нее вершин орграфа. Теперь матрицу W можно получить следующим образом
1. Для всех i от 1 до |V| выполнить п.
2. Сформировать ю строку матрицы W:
2.1. Выполнить алгоритм Дейкстры, считая вершину i исходной.
2.2. Для всех j от 1 до |V| выполнить W
ij
.d := D
j
, W
ij
.t := T
j
.
2. Метод Шимбелла. Матрица весов M взвешенного орграфа определяет длины кратчайших путей между каждой парой вершин орграфа, состоящих из одной дуги. Для того чтобы получить матрицу длин кратчайших путей между каждой парой вершин орграфа, состоящих из двух дуг, возведем матрицу в квадратно при этом заменим операцию умножения (a

b) операцией сложения (a + b), аоперацию сложения (a + b) — выбором минимального элемента (min(a, b)). Матрица будет содержать длины кратчайших путей, состоящих из k дуг. Матрица M + M
2
+ …+ содержит длины кратчайших путей, состоящих не более чем из k дуг здесь операция сложения также заменена выбором минимального элемента. Учитывая, что кратчайший путь может содержать не более чем
n – 1 дуг, где n — количество вершин в орграфе, длины кратчайших путей между каждой парой вершин орграфа можно вычислить по формуле, если a.d < b.d;
b, иначе.
Чтобы найти не только длины кратчайших путей между каждой парой вершин орграфа, но и сами пути, модифицируем матрицу весов M: примем, что элемент M
ij
состоит из двух частей
M
ij
.d — длина дуги из вершины i в вершину j;
i, если есть дуга из вершины i в вершину j;
M
ij
.t = 0, если i = j;
–1, если нет дуги из вершины i в вершину Матрицу W кратчайших путей и их длин между каждой парой вершин орграфа можно вычислить по формуле
W = M + M
2
+ …+ M
n–1
, при этом результатом операции умножения величин a и b будет величина, которая определяется c.d = a.d + b.d,
c.t = b.t; а результатом операции сложения величин a и b будет величина c, которая определяется
c =