Задача коммивояжера: обходим 750 точек за 5 сек
Доброго времени суток . Спасибо всем заинтересовавшимся моей статьей. Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации. Её суть заключается в поиске самого выгодного маршрута, который проходит через указанные города по одному разу с последующим возвратом в исходный город. Уже при небольшом числе городов >20 задача не может быть решена методом перебора вариантов за приемлемое время.Для решения задачи коммивояжёра существует большое количество методов и алгоритмов, самые распространённые — поисковые алгоритмы. Лидеры среди них — генетические алгоритмы и алгоритмы колонии муравьёв.Я придумал свой вариант.В статье «Сравнение производительности генетических алгоритмов и муравьиных алгоритмов применительно к задаче коммивояжера Авторы: Sabry Ahmed Haroun, Benhra Jamal, El Hassani Hicham Лаборатория LISER, ENSEM, UH2C Касабланка, Марокко.» от May 2015. Приводятся результаты тестов. Генетический алгоритм был разработан на C++. Муравьиный алгоритм оптимизации был написан на C#. Читать далее