Главная Учебники - Разные Лекции (разные) - часть 21
по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Вариант №22
Содержание курсовой работы
Пояснительная записка к курсовой работе должна содержать следующие разделы: · постановка задачи; · теоретическая часть; · описание алгоритма решения поставленной задачи; · ручной просчет (на небольшом примере показать работу алгоритма); · описание программы; · тесты; · список использованной литературы; · листинг программы. ЗАДАНИЯ К КУРСОВОЙ РАБОТЕ
Раздел 1. Некоторые базисные алгоритмы обработки графов 1.1. Нахождение минимального пути в графе Путь в орграфе D
из вершины v
в вершину w
, где v
¹ w
, называется минимальным
, если он имеет минимальную длину среди всех путей орграфа D
из v
в w
. Назовем орграф D
= (V
,X
) нагруженным
, если на множестве дуг X
определена некоторая функция l
: X
® R
, которую часто называют весовой функцией. Значение l
(x
) будем называть длиной дуги x
. Предположим, что l
(x
) ³ 0. Длиной пути П
в нагруженном орграфе будем называть величину l
(П
), равную сумме длин дуг, входящих в П
, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь. Нагруженный орграф можно задать с помощью матрицы весов С
(D
) = {cij
}nxn
с элементами cij
= ¥, если (vi
,
vj
) ÏX
. Рассмотрим алгоритм Дейкстры, который позволяет определить минимальный путь в орграфе между двумя заданными вершинами при условии, что этот путь существует. Пусть s
– начальная вершина,
t
– конечная вершина. На каждой итерации любая вершина v
имеет метку l
*
(v
), которая может быть постоянной или временной. Постоянная метка l
*
(v
) – это длина кратчайшего пути от s
к v
, временная метка l
(v
) – это вес кратчайшего пути из s
в v
, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма. Вторая метка Q(v
) – это вершина, из которой вершина v получила свою метку. А л г о р и т м Д е й к с т р ы Данные: матрица весов С
(D
) орграфа D
, начальная вершина s
. Результат: расстояния от вершины s
до всех вершин орграфа D
: D
[v
] = d(s,v),
v
Î V
, а также последовательность вершин, определяющая кратчайший путь из s
в v
. 1. Положим l
*
(s
) = 0 и будем считать эту метку постоянной. Для всех v
ÎV
, v
¹ s
, положим l
*
(v
) = ¥ и будем считать эти метки временными. Положим p
=
s
. 2. Для всех v
Î
Г
p
с временными метками выполним: если l
*
(
v
)>
l
*
(
p
)+
l
(
p
,
v
)
, то l
*
(
v
)=
l
*
(
p
)+
l
(
p
,
v
)
и Q(
v
) =р
. Иначе l
*
(
v
)
и Q(
v
)
не менять, т.е. l
*
(
v
) =
min
(
l
*
(
t
),
l
*
(
p
)+
cpv
).
(Идея состоит в следующем: пусть p
– вершина, получившая постоянную метку l
*
(
p
)
на предыдущей итерации. Просматриваем все вершины v
Î
Г
p
, имеющие временные метки. Метка l
*
(
v
)
вершины v
Î
Г
p
заменяется на l
*
(
p
)+
l
(
p
,
v
),
если оказывается, что ее метка l
*
(
v
)>
l
*
(
p
)+
l
(
p
,
v
).
В этом случае говорим, что вершина v
получила свою метку из вершины p
, поэтому положим Q(
v
) =
p
. С помощью этих дополнительных меток будем потом восстанавливать сам путь. Если l
*
(
v
)
£
l
*
(
p
)+
cpv
,
то метки остаются прежними. 3. Пусть V
* - множество вершин с временными метками. Найдем вершину v
* такую, что l
*
(
v
*) =
min
l
*
(
v
),
v
Î
V
*. Считать метку l
*
(
v
*)
постоянной для вершины v
*. 4. Положим p
=
v
*. Если p
=
t
, то перейдем к п.5 ( l
*
(
t
)
– длина минимального пути ). Иначе перейдем к п.2. 5. Найдем минимальный путь из s
в t
, используя метки Q(
v
):
П
= s
…
Q(
t
)
t
. Заметим, что, если продолжить работу алгоритма Дейкстры до тех пор, пока все вершины не получат постоянные метки, то мы получим расстояния от начальной вершины s
до произвольной вершины графа. Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s
и t
опираются на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг C
вычисляются некоторые верхние ограничения D
[v
] на расстояния от s
до всех вершин v
Î
V
. Каждый раз, когда мы устанавливаем, что D
[u
] + cuv
< D
[v
], оценку D
[v
] улучшаем: D
[v
] = D
[u
] +cuv
. Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Можно показать, что значение каждой из переменных D
[v
] равно тогда d
(
s
,
v
)
- расстоянию от s
до v
. Заметим, что для того, чтобы определить расстояние от s
до t
, мы вычисляем здесь расстояния от s
до всех вершин графа. Описанная общая схема является неполной, т.к. она не определяет очередности, в которой выбираются вершины u
и v
. Эта очередность оказывает сильное влияние на эффективность алгоритма. Опишем алгоритм Форда-Беллмана для нахождения расстояния от фиксированной точки s
до всех остальных вершин графа. Рассмотрим орграф D
= (V
,X
), где V
={v
1
,…,vn
}. А л г о р и т м Форда – Беллмана Данные: матрица весов С
(D
) орграфа D
, начальная вершина s
. Результат: расстояния от вершины s
до всех вершин орграфа D
: D
[v
] = d(s,v),
v
Î V
. 1. Всем вершинам v
Î
V
орграфа присвоим метку D
[v
] = csv
. Вершине s
присвоим метку D
[s
] = 0. 2. Положим k
=1. 3. Выберем произвольную вершину v
Î V
\ {s
}. 4. Выберем произвольную вершину u
ÎV
. 5. Положим D
[v
] = min
(
D
[v
], D
[u
] + cuv
).
6. Если вершина u
пробежала еще не все множество вершин V
, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5. 7. Если вершина v
пробежала еще не все множество вершин V
\ {s
}, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4. 8. Если k
<
n
-2, то положить k
=
k
+1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D
[v
] будут равны расстояниям d
(
s
,
v
)
в орграфе D
. Замечание.
Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины s
до вершины v
. Отметим, что закончить вычисления можно, когда выполнение цикла по k
не вызывает изменения ни одной из переменных D
[v
]. Пример. Определим минимальные пути из вершины v
1
до всех остальных вершин в нагруженном орграфе D
, изображенном на рис. 1. 12 v5
2 Рис.1. Ниже в таблице приведены матрица весов, а также все вычисления по шагам. v1
v2
v3
v4
v5
v6
D(0)
D(1)
D(2)
D(3)
D(4)
v1
¥ ¥ 5 5 2 12 0 0 0 0 0 v2
¥ ¥ ¥ ¥ ¥ 2 ¥ 7 5 5 5 v3
¥ 2 ¥ ¥ ¥ ¥ 5 3 3 3 3 v4
¥ 2 ¥ ¥ ¥ ¥ 5 4 4 4 4 v5
¥ ¥ 1 2 ¥ ¥ 2 2 2 2 2 v6
¥ ¥ ¥ ¥ ¥ ¥ 12 9 9 7 7 На первом шаге всем вершинам v
Î
V
орграфа присвоим метку D
[v
] = csv
, где s
= v
1
. Выберем следующую вершину v
2
. Ей присвоим метку D
[v
2
] = min
(
D
[v
2
], D
[u
] + cuv
)
, где u
ÎV
,
т.е. D
[v
2
] = min
(
D
[v
2
], D
[v
3
]+ c
32
, D
[v
4
]+ c
42
, D
[v
5
]+ c
52
, D
[v
6
]+ c
62
) = (
¥,
5+2, 5+2, 2+¥, 12+¥) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4. Аналогично корректируются метки всех оставшихся вершин, а именно, D
[v
3
] = min (D
[v
3
], D
[v
2
]+c
23
, D
[v
4
]+c
43
, D
[v
5
]+c
53
, D
[v
6
]+c
63
) = (
5,
7+¥, 5+¥, 2+1, 12+¥) = 3, D
[v
4
] = min (D
[v
4
], D
[v
2
]+c
24
, D
[v
3
]+c
34
, D
[v
5
]+c
54
, D
[v
6
]+c
64
) = (
5,
7+¥, 3+¥, 2+2, 12+¥) = 4, D
[v
5
] = min (D
[v
5
], D
[v
2
]+ c
25
, D
[v
3
]+ c
35
, D
[v
4
]+ c
45
, D
[v
6
]+ c
65
) = (
2,
7+¥, 3+¥, 4+¥, 12+¥) = 2, D
[v
6
] = min (D
[v
6
], D
[v
2
]+ c
26
, D
[v
3
]+ c
36
, D
[v
4
]+ c
46
, D
[v
5
]+ c
56
) = (
12,
7+2, 3+¥, 4+¥, 2+¥) = 9. Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k
=
n
-2 =
4. Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v
1
до всех остальных вершин. Например, длина минимального пути из v
1
в v
2
равна 5, сам путь имеет вид: v
1
v
5
v
3
v
2
. Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n
раз (поочередно для каждой вершины) один из описанных ранее алгоритмов. Однако оказывается, что n
-кратное использование этих алгоритмов не является наилучшим методом. Рассмотрим более эффективный алгоритм для решения поставленной задачи – алгоритм Флойда. Идея этого алгоритма следующая. Рассмотрим орграф D
= (V
,X
), где V
={v
1
,…,vn
}. Обозначим через dij
(
m
)
длину кратчайшего из путей из vi
в vj
с промежуточными вершинами из множества {v
1
,…,
vm
}. Тогда имеем следующие уравнения: dij
(0)
=
cij
,
dij
(
m
+1)
=
min
(
dij
(
m
)
,
dim
(
m
)
+
dmj
(
m
)
).
Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из vi
в vj
с промежуточными вершинами из множества {v
1
,…,
vm
,
vm
+1
}. Если этот путь не содержит vm
+1
, то dij
(
m
+1)
=
dij
(
m
)
. Если же он содержит vm
+1
, то, деля путь на отрезки от vi
до vm
+1
и от vm
+1
до vj
, получаем равенство dij
(
m
+1)
=
dim
(
m
)
+
dmj
(
m
)
. Приведенные уравнения дают возможность вычислить расстояния d
(
vi
,
vj
) =
dij
(
n
)
, где 1 £ i
,
j
£ n
. А л г о р и т м Ф л о й д а Данные: матрица весов С(
D
)
орграфа D
. Результат: расстояния между всеми парами вершин D
[i
,
j
] = d
(
vi
,
vj
).
1. Для всех i
= 1,…,n
, j
= 1,…,n
положим D
[i
,
j
] = cij
. 2. Для всех i
= 1,…,n
положим D
[i
,
i
] = 0. 3. Положим m
= 1. 4. Положим i
= 1. 5. Положим j
= 1. 6. D
[i,j
] = min ( D
[i,j
], D
[i,m
] + D
[m,j
] ). 7. Если j
<
n
, то положим j
=
j
+ 1 и переходим к шагу 6. 8. Если i
<
n
, то положим i
=
i
+ 1 и переходим к шагу 5. 9. Если m
<
n
, то положим m
=
m
+ 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D
[i
,
j
] дают расстояния между вершинами vi
и vj
. Замечание.
Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины vi
до вершины vj
. Пример. Определим длины минимальных путей между любыми парами вершин орграфа, изображенного на рис.1. Все вычисления будем проводить с помощью матриц D
. m
= 1 m
= 2 v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v1
0 ¥ 5 5 2 12 v1
0 ¥ 5 5 2 12 v2
¥ 0 ¥ ¥ ¥ 2 v2
¥ 0 ¥ ¥ ¥ 2 v3
¥ 2 0 ¥ ¥ ¥ v3
¥ 2 0 ¥ ¥ ¥ v4
¥ 2 ¥ 0 ¥ ¥ v4
¥ 2 ¥ 0 ¥ ¥ v5
¥ ¥ 1 2 0 ¥ v5
¥ ¥ 1 2 0 ¥ v6
¥ ¥ ¥ ¥ ¥ 0 v6
¥ ¥ ¥ ¥ ¥ 0 Положим m
= 1. Если i
= 1 или j
= 1, то элементы матрицы остаются без изменения, т.к. D
[i
,j
] = min
( D
[i
,j
], D
[i
,m
] + D
[m
,j
] ). Поэтому рассмотрим случай, когда i
= 2 , а j
= 3. Тогда D
[2,3
] = min ( D
[2,3
], D
[2,1
] + D
[1,3
] ) = min
(¥,¥+5) = ¥. Далее, j
= 4, т.е. D
[2,4
] = min
(D
[2,4
], D
[2,1
] + D
[1,4
] ) = min
(¥,¥+5) = ¥. Продолжаем процесс до тех пор, пока i
£ 6 и j
£ 6. Положим m
= 2 и продолжим рассуждения дальше. m
= 3 m
= 4 v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v1
0 ¥ 5 5 2 12 v1
0 7 5 5 2 9 v2
¥ 0 ¥ ¥ ¥ 2 v2
¥ 0 ¥ ¥ ¥ 2 v3
¥ 2 0 ¥ ¥ 4 v3
¥ 2 0 ¥ ¥ 4 v4
¥ 2 ¥ 0 ¥ 4 v4
¥ 2 ¥ 0 ¥ 4 v5
¥ ¥ 1 2 0 ¥ v5
¥ 3 1 2 0 5 v6
¥ ¥ ¥ ¥ ¥ 0 v6
¥ ¥ ¥ ¥ ¥ 0 m
= 5 m
= 6 v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v1
0 7 5 5 2 9 v1
0 5 3 4 2 7 v2
¥ 0 ¥ ¥ ¥ 2 v2
¥ 0 ¥ ¥ ¥ 2 v3
¥ 2 0 ¥ ¥ 4 v3
¥ 2 0 ¥ ¥ 4 v4
¥ 2 ¥ 0 |