
Тип работы:	Предмет:	Язык работы:

Исследование алгоритмов поиска пути в графе

Работа №	108960
Тип работы	Бакалаврская работа
Предмет	информатика
Объем работы	49
Год сдачи	2020
Стоимость	4700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	71

Не подходит работа?

Узнай цену на написание

Содержание

Введение
Глава 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.

Литература

1.Алгоритм A* [Электронный ресурс]. URL:
https: //neerc. ifmo. ru/wiki/index. php?title=%D0%90%D0%BB%D0%B3%D0%BE %D1%80%D0%B8%D1%82%D0%BC A*#.D0.A0.D0.B5.D0.B0.D0.BB.D0.B8. D0.B7.D0.B0.D1.86.D0.B8.D1.8F(gama обращения: 12.02.2020).
2.Алгоритм Дейкстры[Электронный ресурс]. URL:https://algowiki- project.org/ru/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1% 82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D 1 %81 %D 1 %82%D 1 %8 0%D1%8B(дата обращения: 12.02.2020).
3.Алгоритмы поиска пути в графе [Электронный ресурс]. URL: https://infostart.ru/public/1088569/ (дата обращения: 12.02.2020).
4.Архитектура платформы 1С:Предприятие(версия
8.3.17) [Электронный ресурс]. URL:https://v8.1c.ru/platforma/(дата обращения: 12.02.2020).
5.БойковВ. А. О применении жадных алгоритмов в некоторых задачах дискретной математики // Программные продукты и системы. 2019. №1. С.55-62.
6.ГОСТ 19.402-78. Единая система программной документации. Описание программы.
7.ГОСТ 19.701-90 (ИСО 5807-85) Единая система программной документации (ЕСПД). Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения.
8.Задача о кратчайшем пути [Электронный ресурс]. URL:
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D 0%B0%D0%BE%D0%BA%D 1 %80%D0%B0%D 1 %82%D 1 %87%D0%B0%D 0%B9%D 1 %88%D0%B5%D0%BC%D0%BF%D 1 %83%D 1 %82%D0%B8 (дата обращения: 12.02.2020).
9.Ларман К. Применение UML и шаблонов проектирования. М. :
Издательский дом «Вильямс», 2004. 624 с.
10.Лекция «Алгоритм Дейкстры» [Электронный ресурс]. URL: https: //www. intuit. ru/studies/professional retraining/943/courses/2/lecture/42 ?раце=6(дата обращения: 12.02.2020).
11.Плотников, Подвальный Е. С. Решение задачи поиска оптимального пути между двумя точками на графе снерегулярным весом ребер // Вестник ВГТУ. 2012. №6. С. 22-26.
12.Поиск в ширину (BFS) [Электронный ресурс]. URL: https://algowiki-
proj ect.org/ru/%D0%9F%D0%BE%D0%B8%D 1 %81 %D0%BA_%D0%B2_%D 1 %88%D0%B8%D 1 %80%D0%B8%D0%BD%D 1 %83_(BFS)(дата обращения:
12.02.2020).
13.Поиск кратчайшего пути от одной вершины (SSSP) [Электронный
ресурс]. URL: https://algowiki-
proj ect.org/ru/%D0%9F%D0%BE%D0%B8%D 1 %81 %D0%BA%D0%BA%D 1 %80%D0%B0%D 1 %82%D 1 %87%D0%B0%D0%B9%D 1 %88%D0%B5%D0%B 3%D0%BE%D0%BF%D 1 %83%D 1 %82%D0%B8 %D0%BE%D 1 %82%D0% BE%D0%B4%D0%BD%D0%BE%D0%B9%D0%B2%D0%B5%D 1 %80%D 1% 88%D0%B8%D0%BD%D1%8B(SSSP)(дата обращения: 12.02.2020).
14.Реализуем Стек, Очередь и Приоритетную очередь в
1С [Электронный ресурс]. URL:https://infostart.ru/public/1079893/ (дата
обращения: 12.02.2020).
15.Сайт Braincart.com[Электронный ресурс]. URL:
https://www.brainkart.com/(дата обращения: 12.02.2020)...