АЛГОРИТМ МУРАВЬИНОЙ КОЛОНИИ ДЛЯ ПОИСКА ОПТИМАЛЬНЫХ МАРШРУТОВ ОБХОДА ГРАФА

Введение 4
1 Общие сведения об алгоритмах поиска пути в графе и оптимизации маршрута 7
1.1 Понятие графа 7
1.2 Точные алгоритмы поиска путей в графах 9
1.3 Эвристические алгоритмы 10
1.4 Необходимость разработки эвристического алгоритма 12
2 Задача оптимизации маршрута 15
2.1 Постановка задачи обхода точек назначения 15
2.2 Математическая постановка задачи 16
2.3 Муравьиный алгоритм 17
3 Реализация приложения 21
3.1 Основные сведения о программе и её компоненты 21
3.2 Интерфейс и этапы работы с программой 23
3.3 Проверки и ограничения 27
4 Анализ разработанной программы 30
4.1 Подбор оптимальных параметров алгоритма 30
4.2 Анализ эффективности алгоритма 31
4.3 Требуемые модификации 33
Заключение 35
Список использованных источников 37
Приложение А Файл управления моделью 39
Приложение Б Файл представления графа и интерфейса 46
Приложение В Файл модели графа с алгоритмом 50

Весь текст будет доступен после покупки

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

Весь текст будет доступен после покупки

1 Общие сведения об алгоритмах поиска пути в графе и оптимизации маршрута

1.1 Понятие графа

Граф — это математическая структура, которая состоит из множества вершин (узлов) и множества соединяющих их рёбер. Эта структура позволяет наглядно представить сложные взаимосвязи и взаимодействия между объектами или явлениями. Графы как схемы связи в различных областях по типу компьютерных сетей, транспортных [2].
Для понимания объекта работы с алгоритмом необходимо классифицировать возможные типы графов в работе, так как каждый тип задает различные условия маршрутизации.
Неориентированный взвешенный граф – не имеющий четкого направления ребра, являющегося двусторонним, и с весовой стоимостью, представляющей, например, время или расстояние перемещения между двумя узлами. Связный – в таком графе каждая вершина является достижимой, то есть возможен путь из любой вершины в каждую. Пример такого графа представлен на рисунке 1.

Весь текст будет доступен после покупки

1 Костин, А. С. Исследование алгоритма маршрутизации для решения задачи коммивояжера на примере алгоритма муравьиной колонии / А. С. Костин, Д. В. Кучко // Системный анализ и логистика. – 2023. – № 4(38). – С. 47-53. – DOI 10.31799/2077-5687-2023-4-47-53. – EDN VTXDDL. — Текст: непосредственный.
2 Дольников, В. Л. Теория графов. Алгоритмы на графах : Учеб. пособие : [Для студентов ЯрГУ] / В. Л. Дольников, О. П. Полякова ; В.Л. Дольн¬иков, О.П. Полякова; М-во образования Рос. Федерации, Яросл. гос. ун-т им. П.Г. Демидова. – Ярославль : ЯрГУ, 2003. – 115 с. – ISBN 5-8397-0312-5. – EDN QJMPMP. — Текст: непосредственный.
3 Штовба С. Д. Муравьиные алгоритмы. Журнал «Математика в приложениях», 2003 г., №4, с. 70-75. — Текст: непосредственный.
4 Ветрова, О. А. Использование компьютерной модели "муравьиных" алгоритмов в задачах логистики / О. А. Ветрова, Т. М. Кузьмина, П. С. Калошин // Альманах мировой науки. – 2017. – № 1-1(16). – С. 41-43. – EDN XXDBTF. — Текст: непосредственный.
5 Штовба, С. Д. Муравьиные алгоритмы: теория и применение / С. Д. Штовба // Программирование. – 2005. – Т. 31, № 4. – С. 3-18. – EDN HSCKQV. — Текст: непосредственный.
6 Сазонова, А. С. Применение муравьиного алгоритма для решения задач коммивояжера, путём создания имитационной модели муравьиной колонии / А. С. Сазонова, А. С. Ашеко // Автоматизация и моделирование в проектировании и управлении : сборник научных статей Всероссийской конференции, Брянск, 22 мая 2023 года. – Курск: ЗАО «Университетская книга», 2023. – С. 7-14. – EDN NIFFBF. — Текст: непосредственный.
7 Гергедава, Д. А. Анализ эффективности алгоритма муравьиной колонии в задаче маршрутизации транспортных средств с ограниченной вместимостью / Д. А. Гергедава // Международный журнал информационных технологий и энергоэффективности. – 2024. – Т. 9, № 4(42). – С. 128-137. – EDN KEOUMW. — Текст: непосредственный.

Весь текст будет доступен после покупки