Комментарии 4
Подскажите, а как будет работать муравьинный алгоритм при моделировании пути,
если прошлый/этот путь перекрыт барьером (гипотетическим "бревном"-отрезком_соединяющим_два_города, которое не обойти и появившемся в этом месте или случайно или в результате оставленного "бревна" самими муравьями).
P.S. Т.е. задача из серии для моделирования трассировки пути/дорожек на электронной плате.
Интересно бы было к рассмотрения и пересекайщаяся с этим задача по расстановке исходных
элементов/компонентов на печатной плате для минимизации длины пути или сумм длин путей.
… задача с многими элементами вариативности, если рассматривать, к примеру, логические микросхемы как в планарном исполнении так и в Дип (со сверлением под их выводы отверстий в плате).
… а, если запах сильный, но путь перекрыт, то может ли, к примеру, гипотетический муравей "прогрызть" короткий путь к еде создав своеобразный мостик в этом месте не трогая само "бревно"? :)
Спасибо за интересную статью) Алгоритм оч интересный, проблема только с псевдорандомом в наших машинках) По сути алгоритм получается детерминированным. Пробовали запусках на разных сидах и считать средние ? Интересно, насколько стабильно он себя ведёт
Алгоритм всегда ведёт себя по разному, изза того что сид рандома прикован в системному времени, на полных графах находит наилучшее решение в среднем за 10-15 итераций, однако если же граф не полный, что очень плохо для данного алгоритма, то 75 итераций (75 это константа установленная в моей реализации) не всегда хватает для нахождения хоть какого то пути, для этого существуют усовершенствованные алгоритмы муравьёв, в данной статье я разобрал классический муравьиный алгоритм.
посещенные/не посещенные вершины - стоило бы реализовать маской, чтобы перебором за О(n) не искать через std::find
колесо рулетки стоило бы реализовать через бинарный поиск, а не опять же линейным алгоритмом. Если вероятность выпала 0.3, к примеру, то в массиве {0.2 0.7 1.0} делаем бинарный поиск и находим, что 0.3 соответствует второй позиции. Это существенно ускорит алгоритм.
Кроме проблем с временной сложностью алгоритма при реализации возникли и проблемы с пространственной сложностью. Считаю, что нет необходимости хранить информацию о каждом муравье. Тем более, инициализировать всю колонию каждую итерацию это неразумно. Нам нужно знать только, где неходится текущий муравей. Кстати, об этом же сказано в приложенном видео.
Предлагаю свой алгоритм приложить сюда и посмотреть результаты в сравнении:
Также рекомендую по этой теме группу ВК, так и называется "Муравьиные алгоритмы", где собраны различные работы, люди делятся своим опытом:
Муравьиный алгоритм | Задача коммивояжёра