Проблема коммивояжера: когда «достаточно хорошо» лучше, чем «идеально».

Задача коммивояжера (TSP) — одна из самых известных задач в области информатики. В этом видео мы подробно рассмотрим, почему эта задача представляет собой такой вызов для специалистов по информатике, и некоторые из остроумных методов, используемых для её решения. Мы начнём с демонстрации того, почему все решения методом перебора и даже оптимизации для получения точных решений не могут быть надёжно использованы для больших экземпляров задачи. Затем мы обсудим некоторые эвристические подходы, такие как метод ближайших соседей, жадный алгоритм и алгоритм Кристофидеса, для получения решений, достаточно близких к оптимальному. Но после нахождения потенциального решения мы также покажем, как можно улучшить это решение с помощью локального поиска. Мы обсудим некоторые интересные алгоритмы для улучшения маршрутов, включая 2-оптимальные, случайные перестановки и 3-оптимальные улучшения. Наконец, мы покажем несколько остроумных способов анализа пространства поиска, включая имитацию отжига и оптимизацию муравьиной колонии. Удобная интерактивная таблица с описанием различных алгоритмов решения задачи коммивояжера:https://cse442-17f.github.io/Traveling-Salesman-Algorithms/- Многие результаты, полученные с помощью алгоритмов, основаны на выводах, представленных в данной статье:https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf Вот ссылка на репозиторий, содержащий код, использованный для создания анимации в этом видео:https://github.com/nipunramk/Reducible Оригинал видео:https://www.youtube.com/watch?v=GiDsjIBOVoA Автор:Reducible