Модернизация алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции

Пример готовой дипломной работы по предмету: Программирование

Оглавление

Введение 3

1. Основные определения и понятия теории графов 7

2. Задачи многокритериальной оптимизации 10

3. Оптимальность по Слейтеру и Парето 13

4. Модифицированная задача и алгоритма Дейкстры поиска кратчайших путей для векторно-весовой функции 16

5. Вычислительная эффективность алгоритма 22

6. Пример реализации модифицированного обобщенного алгоритма Дейкстры 24

7. Методы ускорения классического алгоритма Дейкстры 29

Заключение 31

Список использованной литературы 32

Содержание

Выдержка из текста

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

Во-первых, были рассмотрены основные понятия теории графов (1 часть теоретического раздела).

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

В-третьих, был подробно рассмотрен алгоритм Флойда-Уоршалла поиска кратчайших путей между каждой парой вершин (3 часть теоретического раздела).

Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление).

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

Устройства для превращения персональных компьютеров в маленькие суперкомпьютеры известны довольно давно. Ещё в 80-х годах прошлого века на рынке предлагались так называемые транспьютеры, которые вставлялись в распространенные тогда слоты расширения ISA. Первое время их производительность в соответствующих задачах впечатляла, но затем рост быстродействия универсальных процессоров ускорился, они усилили свои позиции в параллельных вычислениях, и смысла в транспьютерах не осталось. Хотя подобные устройства существуют и сейчас — это разнообразные специализированные ускорители. Но зачастую сфера их применения узка и особого распространения такие ускорители не получили.

Обработчик нажатия на кнопку Button 1 («Найти кратчайшие пути»).

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

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

Вторая распространенная задача задача нахождения минимального остовного дерева графа. Задача о минимальном остовном дереве (В англоязычной литературе «Minimum Spanning Tree»), заключается в следующем: задан связный неориентированный граф G=(V,E), где V множество вершин, |V|=n, E множество ребер между ними, и весовая функция .

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

Теория графов находит применение, например, в геоинформационных системах (ГИС).

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

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

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

Целью курсовой работы было изучить алгоритм Флойда для нахождения кротчайших путей в графе. Определим длину l(Pab) пути Pab из вершины a в вершину b, как сумму длин ребер, составляющих этот путь.Задача отыскания кратчайшего пути для заданных вершин s,tV заключается в построении пути из s в t минимальной длины при условии, что такой путь существует.

Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если нет – то временный. Обходя граф, алгоритм считает для каждой вершины маршрут, и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится вес пути. Для всех соседей данной вершины алгоритм также рассчитывает вес, при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины. [3]

Цель работы – разработка информационной системы поиска оптимального маршрута следования почтового отправления c учетом ограничения транспортных ресурсов для филилага ФГУП «Почта России» города Тверь.Для достижения поставленной цели необходимо решить следующие задачи:

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

Список использованной литературы

1. Валуев А.М. Модель многокритериального выбора основных проектных решений для глубоких карьеров // Научное обозрение. 2014. № 12. С. 76– 80.

2. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М., 1978.

3. Deo, N., Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, New Jersey, 1974.

4. Ху Т. Целочисленное программирование и потоки в сетях, М.: Мир, 1974. — 520 с.

5. JOHNSON, D. E., and JOHNSON, J. E., Graph Theory with Engineering Applications, Ronald Press, New York, New York, 1972.

6. Филлипс Д.,Гарсия-Диас А. Методы анализа сетей: пер. с англ. М. Мир, 1984. — 496 с.

7. Hitchner, L. E., A Comparative Investigation of the Computational Efficiency of Shortest Path Algorithms, University of California, Berkeley, Operations Research Center, Report No. ORC 68-17, 1968.

8. Dreyyfus, S. E., An Appraisal of Some Shortest-Path Algorithms, Operations Research, Vol. 17, pp. 395-412,1969.

9. Gilsinn, J., and Witzgall, C., A Performance Comparison of Labelling Algorithms for Calculating Shortest Path Trees, National Bureau of Standards, Washington, DC, NBS Technical Note No.777, 1973.

10. Golden, B., Shortest-Path Algorithms: A Comparison, Operations Research, Vol. 24, pp. 1164-1168,1976.

11. Denardo, E., and Fox, B., Shortest-Route Methods, 1: Reaching, Pruning, and Buckets, Operations Research, Vol. 27, pp. 161-186, 1979.

12. Bloniarz, P., A Shortest-Path Algorithm with Expected Time O(n 2log n log* n), SlAM Journal on Computing, Vol. 12, pp. 588-600, 1983.

13. ФордЛ.Р., Фалкерсон Д.Р. Потоки в сетях. : пер. с англ. – М.: Мир, 1966, 356с.

14. Moore, E. F., The Shortest Path through a Maze, Proceedings of the International Symposium on the Theory of Switching, Part II, pp. 285-292, 1957; Annals of the Computation Laboratory of Harvard University, Harvard University Press, Cambridge, Massachusetts, Vol. 30, 1959.

15. Bellman, R. E., On a Routing Problem, Quarterly of Applied Mathematics, Vol. 16, pp. 87-90, 1958.

16. Floyd, R. W., Algorithm 97, Shortest Path, Communications of the ACM, Vol. 5, p.345, 1962.

17. Эвристики для поиска кратчайших путей [Электронный ресурс].

– Режим доступа: http://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D0%BF%D1%83%D1%82%D0%B5%D0%B9. Дата обращения: 01.03.2017 г.

18. Эвристический поиск [Электронный ресурс].

– Режим доступа: http://chernykh.net/content/view/293/493/. Дата обращения: 13.03.2017 г.

19. Hart, P. A Formal Basis for the Heuristic Determination of Minimum Cost Paths / P. Hart, N. Nilsson, B. Raphael // IEEE Trans. Syst. Science and Cybernetics. – 1968. — № SSC-4(2).

– C. 100-107.

20. 54 Koenig, S. Incremental Heuristic Search in Artificial Intelligence / S. Koenig, M. Likhachev, Y. Liu, D. Furcy // Artificial Intelligence Magazine. – 2004. — № 25(2).

• C. 99-112.

21. Cormen, Thomas H. Introduction to Algorithms Third Edition Thomas / Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. – Ldn. : The MIT Press, 2009. – 1313 c.

22. Deo, N. Shortest-path algorithms: Taxonomy and Annotation / N. Deo, C. Pang // Networks. – 1984. — № 14. — С. 275– 323.

23. Котов, А.Н. Метод минимизации суммарных затрат по развертыванию распределительных сетей на основе модифицированного метода Дейкстры [Электронный ресурс]

/ А.Н. Котов. – СПб. : СПбГУТ им. проф. М.А. Бонч-Бруевича, 2007. – Режим доступа: http://jurnal.org/articles/2007/radio 4.html . Дата обращения: 26.03.2017 г.

список литературы