Содержание

Введение

Раздел 1. Общая часть

1.1 Постановка задачи

1.2 Цели разработки

1.3 Построение математической модели

1.4 Описание математического метода

Раздел 2 . Специальная часть

2.1 Расчёт математической модели

2.2 Описание программы

2.2.1 О программе

2.2.2 Алгоритм работы программы

2.2.3 Входные данные

2.2.4 Выходные данные

2.3 тестирование программы

2.4 Руководства пользователю

Заключение

Литература

Введение

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

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

Целью курсовой работы было изучить и реализовать на практике алгоритм Флойда для нахождения кратчайших путей в графе. Объектом работы является алгоритм Флойда.

Задачи работы:

1. Изучение теории графов.

2. Изучение алгоритма Флойда для нахождения кратчайших путей в графе.

3. Создание приложения, которое реализует алгоритм Флойда.

4. Отладка приложения.

Раздел 1. Общая часть

1.1 Постановка задачи

Прикладная задача, которую будет решать алгоритм Флойда, заключается в следующем: Телефонная компания обслуживает семь удаленных друг от друга районов, которые связаны сетью. Компании необходимо определить наиболее эффективные маршруты пересылки сообщений между любыми двумя районами.

Схема 1. Постановка задачи

1.2 Цель разработки

Целью курсовой работы является создание компьютерной модели решение задачи реализующего метод принятия решений в условиях неопределенности для достижения поставленной цели по созданию компьютерной модели необходимо реализовать следующие подцели:

1. Понять математические закономерности конкретного объекта, его структуру, основные свойства и законы развития.

2. Научиться управлять объектом или процессом при задании целях и критериях.

3. Прогнозировать прямые и косвенные последствия реализации данной математической модели.

При достижении данных целей программа должно удовлетворять требованиям:

· быть понятной пользователю;

· обладать наглядным графическим интерфейсом;

· быстро и корректно выполнять расчеты;

· реализовать данные математический метод, оптимальным образом;

· легко переноситься на различные технологические платформы.

1.3 Построение математической модели

Цель алгоритма Флойда - определение кратчайшего пути между вершинами взвешенного графа. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию d_ij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Постановка задачи: пусть дан непустой взвешенный граф G=(V, E) с произвольными весами ребер (дуг). Требуется найти длины кратчайших путей между всеми парами вершин графа

Применительно к прикладной задаче целью разработки приложения является - определение наиболее эффективного маршрута пересылки сообщений между любыми двумя районами. Причем алгоритм может решать подобные задачи для разных критериев, например, критерием может быть - поиск наиболее дешевого пути (каждой дуге ставится в соответствие денежный эквивалент, который необходимо затратить при использовании этой дуги); или поиск наиболее быстрого пути (в этом случае каждой дуге присваивается время, которое будет потрачено при ее использовании); можно таким же образом найти самый надежный путь (каждой дуге ставится в соответствие коэффициент риска передачи сообщения по этой дуге/пути). Подобных задач может возникнуть очень много, а цель этих задач одинакова - нахождение кратчайшего пути из одного состояния в другое (относительно графа - нахождение минимального расстояния между 2-мя вершинами).

1.4 Описание математического метода

