Дипломная работа на тему "ТЮМГУ | Сравнительный анализ алгоритмов поиска кратчайших путей в динамической сети на основе данных дорожной структуры г Тюмень"

Работа на тему: Сравнительный анализ алгоритмов поиска кратчайших путей в динамической сети на основе данных дорожной структуры г Тюмень
Оценка: хорошо.
Оригинальность работы на момент публикации 50+% на антиплагиат.ру.
Ниже прилагаю все данные для покупки.
https://studentu24.ru/list/suppliers/Anastasiya1---1326

Описание работы

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего образования
«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК
Кафедра программного обеспечения

РЕКОМЕНДОВАНО К ЗАЩИТЕ В ГЭК

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
бакалаврская работа
СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ДИНАМИЧЕСКОЙ СЕТИ НА ОСНОВЕ ДАННЫХ
ДОРОЖНОЙ СТРУКТУРЫ Г. ТЮМЕНЬ

02.03.03 Математическое обеспечение и администрирование информационных систем
Профиль «Технологии программирования»

Тюмень 2022 год

СОДЕРЖАНИЕ
ВВЕДЕНИЕ 3
ГЛАВА 1. ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ ЗАДАЧИ APSP 6
1.2. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 8
1.3. ОПИСАНИЕ АЛГОРИТМА ДЕМЕТРЕСКУ И ИТАЛЬЯНО 9
1.4. ОПИСАНИЕ АЛГОРИТМА РАМАЛИНГАМ И РЕПС 12
1.5. ОПИСАНИЕ АЛГОРИТМА ДЕЙКСТРЫ 17
ГЛАВА 2. ОПИСАНИЕ ИСХОДНЫХ ДАННЫХ 21
2.1. ОПИСАНИЕ ИСХОДНЫХ ДАННЫХ ДОРОГ Г. ТЮМЕНЬ 21
2.2. ПРЕОБРАЗОВАНИЕ ДАННЫХ ИЗ OSM В ДОРОЖНЫЙ ГРАФ 22
2.3. ОПИСАНИЕ ДОРОЖНЫХ ГРАФОВ Г. ТЮМЕНЬ 24
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПРИЛОЖЕНИЯ 26
3.1. ОПИСАНИЕ ПРИЛОЖЕНИЯ 26
3.2. ОПИСАНИЕ СТРУКТУР И МЕТОДОВ ПРИЛОЖЕНИЯ 28
ГЛАВА 4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 32
4.1. ИССЛЕДОВАНИЕ ИСПОЛЬЗУЕМОГО ОБЪЕМА ОЗУ НА СЛУЧАЙНЫХ ВХОДНЫХ ДАННЫХ 33
4.2. ИССЛЕДОВАНИЕ ЗАТРАЧЕННОГО ОБЪЕМА ОЗУ НА РЕАЛЬНЫХ ДАННЫХ 39
4.3. СРАВНЕНИЕ ВРЕМЕНИ ВЫПОЛНЕНИЯ АЛГОРИТМОВ 41
ЗАКЛЮЧЕНИЕ 43
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 44
ПРИЛОЖЕНИЯ 1-7 49

