​Задача коммивояжёра — точное решение через метод целочисленного линейного программирования

Если коротко, задача комивояжёра — это классический пул задач на поиск кратчайшего маршрута среди нескольких городов. Или маршрута по городу. В общем — это задачи о том, как принимать решения в ситуациях со множеством переменных.

Задачу коммивояжёра можно решить несколькими способами. Например, простым перебором. Но чем больше будет городов, тем медленнее будет расчёт. Уже на 10 городах мы получим миллионы выполнений цикла. А на 13 городах таких — уже несколько миллиардов, и компьютер может их считать неделю и даже больше.

Чуть более оптимальное решение — метод динамического программирования и метод ветвей и границ. Результат получается неплохой, но всё равно он слабоват.

Вот интересная статья, которая показывает, что точное решение этой задачи можно получить гораздо более оптимальным способом. Всё с понятными объяснениями и кодом на Python: https://habr.com/ru/post/711708/

#задачи