Задача коммивояжёра на практике: быстрые эвристики вместо полного перебора

Задача коммивояжёра проста в формулировке: пройти все точки и вернуться назад с минимальным маршрутом. Но полный перебор взрывается уже на небольшом числе городов. В практических задачах важнее не идеальное решение, а хороший маршрут за ограниченное время.

Стартовая эвристика

Nearest neighbor — простой baseline: выбираем ближайшую ещё не посещённую точку. Решение строится быстро, но часто далеко от оптимального. Тем не менее это хорошая стартовая точка для улучшений.

2-opt

2-opt берёт маршрут и пытается улучшить его перестановками рёбер. Если два ребра пересекаются, их можно заменить так, чтобы путь стал короче. Метод прост и часто даёт большой выигрыш.

Ограничение времени

Для production-задачи важно задать time budget: например, улучшать маршрут не больше 5 секунд. Алгоритм должен уметь вернуть лучшее найденное решение, а не падать без результата.

Проверка качества

Нужны метрики: длина маршрута, время расчёта, стабильность результата, качество относительно baseline и поведение на случайных и реальных данных.

Итог

TSP показывает важный инженерный принцип: оптимальное решение не всегда нужно. Часто достаточно хорошей эвристики, понятного baseline и контроля времени.