ВВЕДЕНИЕ
Задача поиска кратчайших путей между всем парами вершин (задача APSP1) является одной из фундаментальных алгоритмических задач в теории графов [7]. Различают две разновидности такой задачи – статическая и динамическая – ключевое отличие между которыми заключается в рассматриваемом графе. В классической (статической) задаче APSP структура и веса ребер исследуемого графа не изменяются с течением времени, в таком случае кратчайшие пути находятся один раз и далее используются без изменений. В другой, менее исследованной динамической задаче предполагается, что подлежащий граф изменяется с течением времени, в связи с чем возникает необходимость поддержания актуальности кратчайших путей с учетом происходящих изменений.
За последние два десятилетия проведено множество исследований в области решения динамической задачи APSP, но многие из них не дают четкого направления выбора алгоритма, когда возникает проблема вычисления кратчайших путей в реальных дорожных сетях, поскольку некоторые исследования содержат только теоретические сведения, в других работах эмпирические вычисления в основном опираются на случайно сгенерированные сети.
По сравнению с реальными дорожными сетями случайные часто различаются по среднему значению степени вершин, что выражается отношением количества ребер к числу вершин. Так, например в статье [28] авторы приводят диапазон значений средней степени вершин для дорожных сетей десяти штатов в США от 2,66 до 3,28.
Для города Тюмень значение средней степени вершин составляет около 2,31, а в случайных сетях данный показатель может достигать 10 [15]. Сгенерированные сети могут отличаться от реальных также тем, что длины дуг задаются независимо – это может привести к невозможным конструкциям,
например, когда один узел может быть «близок» к двум соседним узлам, которые в свою очередь находятся «далеко» друг от друга.
Одним из важных недочетов случайных сетей также можно считать однородность установления связей между вершинами, что не характерно для реальных дорожных сетей, которые часто содержат области плотной городской сети, окруженной сильно разветвленными пригородными районами. Особенно неоднородность связей ярко выражена для городов, через которые протекает река, так, например в Тюмени только шесть мостов соединяют левую и правую часть города.
Исследование алгоритмов для решения задачи APSP на основе данных реальной городской дорожной сети может быть полезно для исследователей и разработчиков интеллектуальных транспортных систем, поскольку готовые решения в основном находятся в закрытом доступе, а многие исследования носят лишь теоретический характер.
Целью выпускной квалификационной работы является проведение сравнительного анализа алгоритмов поиска кратчайшего пути между всеми парами вершин на основе данных о дорожной сети г. Тюмень.
Задачи:
1. Изучение алгоритмов поиска пути между всеми парами вершин на динамических топологических структурах.
2. Сбор данных о транспортной сети г. Тюмень из открытых источников.
3. Преобразование исходных данных в дорожный граф.
4. Программная реализация изученных алгоритмов.
5. Разработка приложения для проведения сравнительного анализа реализованных алгоритмов.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Гмурман В. Е. Теория вероятностей и математическая статистика 12- е изд. Учебник для вузов. – М.: Юрайт, 2020. – 479 с.
2. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. ? М.: УРСС, 2009. – 392 с.
3. Кочкаров А. А. Структурная динамика: свойства и количественные характеристики предфрактальных графов. – М.: Вега-Инфо, 2012. – 120 с.
4. Кочкаров А. А., Сенникова Л. И., Кочкаров Р. А. Некоторые особенности применения динамических графов для конструирования алгоритмов взаимодействия подвижных абонентов //Известия Южного федерального университета. Технические науки. – 2015. –
№. 1 (162). – С. 207-214.
5. Подлазов А. В., Щетинина Д. П. Модель роста социальной сети // ПрепринтыИПМ им. М.В. Келдыша. – 2013. – № 95. – 16 с.
6. Ревунков Г. И., Кайнов П. И., Силантьева Е. Ю. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ДРЕВОВИДНЫХ СТРУКТУР ДАННЫХ: ДВОИЧНОЕ ДЕРЕВО, ДВОИЧНАЯ КУЧА, АВЛ ДЕРЕВО И КРАСНО-ЧЕРНОЕ ДЕРЕВО //Аспирант и соискатель. – 2020. – №. 2. – С. 63-
7. Ураков А. Р., Тимеряев Т. В. Алгоритм поиска кратчайших путей для разреженных графов большой размерности //Прикладная дискретная математика. – 2013. – №. 1 (19). – С. 84-92.
8. Dauni P. et al. Implementation of Haversine formula for school location tracking //Journal of Physics: Conference Series. – IOP Publishing, 2019.
– Т. 1402. – №. 7. – С. 077028.
9. Demetrescu C., Italiano G. F. Fully dynamic all pairs shortest paths with real edge weights //Proceedings 42nd IEEE Symposium on Foundations of Computer Science. – IEEE, 2001. – С. 260-267.
10. Demetrescu C., Italiano G. F. A new approach to dynamic all pairs shortest paths //Journal of the ACM (JACM). – 2004. – Т. 51. – №. 6. – С. 968- 992.
11. Dijkstra E. W. et al. A note on two problems in connexion with graphs
//Numerische mathematik. – 1959. – Т. 1. – №. 1. – С. 269-271.
12. Even S., Gazit H. Updating distances in dynamic graphs //Methods of Operations Research. – 1985. – Т. 49. – №. 1985. – С. 37.
13. Frigioni D., Marchetti-Spaccamela A., Nanni U. Semidynamic algorithms for maintaining single-source shortest path trees //Algorithmica. – 1998. – Т. 22. – №. 3. – С. 250-274.
14. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees //Journal of Algorithms. – 2000. – Т. 34. – №. 2. – С. 251-281.
15. Gallo G., Pallottino S. Shortest path algorithms //Annals of operations research. – 1988. – Т. 13. – №. 1. – С. 1-79.
16. Garey M. R., Graham R. L., Ullman J. D. Worst-case analysis of memory allocation algorithms //Proceedings of the fourth annual ACM symposium on Theory of computing. – 1972. – С. 143-150.
17. King V. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs //40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039). – IEEE, 1999.
– С. 81-89.
18. King V., Thorup M. A space saving trick for directed dynamic transitive closure and shortest path algorithms //International Computing and Combinatorics Conference. – Springer, Berlin, Heidelberg, 2001. – С. 268
19. Loubai P. S. A network evaluation procedure //Highway Research Record.– 1967. – №. 205.
20. Murchland J. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. – Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, London, UK,1967.
21. OpenStreetMap.
22. Ramalingam G., Reps T. An incremental algorithm for a generalization of the shortest-path problem //Journal of Algorithms. – 1996. – Т. 21. – №. 2.
– С. 267-305.
23. Ramalingam G., Reps T. On the computational complexity of dynamic graph problems //Theoretical Computer Science. – 1996. – Т. 158. – №. 1- 2. – С. 233-277.
24. Rodionov V. V. The parametric problem of shortest distances //USSR Computational Mathematics and Mathematical Physics. – 1968. – Т. 8. –
№. 5. – С. 336-343.
25. Rohnert H. A dynamization of the all pairs least cost path problem
//Annual Symposium on Theoretical Aspects of Computer Science. – Springer, Berlin, Heidelberg, 1985. – С. 279-286.
26. Thorup M. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles //Scandinavian Workshop on Algorithm Theory. – Springer, Berlin, Heidelberg, 2004. – С. 384-396.
27. Thorup M. Worst-case update times for fully-dynamic all-pairs shortest paths //Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. – 2005. – С. 112-119.
28. Zhan F. B., Noon C. E. Shortest path algorithms: an evaluation using real road networks //Transportation science. – 1998. – Т. 32. – №. 1. – С. 65