Поиск гамильтонова цикла в большом графе (задача коммивояжера).Часть 2

[phikus]

На вид, как алгоритм работы Spanning Tree Protocol, а вы всё муравьи, да муравьи…

[qw1]

Spanning Tree имеет быстрое оптимальное решение, поэтому муравьиные эвристики не нужны.

[Diversus]

Простейшая реализация работала за 2 часа и выиграла у жадины всего ~4%
Стоит отметить, что это связано во многом из-за простейшей реализации, многие источники утверждают, что генетический алгоритм один из лучших, если не лучший.

Да, это из-за простейшей реализации. Никто не мешает в процессе мутации и скрещивания добавить свои эвристики, т.е. какие то операции с популяцией, которые позволят быстрее сойтись.

Кстати я нашел курсовую работу, которую помогал делать жене.

Видео по коммивояжеру и генетическому алгоритму.

Вот ссылка на программу.
Получилось достаточно неплохо.