Аннотация 2
Введение 5
Глава 1 Анализ исследуемой задачи 7
1.1 Описание и постановка задачи поиска кратчайшего пути в графе 7
1.2 Выбор и обоснование принципа и методов решения задачи 11
1.3 Аналитический обзор состояния проблемы в литературе 13
Глава 2 Разработка и реализация алгоритмов решения задачи 17
2.1 Используемые методы и алгоритмы решения задачи 17
2.2 Сравнение выбранных алгоритмов для решения поставленной задачи 27
2.3 Программная реализация выбранных алгоритмов 29
Глава 3 Проведение вычислительных экспериментов 36
3.1 Выбор методики проведения эксперимента. Подготовка оборудования и программного обеспечения 36
3.2 Проведение эксперимента и анализ результатов 37
Заключение 40
Список используемой литературы 41
Приложение А Программный код генерации графа для тестирования алгоритмов 43
Купить

Поиск кратчайшего пути от одной вершины графа до другой на сегодняшний момент является одной из наиболее востребованных математических задач, и имеет обширную зону практического применения: транспортная логистика, начиная от масштабных грузовых перевозок, заканчивая персональными автомобильными навигаторами; системы автопилотов воздушных и морских судов; размещение товаров на складе; сетевые коммуникации; социологические связи между группами людей и многое другое. Проблемы кратчайшего пути важны при изучении сетей. Во- первых, они очень распространены на практике; часто нужно найти лучший маршрут для отправки чего-либо из одного места в другое. Во-вторых, они обеспечивают основу для ряда ключевых идей предметного материала; рассматривая проблемы пути, можно заложить основу для большого количества других, более сложных сетевых моделей.
Если раньше поиск кратчайшего пути в графе мог занимать огромное количество времени в случае масштабных и запутанных графов, то с появлением первых ЭВМ эта задача стала более тривиальной. Вычислительные мощности современных устройств позволяют буквально «на лету» вычислять сложные пути и корректировать их в зависимости от внешних обстоятельств. Таким образом, актуальность бакалаврской работы заключается в реализации практического решения актуальной проблемы. Такое решение представляет практический интерес, поскольку может быть использовано для дальнейшего решения проблемы поиска кратчайшего пути в графе, а также теоретический, поскольку позволяет найти наиболее оптимальный алгоритм для решения каждой задачи.
Объект исследования бакалаврской работы - теория графов.
Предмет исследования - проблема поиска кратчайшего пути графа и конкретные алгоритмы решения данной проблемы.
Целью ВКР является разработка программного обеспечения для решения задачи поиска кратчайшего пути в графе, а также проведение анализа алгоритмов, позволяющего выявить наиболее оптимальный алгоритм решения поставленной проблемы.
Для достижения цели ВКР необходимо выполнить следующие задачи:
• провести анализ предметной области и определить итоговую формулировку решаемой задачи;
• провести аналитический обзор состояния проблемы в работах других исследователей для конкретизации используемых алгоритмов;
• выбрать алгоритмы, используемые для решения поставленной задачи;
• реализовать выбранные алгоритмы в виде программного кода;
• протестировать полученные программы и выбрать наиболее оптимальный алгоритм для решения поставленной задачи.
Структурно ВКР состоит из введения, трёх глав, заключения и приложения.
В первой главе рассматривается теоретическая основа поставленной задачи, её описание и решение в работах других авторов, а также математическое описание задачи для дальнейшего поиска решения.
Вторая глава ВКР посвящена алгоритмам решения задачи поиска кратчайшего пути в графе. В ней подробным образом описываются алгоритмы, их достоинства и недостатки в контексте решаемой задачи, а затем описывается реализация выбранных алгоритмов в виде программ.
В третьей главе бакалаврской работы полученные программы проходят тестирование, их работа профилируется, полученные данные подвергаются анализу и на основании данных о работе каждого алгоритма принимается решение о возможности использования его для решения искомой задачи. Кроме этого, выявляется наиболее оптимальный алгоритм для решения задачи поиска кратчайшего пути в графе.
Купить