Как муравьи находят кратчайший путь

Как муравьи находят кратчайший путь Достаточно ли случайного поиска и феромонных следов, чтобы колония нашла самую короткую дорогу к пище? Статья Лéo Дана «Les fourmis partent dîner» разбирает математическую модель, в которой ответ зависит от правил возвращения, реакции на феромоны и устройства графа. Лабиринт заменяют графом. Муравьи отправляются за пищей по очереди, выбирая ребро с вероятностью, пропорциональной его феромонному весу. На обратном пути каждый следует цепочке предшественников, запомненных при первом посещении вершин, и подкрепляет только этот маршрут. Петель в нём нет, но кратчайшим он быть не обязан. Тем интереснее коллективный результат. Для последовательно-параллельных графов и графа-ромба доказано, что вес каждого ребра, делённый на число прошедших муравьёв, имеет предел. Почти наверное этот предел положителен на рёбрах кратчайших путей и равен нулю на остальных. Несколько оптимальных маршрутов могут сохраняться одновременно. Для произвольного графа это остаётся гипотезой в изложении статьи. Автор показывает на простом примере, как короткий маршрут получает первоначальное преимущество, а затем обсуждает отдельную задачу о распределении случайных предельных весов между оптимальными маршрутами. Особенно показательно изменение правила выбора. Если вероятность перехода пропорциональна весу в степени α, то при α > 1 подкрепление сосредоточивается на одном пути, который может оказаться длиннее кратчайшего. При α < 1 ненулевые предельные веса сохраняются у всех путей, а для последовательно-параллельных графов определяются их структурой. Линейный случай α = 1 выделяется именно отбором кратчайших маршрутов в доказанных случаях. Одного наличия феромонной памяти для такого результата недостаточно. https://images.math.cnrs.fr/freeze/img/pdf/dana_leo.pdf Наши каналы MAX · Telegram · Дзен #ТеорияГрафов #Вероятность #Самоорганизация #КратчайшийПуть