Задача коммивояжёра: когда достаточно хорошо лучше идеального

Используйте код «reducible», чтобы получить CuriosityStream менее чем за 15 долларов в год!
Задача коммивояжёра (TSP) — одна из самых известных задач в информатике. В этом видео мы подробно расскажем, почему эта задача представляет такую ​​сложность для специалистов по информатике, и рассмотрим некоторые хитроумные методы её решения. Мы начнём с того, что покажем, почему все решения методом полного перебора и даже оптимизации для получения точных решений не могут быть надёжно использованы для больших объёмов задач. Затем мы обсудим некоторые эвристические подходы, такие как метод ближайших соседей, жадный алгоритм и метод Кристофидеса, для получения решений, достаточно близких к оптимальному. Но после нахождения потенциального решения мы также покажем, как можно улучшить это решение с помощью локального поиска. Мы обсудим несколько интересных алгоритмов для улучшения маршрутов, включая 2-opt, случайную замену и 3-opt. Наконец, мы покажем несколько интересных способов анализа пространства поиска, включая имитацию отжига и оптимизацию муравьиной колонии. Главы: 0:00 Введение 1:27 Определение задачи 2:27 Почему найти оптимальное решение практически невозможно 5:35 Эвристика ближайшего соседа 6:59 Нижняя граница задачи коммивояжёра 11:03 Жадная эвристика 12:06 Алгоритм Кристофидеса 16:11 Спонсор (CuriosityStream) 17:15 Улучшения тура 21:13 Имитация отжига 24:14 Оптимизация муравьиной колонии 28:25 Заключение Анимации созданы совместно Нипуном Рамакришнаном и Хесусом Расконом. Ссылки: Интерактивное видео о различных алгоритмах TSP:
Многие результаты работы алгоритмов основаны на данных из этой статьи:
Это видео было бы невозможно без библиотеки с открытым исходным кодом manim, созданной 3blue1brown и поддерживаемой сообществом Manim. Разработчики сообщества Manim. (2022). Manim – фреймворк математической анимации (версия v0.11.0) [Программное обеспечение].
Вот ссылка на репозиторий с кодом, использованным для создания анимаций в этом видео:
Музыка в этом видео принадлежит Хесусу Раскону и Ааскашу Ганди. Соцсети: Patreon:   / reducible   Twitter:   / reducible20   Большое спасибо сообществу пользователей Patreon, которые поддерживают этот канал. Особая благодарность следующим пользователям Patreon: Анджела Арсич Андреас Адам Држинек Бёрт Хамбург Брайан Клотье Юджин Тулушев kerrytazi Мэтт Кью Взаимная информация Рэм Кью Ричард Уэллс Себастьян Гамбоа Уинстон Дюран Зак Лэндис