Главная      Учебники - Разные     Лекции (разные) - часть 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 с элементами

l (vi , vj ), если (vi , vj ) ÎX ,

cij =

¥, если (vi , vj ) Ï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 )+ 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 до произвольной вершины графа.

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

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами 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.

v4

v1 5 2 2 v2

5 2

2 1 v3

12 v5 2

v6

Рис.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 .

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

Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя 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