Задача коммивояжера – это классическая задача оптимизации, которая заключается в поиске кратчайшего маршрута, проходящего через все заданные города ровно по одному разу с последующим возвратом в исходный город. Существует множество методов для решения задачи коммивояжера, которые можно условно разделить на два типа: Выбор метода зависит от конкретной задачи: Для реализации алгоритмов решения задачи коммивояжера можно использовать различные языки программирования и библиотеки: import networkx as nx # Создаем граф с весами ребер G = nx...

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