Задача коммивояжёра (Traveling Salesman Problem, TSP) — одна из самых известных NP-сложных задач в комбинаторной оптимизации. Её суть заключается в поиске кратчайшего маршрута, проходящего через все заданные города ровно по одному разу с возвратом в исходную точку. В этой статье мы рассмотрим несколько подходов к решению TSP на Python, включая точные и эвристические методы.
1. Точное решение: полный перебор
Для небольшого числа городов (N ≤ 10) можно использовать метод полного перебора всех возможных маршрутов. Хотя алгоритм имеет факториальную сложность O(N!), он гарантирует нахождение оптимального решения.
Пример кода
2. Жадный алгоритм "Ближайший сосед"
Для больших N применяют эвристики. Один из простейших методов — жадный алгоритм, который на каждом шаге выбирает ближайший непосещённый город. Решение может быть субоптимальным, но работает за O(N²).
Реализация
3. Генетический алгоритм (используем библиотеку mlrose)
Для сложных случаев с десятками городов подходят метаэвристики. Установите библиотеку:
Пример кода
4. Визуализация маршрута
Используем matplotlib для отображения пути:
Сравнение методов
Метод Точность Скорость Рекомендуемый N
Полный перебор Точный O(N!) ≤ 10
Жадный алгоритм Субоптимальный O(N²) Любой
Генетический алгоритм Приближённый Зависит от параметров ≥ 20
Заключение
Задача коммивояжёра находит применение в логистике, проектировании микросхем и биоинформатике. Выбор метода зависит от размера задачи и требований к точности. Для небольших данных используйте полный перебор, для крупных — эвристики или метаэвристики. Код из статьи можно адаптировать для реальных данных, заменив матрицу расстояний на актуальные значения.