Муравьиный алгоритм

crautcher · Регистрация: 27.05.2011

Студворк — интернет-сервис помощи студентам

У меня стояла задача написать утилиту поиска кратчайшего маршрута проходящего через указанные точки хотя бы по одному разу с последующим возвратом в исходную точку. Наткнулся на очень интересный алгоритм "алгоритм муравья" и решил о нем написать , возможно кому когда-нибудь придется решать схожие задачи .
Суть в том что в поиске источника пищи муравьи бродят рандомно . Найдя источник пищи , муравей возвращается прокладывая феромоный след . Когда рандомно гуляя , другой муравей натыкается на феромоный след он продолжает свой путь по нему . Вернувшись в гнездо он укрепят феромонную тропу .
Если существует 2 маршрута, то по более короткому, за то же время, успеют пройти больше муравьёв, чем по длинному и короткий маршрут станет более привлекательным . Длинные пути, в конечном итоге, исчезнут из-за испарения феромонов .

псевдокод выглядит так :

PHP
1
2
3
4
5
6
7
8
9
function MuravejSearch()
{
while ( !$this -> FoundBest() )
 {
   $this -> FindRandom();
   $this -> SavePath();
   $this -> PheromoneUpdate();
 }
}

@taras atavin · 13.02.2012, 13:26

Если муравей шел прямо и рандомно вильнул там, где можно спрямить, а потом вернулся на прямую и пошёл дальше, то такой путь ни когда не будет спрямлён, так как все муравьи пойдут точно по пути разведчика. Может лучше будет сделать нейросеть размером с головной нейроузел насекомого и на его основе смоделировать муравья? С теми же феромонными следами, но ближе к реальности.

crautcher · 13.02.2012, 13:38 **[ТС]**

они продолжают путь по найденому следу а не изначально по нему идут , создавая новый путь , и то если попадут на него , а если нет то прокладывают свой уникальный путь

@taras atavin · 13.02.2012, 13:54

Сначала они ищут и ищут рандомно. При этом они именно создают путь. Если на твоём рисунке можно пройти прямо, то это и есть кратчайший путь, но муравьи остановятся на третьем. Ну или сделай хотя бы способность почуять и феромон, рассеяный в воздухе после испарения с загигулины впереди.

crautcher · 13.02.2012, 13:58 **[ТС]**

Сообщение от taras atavin

Сначала они ищут и ищут рандомно. При этом они именно создают путь. Если на твоём рисунке можно пройти прямо, то это и есть кратчайший путь, но муравьи остановятся на третьем. Ну или сделай хотя бы способность почуять и феромон, рассеяный в воздухе после испарения с загигулины впереди.

еслиб можно было пройти прямо то ктонить бы срезал путь , и длиный след испарился бы быстрее

@taras atavin · 13.02.2012, 14:05

Срезал бы? Они ведь ходят рандомно. А отсюда следует, что мог ни кто не успеть пройти прямо к еде до того, как те двое назад пройдут криво, так как вероятность того, что кто нибудь случайно блужданёт прямо ниже суммарной вероятности пьяных траекторий.

crautcher · 13.02.2012, 14:12 **[ТС]**

как бы ты решил задачу . Например у тебя массив 100 на 100 . Индикатор положения в $map[1][1] . тебе надо прибавляя координаты +1 или -1 за такт цикла ,посетить сектора ну там скажем $map[47][3] , $map[8][24] , $map[99][85] , и вернутся в [1][1] . а также нельзя попадать на сектора $map[4][3] ,$map[8][23] , $map[2][92] и например на полосу от $map[50][50] до $map[50][100] .
нужно найти самый короткий маршрут (за меньшее количество тактов) и вернуть массив корринат перемещения.

@Jazon_deenAlt · 13.02.2012, 14:17

taras atavin, уважаемый, придумайте свой алгоритм атавина, в котором тысячи маленьких тарасиков будут бегать неся по пути феромоны, а затем возвращаясь улавливать феромоны и срезать углы, затем обучите муравьев двигатса по вашему алгоритму, либо просто забейте и примите алгоритм муравьиный как его придумала матушка природа

@Maple White · 17.01.2024, 08:10

Срезал бы? Они ведь ходят рандомно

Уточню что ходят они то рандомно, но проценты вероятности выбора пути зависят от кол-ва феромонов и других показателей, по специальной формуле.
Реализацию можно посмотреть в например этой библиотеке.
Находит хорошие решения в результате.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	13.02.2012, 13:26
	Если муравей шел прямо и рандомно вильнул там, где можно спрямить, а потом вернулся на прямую и пошёл дальше, то такой путь ни когда не будет спрямлён, так как все муравьи пойдут точно по пути разведчика. Может лучше будет сделать нейросеть размером с головной нейроузел насекомого и на его основе смоделировать муравья? С теми же феромонными следами, но ближе к реальности. 0

crautcher 2450 / 2301 / 597 Регистрация: 27.05.2011 Сообщений: 7,844
	13.02.2012, 13:38 [ТС]
	они продолжают путь по найденому следу а не изначально по нему идут , создавая новый путь , и то если попадут на него , а если нет то прокладывают свой уникальный путь 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	13.02.2012, 13:54
	Сначала они ищут и ищут рандомно. При этом они именно создают путь. Если на твоём рисунке можно пройти прямо, то это и есть кратчайший путь, но муравьи остановятся на третьем. Ну или сделай хотя бы способность почуять и феромон, рассеяный в воздухе после испарения с загигулины впереди. 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	13.02.2012, 14:05
	Срезал бы? Они ведь ходят рандомно. А отсюда следует, что мог ни кто не успеть пройти прямо к еде до того, как те двое назад пройдут криво, так как вероятность того, что кто нибудь случайно блужданёт прямо ниже суммарной вероятности пьяных траекторий. 0

crautcher 2450 / 2301 / 597 Регистрация: 27.05.2011 Сообщений: 7,844
	13.02.2012, 14:12 [ТС]
	как бы ты решил задачу . Например у тебя массив 100 на 100 . Индикатор положения в $map[1][1] . тебе надо прибавляя координаты +1 или -1 за такт цикла ,посетить сектора ну там скажем $map[47][3] , $map[8][24] , $map[99][85] , и вернутся в [1][1] . а также нельзя попадать на сектора $map[4][3] ,$map[8][23] , $map[2][92] и например на полосу от $map[50][50] до $map[50][100] . нужно найти самый короткий маршрут (за меньшее количество тактов) и вернуть массив корринат перемещения. 0

@Jazon_deenAlt 4117 / 999 / 191 Регистрация: 09.04.2009 Сообщений: 4,223
	13.02.2012, 14:17
	taras atavin, уважаемый, придумайте свой алгоритм атавина, в котором тысячи маленьких тарасиков будут бегать неся по пути феромоны, а затем возвращаясь улавливать феромоны и срезать углы, затем обучите муравьев двигатса по вашему алгоритму, либо просто забейте и примите алгоритм муравьиный как его придумала матушка природа 0