Основная идея метода Флойда состоит в следующем: пусть есть три узла i, j и k и заданы расстояния между ними (рис. 1). Если выполняется неравенство d_ij + d_jk < d_ik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (условно называемая треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Схема 2. Треугольный оператор

Алгоритм Флойда требует выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояния D₀ и матрицу последовательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k :=1.



Схема 3.Первоначальная ситуация

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_ij матрицы D_k-1. Если выполняется неравенство d_ik + d_kj < d_ij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:

· создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij на сумму d_ik + d_kj,

· создаем матрицу S_k путем замены в матрице S_k-1 элемента s_ij на k. Полагаем k = k + 1 и повторяем шаг k.

Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу D_k-1 так, как она показана на рисунке 4. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:

Схема 4. Иллюстрация алгоритма Флойда

После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам.

Расстояние между узлами i и j равно элементу d_ij в матрице D_n.

Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i -> k -> j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

Схема 5. Треугольный оператор

Раздел 2 Специальная часть

2.1 Расчет математической модели

Составим для поставленной задачи изображенной на рисунке 1 матрицу смежности, получим матрицу D₀ схема 6.

D₀ =

Схема 6. Первоначальная матрица

Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов схема 7:

D = S =

Схема 7. Результат работы алгоритма

Таким образом, например, кратчайшее расстояние из первой вершины во вторую равно 4. Из шестой в седьмую равно 9, причем проходим через 5-ю вершину, из пятой в первую расстояние равно 10, и проходим через 7-ю вершину, схема 8.

Схема 8. Результат работы алгоритма показан на графе

Путь из 6 в 9 равен 2+7=9.Путь из 1 в 2 равен 4

Перенумеруем узлы по другому схема 9.

Схема 9. Вторая задача

Составим для поставленной задачи изображенной на рисунке 1 матрицу смежности, получим матрицу D₀ схема 10.

D₀ =

Схема 10. Первоначальная матрица к второй задаче

Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов схема 11:

D = S =

Схема 11. Результат работы алгоритма

Таким образом, например, кратчайшее расстояние из первой вершины в третью равно 7, путь проходит через 2-ю вершину. Из шестой в четвертую равно 7, причем проходим через 7-ю вершину, схема 12.



Схема 12. Результат работы алгоритма показан на графе

Перенумеруем узлы по другому схема 13.

Схема 13. Третья задача

Составим для поставленной задачи изображенной на рисунке 13 матрицу смежности, получим матрицу D₀ схема 14.

D₀ =

Схема 14. Первоначальная матрица к третьей задаче

Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов схема 15:

D = S =

Схема 15. Результат работы алгоритма

Таким образом, например, кратчайшее расстояние из третьей вершины в шестую равно 10, путь проходит через 5-ю вершину. Из седьмой во вторую равно 7, причем проходим через 1-ю вершину.

2.2 Описание программы

Программа написана в среде Borland Delphi 7. Главное окно приложения имеет следующий вид (рисунок 1):



Рисунок 1. Главное окно приложения

2.2.1 О программе

Программа написана в среде Borland Delphi 7. Главное окно приложения имеет следующий вид (рисунок 2):



Рисунок 2. Главное окно приложения

Главное меню программы содержит следующие пункты:

Файл	Помощь
Закрыть	Справка
	О программе

По нажатию на пункт Файл->Закрыть приложение завершает свою работу.

По нажатию на пункт Помощь->Справка на экран выводится справка пользователю по правильному применению приложения для расчета кратчайших путей рисунок 3.



Рисунок 3. Пункт меню Помощь->Справка

По нажатию на пункт Помощь->О программе на экран выводится сообщение об авторе программы рисунок 4.

Рисунок 4. Пункт меню Помощь->О программе

2.2.2Алгоритм работы программы

В основе программы лежит алгоритм Флойда, который реализуется в следующей блок-схеме:



2.2.3 Входные данные

Входными данными является матрица смежности графа, то есть матрица, содержащая веса дуг взвешенного графа. Матрица смежности представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию d_ij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Существуют некоторые ограничения на матрицу смежности:

1. На главной диагонали размещены нули.

2. Если дуги между 2-мя вершинами, то вес ребра принимает значение 100.

2.2.4 Выходные данные

По завершению работы приложения на экран выводится матрица кратчайших путей, которая представляет из себя квадратную матрицу с n строками и n столбцами. Элемент (i, j) равен минимальному расстоянию mind_ij от узла i к узлу j, которое имеет конечное значение, если существует путь из узла i в узел j, и равен бесконечности в противном случае.

Матрица кратчайших путей имеет следующие особенности:

1. На главной диагонали матрицы расположены нули.

2. Если путь из узла i в узел j не существует, то значение элемента матрицы (i, j) равно бесконечности, в нашем случае это 100. Так как мы приняли в входных данных 100 - как бесконечно большое число.

Вторая матрица, которую порождает алгоритм - это матрица маршрутов, которая представляет из себя квадратную матрицу с n строками и n столбцами. Элемент (i, j) содержит номер узла, через который необходимо пройти, чтобы попасть из узла i в узлу j. Если элемент (i, j) матрицы маршрутов содержит 0, значит между узлами i и j нет промежуточных узлов.

2.4Тестирование программы

Проверим, правильно ли рассчитывает программа кратчайшие пути. Воспользуемся задачей 1, постановка которой приведена на рисунке 1. Получим следующий результат рисунок 5:

Рисунок 6. Нахождение кратчайшего пути

Таким образом видим, что приложение верно рассчитало матрицу кратчайших путей.

Тестируем программу. Введем другие значения весов ребер, получим следующий результат, изображенный на рисунке 7.



Рисунок 7. Расчет кратчайших путей приложением

Если введем в качестве начального узла 4, а в качестве конечного узла 7, то приложение выводит сообщение о том, что из узла 4 нет пути в узел 7, в то время как из узла 7 есть путь в узел 4.

Если сейчас ввести в качестве начального узла узел 7, а в качестве конечного узла узел 4, то получим минимальное расстояние между узлами, которое равно 3

:

Рисунок 8. Расчет кратчайших путей задачи приложением

2.5 Руководство пользователю

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

1. Приложение следует использовать для реализации метода Флойда нахождения кратчайшего пути в графе от одной вершины до другой.

2. Первоначально вводится веса дуг графа.

3. Далее необходимо нажать кнопку "Применить", чтобы программы обработала введенные пользователем данные и применила по отношению к ним алгоритм Флойда. На этом этапе, таблица «Матрица весов ребер графа» будет отображать матрицу смежности графа в соответствии с рисунком. Таблица «Матрица кратчайших путей» будет отображать те узлы, через которые проходит кратчайший путь.

4. Для определения кратчайшего пути между любыми 2-мя узлами нужно ввести номер первоначального узла, номер конечного узла и нажать на кнопку «Рассчитать».

Заключение

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

При выполнении курсовой работы были выполнены следующие задачи

1. Изучены общие понятия теории графов: граф, узлы графа, ориентированные графы, дуги графа, кратчайшие пути из одной вершины в другую.

2. Изучены алгоритмы нахождения кратчайших путей в графе, такие как алгоритм Дейкстры (является частным случаем алгоритма Флойда) и алгоритм Флойда.

3. Создано приложение, которое реализует алгоритм Флойда для поставленной задачи.

4. Приложение отлажено и протестировано на примерах, приведенных в курсовой работе.

В целом можно сказать, что алгоритм Флойда является достаточно трудоемким алгоритмом. Три вложенных цикла содержат операцию, исполняемую за константное время, то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях -- помимо расстояния между двумя узлами записывать матрицу идентификатор первого узла в пути.

Литература

1 Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. М. Изд-во МГТУ им. Н.Э.Баумана, 2003. - 325 с.

2 Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 2002. - 165 с.

3 Гофман В.Э., Хомоненко А.Д. Delphi 5. - СПб.: БХВ - Санкт Петербург, 2002. - 800с.

4 Королев Н.А. Введение в Delphi 7. М. ЮНИТИ, 2005. - 322 с.

5 Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 2002. - 222с.

6 Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 2000. - 302 с.

7 Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992. - 332 с.

8 Оре О. Теория графов. - М.: Наука, 1980. - 345 с.