Введение
Глава 1 Анализ и определение проблемы поиска кратчайшего пути в графе
1.1Постановка задачи поиска кратчайшего пути в графе
1.2Задача поиска кратчайшего пути в графе с одним источником
1.3Задача поиска оптимального пути в графе
Глава 2 Анализ алгоритмов поиска пути в графе
2.1Алгоритм поиска в ширину
2.2Жадный алгоритм поиска кратчайшего пути
2.3Алгоритм Дейкстры
2.4Алгоритм A*
2.4Сравнительный анализ алгоритмов поиска пути в графе
Глава 3 Программная реализация поиска пути в графе
3.1Разработка логической архитектуры программы
3.2Разработка программного обеспечения для реализации алгоритмов
поиска
Заключение
Список используемой литературы и используемых источников
Приложение АФрагмент кода формы интерфейса программы
Большое разнообразие проблем в области науки и техники может быть сведено к проблемам поиска пути в графе, таких как задача кратчайшего пути или задача поиска оптимальных путей относительно более общих определенных целевых функций др. [20].
Стоить отметить, что поиск кратчайшего и оптимального пути в графе имеет широкое практическое применение, например, при решении задач маршрутизации телефонного или интернет-трафика, компоновки печатных плат, GPS-маршрутизации, принятии решений в области искусственного интеллекта и робототехникии др.
Для решения таких задач используются алгоритмы поиска пути в графе.
Исследования и программная реализация алгоритмов поиска пути в графеявляются актуальными и представляют научно-практический интерес.
Объектом исследованиябакалаврской работы является граф.
Предметом исследованиябакалаврской работы являются алгоритмы поиска пути в графе.
Цельвыпускной квалификационной работы - исследование и программная реализация алгоритмов поиска кратчайшего пути в графе на платформе 1С: Предприятие 8.
Для достижения данной цели необходимо выполнить следующие задачи:
-проанализировать проблему поиска кратчайшего пути в графе;
-произвести анализ известных алгоритмов поиска кратчайшего пути в графе;
-выполнить программную реализацию и тестирование известных алгоритмов кратчайшего поиска пути в графе на платформе 1С: Предприятие 8.
Методы исследования- математический аппарат графов, методы и алгоритмы поиска путей в графе, объектно-ориентированный подход к 5
проектированию программного обеспечения.
Практическая значимостьбакалаврской работызаключается в разработке комплекса программ, реализующих популярные алгоритмы поиска кратчайшего пути в графе.
Данная работа состоит из введения, трех глав, заключения, списка используемой литературы и приложений.
Первая глава посвящена анализу и определению проблемы поиска кратчайшего пути в графе, описаны задачи поиска кратчайшего и оптимального пути в графе.
Во второй главе проанализированы известные алгоритмы поиска кратчайшего пути в графе: алгоритм поиска в ширину; жадный алгоритм; алгоритм Дейкстры; алгоритм А*.
Третья главапосвящена программной реализации известных алгоритмов поиска кратчайшего пути в графе. Разработаны логическая архитектура и конфигурация программы. Выполнено экспериментальное тестирование алгоритмов.
В заключении описываются результаты выполнения выпускной квалификационной работы.
Приложение содержит фрагменты программного кода.
Структура бакалаврской работы: страниц 49с приложением, рисунков 14, таблиц 2, источников 24.
Бакалаврская работа посвящена актуальной проблеме анализа и реализации алгоритмов поиска пути в графе.
В ходе выполнения бакалаврской работы достигнуты следующие результаты:
1.Проанализирована проблема поиска пути в графе. Описаны общая задача поиска кратчайшего пути в графе, задача поиска пути с одним источником и задача поиска оптимального пути в графе.
2.Приведен анализ известных алгоритмов поиска кратчайшего пути в графе: алгоритма поиска в ширину, жадного алгоритма, алгоритма Дейкстры и алгоритма А*. Как показал сравнительный анализ, все известные алгоритмы позволяют решить задачу поиска кратчайшего пути в графе. Выбор конкретного алгоритма поиска пути в графе зависит от многих факторов, в том числе от требования простоты программной реализации алгоритма.
3.Выполнена программная реализацияизвестных алгоритмов поиска кратчайшего пути в графе. Разработаны логическая архитектура программы и конфигурация на платформе 1С: Предприятие 8.3.
4.Проведено экспериментальное тестирование алгоритмов на одном и том же случайном графе. Тестирование известных алгоритмы поиска пути в графе с помощью разработанной программы подтвердило их описанные свойства.
Результаты бакалаврской работы могут быть рекомендованы для практического решения задач поиска кратчайшего и оптимального пути в графе на платформе 1С: Предприятие 8.
