Задача коммивояжёра
Задача коммивояжера. Точное решение — метод целочисленного линейного программирования Мы уже пробовали решать точно задачу коммивояжёра методом динамического программирования и методом ветвей и границ. Результат неплох, но слабоват. В этой статье мы увидим, что точное решение ближе, чем принято считать. Будем использовать метод целочисленного программирования, который является частным случаем линейного программирования, который в свою очередь является подклассом математического программирования.
Задача коммивояжёра — история и теория
Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Есть N городов, связанных дорогами. Как помочь коммивояжёру проложить наиболее короткий/выгодный/дешёвый маршрут между этими городами, чтобы посетить каждый город хотя бы по одному разу и вернуться в исходную точку? Многие, изучающие computer science, знают о существовании этой задачи как одной из самых известных задач на графах. Все знают, что эта задача NP-полная и нерешаема в общем виде на современных компьютерах...