работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 1 из 11)

Курсовая работа

по курсу «Дискретная математика»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов

Вариант №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) = {c_ij}_nxn с элементами

l(v_i,v_j), если (v_i,v_j) ÎX,

c_ij =

¥, если (v_i,v_j) ÏX.

ЗАДАНИЕ 1. Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Дейкстры.

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

Пусть 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)+c_pv). (Идея состоит в следующем: пусть 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)+c_pv, то метки остаются прежними.

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 до произвольной вершины графа.

ЗАДАНИЕ 2. Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Форда-Беллмана.

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опираются на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг C вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин vÎV. Каждый раз, когда мы устанавливаем, что D[u] + c_uv < D[v], оценку D[v] улучшаем: D[v] = D[u] +c_uv.

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Можно показать, что значение каждой из переменных D[v] равно тогда d(s,v) - расстоянию от s до v. Заметим, что для того, чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа. Описанная общая схема является неполной, т.к. она не определяет очередности, в которой выбираются вершины u и v. Эта очередность оказывает сильное влияние на эффективность алгоритма. Опишем алгоритм Форда-Беллмана для нахождения расстояния от фиксированной точки s до всех остальных вершин графа.

Рассмотрим орграф D = (V,X), где V={v₁,…,v_n}.

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

Данные: матрица весов С(D) орграфа D, начальная вершина s.

Результат: расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v Î V.

1. Всем вершинам vÎV орграфа присвоим метку D[v] = c_sv. Вершине s присвоим метку D[s] = 0.

2. Положим k=1.

3. Выберем произвольную вершину vÎ V &bsol; {s}.

4. Выберем произвольную вершину u ÎV.

5. Положим D[v] = min (D[v], D[u] + c_uv).

6. Если вершина u пробежала еще не все множество вершин V, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5.

7. Если вершина v пробежала еще не все множество вершин V &bsol; {s}, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4.

8. Если k < n-2, то положить k=k+1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D[v] будут равны расстояниям d(s,v) в орграфе D.

Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины s до вершины v.

Отметим, что закончить вычисления можно, когда выполнение цикла по k не вызывает изменения ни одной из переменных D[v].

Пример. Определим минимальные пути из вершины v₁ до всех остальных вершин в нагруженном орграфе D, изображенном на рис. 1.

v₄

v₁ 5 2 2 v₂

5 2

2 1 v₃

12 v₅ 2

v₆

Рис.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] = c_sv, где s = v₁. Выберем следующую вершину v₂. Ей присвоим метку D[v₂] = min (D[v₂], D[u] + c_uv), где u ÎV, т.е. D[v₂] = min (D[v₂], D[v₃]+ c₃₂, D[v₄]+ c₄₂, D[v₅]+ c₅₂, D[v₆]+ c₆₂) = (¥,5+2, 5+2, 2+¥, 12+¥) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.