Муравьиный алгоритм. Решение задачи коммивояжера

[RodionGork]

С одной стороны спасибо что рассказали об этом алгоритме - я его не знал и поэтому весьма заинтригован и рад :) с другой стороны, извините за прямоту, но в ваше изложение не очень легко вникнуть - я в какой-то момент бросил и пошёл википедию читать :) возможно если где-то в начале "принципов работы алгоритма" добавить пояснение как там муравьи бегут по очереди и зачем они тут и там оставляют ферромоны и как это отмечается - получится более понятно для неподготовленного пользователя.

[alivewel]

Спасибо за обратную связь. В данной статье я постарался максимально понятно и подробно объяснить его работу. Когда я сам изучал его, мне потребовалось несколько дней, чтобы понять его. Алгоритм не из простых :)

[Lukerman]

Del

[xorcerer]

А какая ассимптотика у этого алгоритма?

[alivewel]

Думаю, что сложность алгоритма O(n^2). В цикле по муравьям O(n) + в цикле при построении пути O(n). Ну и основной алгоритм 100 раз каждый раз запускается.

[FemboyEnjoyer]

тся

[Zara6502]

выделяете и Ctrl+Enter

[Deosis]

Задача коммивояжера - NP-трудная, и из заголовка следует, что вы доказали, что P = NP.

Так что стоит указать, что решение - приближенное, раньше, чем в последней строке.

[Asker1987]

Про муравьиные алгоритмы, да и ещё для решения задачи коммивояжера, в Хабре полно статей. Эта, увы, одна из самых бедных.

[alivewel]

Да, в интернете много теоретической информации о данном алгоритме. Данная статья носит больше практическую цель. Я поставил себе цель написать алгоритм на языке Go и, к сожалению, не смог найти ничего подобного. Поэтому пришлось провести свой ресерч и написать свою реализацию, результат работы изложен в данной статье.

[Bigata]

А почему 100 итераций? Есть какое-то логичное объяснение или просто ткнули в круглую цифру?

[alivewel]

100 итераций алгоритма было в книге от Михаила Кирсанова на языке maple. Предполагаю, что при больших размерах графа число итераций нужно увеличить. Для более точного ответа нужно провести тесты.