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



страница1/6
Дата04.07.2013
Размер0.63 Mb.
ТипКурсовая
  1   2   3   4   5   6

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

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



Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Вариант №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, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.

Вторая метка (v) – это вершина, из которой вершина v получила свою метку.
А л г о р и т м Д е й к с т р ы
Данные: матрица весов С(D) орграфа D, начальная вершина s.

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


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

  2. Для всех vГp с временными метками выполним: если l*(v)>l*(p)+l(p,v), то l*(v)=l*(p)+l(p,v) и (v) =р. Иначе l*(v) и (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, поэтому положим (v) = p. С помощью этих допол­нительных меток будем потом восстанавливать сам путь. Если l*(v) l*(p)+cpv, то метки остаются прежними.

  1. Пусть V* - множество вершин с временными метками. Найдем вершину v* такую, что l*(v*) = min l*(v), v V*. Считать метку l*(v*) постоянной для вершины v*.

  2. Положим p = v*. Если p = t, то перейдем к п.5 ( l*(t) – длина минимального пути ). Иначе перейдем к п.2.

  3. Найдем минимальный путь из s в t, используя метки (v): П = s(t)t.

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


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



Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опираются на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг C вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин vV. Каждый раз, когда мы устанавливаем, что 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={v1,…,vn}.
А л г о р и т м Форда – Беллмана
Данные: матрица весов С(D) орграфа D, начальная вершина s.

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


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

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

  3. Выберем произвольную вершину vV \ {s}.

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

  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].
Пример. Определим минимальные пути из вершины v1 до всех остальных вершин в нагруженном орграфе 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


На первом шаге всем вершинам vV орграфа присвоим метку D[v] = csv, где s = v1. Выберем следующую вершину v2. Ей присвоим метку D[v2] = min (D[v2], D[u] + cuv), где uV, т.е. D[v2] = min (D[v2], D[v3]+ c32, D[v4]+ c42, D[v5]+ c52, D[v6]+ c62) = (,5+2, 5+2, 2+, 12+) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.

Аналогично корректируются метки всех оставшихся вершин, а именно,

D[v3] = min (D[v3], D[v2]+c23, D[v4]+c43, D[v5]+c53, D[v6]+c63) = (5,7+, 5+, 2+1, 12+) = 3,

D[v4] = min (D[v4], D[v2]+c24, D[v3]+c34, D[v5]+c54, D[v6]+c64) = (5,7+, 3+, 2+2, 12+) = 4,

D[v5] = min (D[v5], D[v2]+ c25, D[v3]+ c35, D[v4]+ c45, D[v6]+ c65) = (2,7+, 3+, 4+, 12+) = 2,

D[v6] = min (D[v6], D[v2]+ c26, D[v3]+ c36, D[v4]+ c46, D[v5]+ c56) = (12,7+2, 3+, 4+, 2+) = 9.

Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n-2 = 4.

Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v1 до всех остальных вершин. Например, длина минимального пути из v1 в v2 равна 5, сам путь имеет вид: v1v5v3v2.


      1. Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда.



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

Идея этого алгоритма следующая. Рассмотрим орграф D = (V,X), где V={v1,…,vn}. Обозначим через dij(m) длину кратчайшего из путей из vi в vj с промежуточными вершинами из множества {v1,…,vm}.

Тогда имеем следующие уравнения:

dij(0) = cij,

dij(m+1) = min ( dij(m), dim(m) + dmj(m)).

Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из vi в vj с промежуточными вершинами из множества {v1,…, 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, jn.

А л г о р и т м Ф л о й д а

Данные: матрица весов С(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



4

v4



2



0



4

v5



3

1

2

0

5

v5



3

1

2

0

5

v6











0

v6











0

Матрица D:




v1

v2

v3

v4

v5

v6

v1

0

5

3

4

2

7

v2



0







2

v3



2

0





4

v4



2



0



4

v5



3

1

2

0

5

v6











0


  1   2   3   4   5   6

Похожие:

Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconРазработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер
Для решения np-трудной задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер предлагается эффективный метод...
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconЛекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения
Машина состояний. Блок-схема алгоритма (бса). Матричная структура алгоритма (мса). Строка Тьюринга. Строка Маркова. Строка Ляпунова....
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconПеречень работ по тематике спо, выполненных в рамках государственных контрактов в период с 2003 по 2009 гг
Икт. Разработка предложений по развитию в Российской Федерации рынка программного обеспечения со свободной лицензией. Разработка...
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconЗадача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную)
Краткие сведения из истории возникновения теории графов. Области применения теории графов
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconПостроение защищенного видеоканала с использованием изоморфизма графов
Поскольку процедура дешифрования шифра двойной перестановки может быть сведена к решению задачи проверки изоморфизма графов [2],...
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconЗадача 6 олимпиадного задания выполняется на компьютере с использованием установленного прикладного программного обеспечения. Рекомендуем Вам заранее ознакомиться с ним
Для выполнения задачи 6 будут установлены две программы emt (Эмулятор машина Тьюринга) и Эмулятор нормального алгоритма Маркова
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconРабочая программа По дисциплине «Разработка программного обеспечения» По специальности
Основная задача курса – сформировать фундаментальные знания у студентов о принципах построения, реализации и функционирования программного...
Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов iconДипломной практике по теме: «Разработка программного обеспечения для моделирования комплекса многокамерной автоматизированной съемки и видеотрансляции»
«Разработка программного обеспечения для моделирования комплекса многокамерной автоматизированной съемки и видеотрансляции»
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org