Моделирование передвижения муравьев. Метод ветвей и границ, ближайшего соседа. Ограничения, накладываемые на агента в стандартной постановке задачи коммивояжера. Использование графа видимости в алгоритме муравья. Структура данных алгоритма муравья.
При низкой оригинальности работы "Использование алгоритма муравья для решения задачи коммивояжера", Вы можете повысить уникальность этой работы до 80-100%
1. Специальная часть 1.1 Постановка задачи и анализ исходных данных 1.2 Обзор известных алгоритмов для решения поставленной задачи 1.2.1 Алгоритм А* 1.2.2 Метод ветвей и границ 1.2.3 Метод ближайшего соседа 1.2.4 Алгоритм поиска в глубину (ширину) 1.2.5 Алгоритм Дейкстры 1.2.6 Алгоритм Джонсона 1.2.7 Алгоритм муравья. 1.3 Алгоритм муравья, основные понятия. 1.3.1 Биологические основы 1.3.2 Начальная популяция 1.3.3 Движение муравья 1.3.4 Пример итерации 1.3.5 Разновидности алгоритма муравья 1.4 Построение алгоритма движения муравья и моделирование этого алгоритма на ЭВМ 1.4.1 Ограничения, накладываемые на агента в стандартной постановке задачи коммивояжера 1.4.2 Алгоритм обхода препятствий 1.4.3 Пример работы алгоритма обхода препятствий 1.4.4 Структура данных алгоритма муравья 1.4.5 Использование графа видимости в алгоритме муравья 1.4.6 Моделирование алгоритма муравья на ЭВМ 1.5 Анализ полученных результатов 2. В основу алгоритма муравья положена имитация жизнедеятельности муравьиных колоний. В общем виде на графах задача формулируется следующим образом: необходимо найти минимальный маршрут, проходящий через указанные узлы графа хотя бы по одному разу с последующим возвратом в исходный узел. В настоящее время задача коммивояжера находит много практических применений в таких областях как: - Оптимизация в сетях - Оптимизация маршрутов - Приложения в кристаллографии - Управление роботами - Обработка печатных плат - Исследование ДНК Городами в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности. Обычно, в целях упрощения задачи и гарантии существования маршрута в задаче коммивояжера считается, что граф, описывающий задачу, является полностью связным, то есть, что между произвольной парой вершин существует ребро. Описание алгоритма A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Свойство монотонности означает, что если существуют пути A-B-C и A-C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше, либо равна сумме оценок путей A-B и B-C. Частные случаи В общем случае, поиск в глубину и поиск в ширину являются двумя частными случаями алгоритма A*. Известен также под названием кратчайший путь - первый (Shortest Path First). Первоначально Марком Дориго было предложено три метода муравьиных систем, различных между собой способом обновления путей - рёбер.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
