Почему вариантов становится так много
Если нужно посетить несколько городов и вернуться в исходный, маршрут задаётся порядком посещения. При добавлении каждого города вариантов становится резко больше: для десяти городов возможны миллионы порядков, хотя многие из них отличаются лишь направлением обхода и дают ту же длину.
Поэтому перебрать все маршруты и выбрать самый короткий быстро становится непрактично. В задаче коммивояжёра важно не только найти путь, но и сравнить его со всеми возможными конкурентами — или доказать, что остальные не могут быть лучше.
Хороший маршрут — ещё не доказанный минимум
Приближённые методы строят маршрут постепенно: например, выбирают ближайший следующий город, а затем переставляют отдельные участки пути, если это сокращает поездку. Такие приёмы часто быстро дают полезный результат, но не гарантируют, что где-то нет более короткого варианта.
Чтобы подтвердить оптимальность, точный алгоритм должен исключить все маршруты, способные улучшить найденный. Он не всегда перебирает их по одному: может оценить целую группу вариантов и отбросить её, если даже самый благоприятный исход в этой группе хуже уже найденного маршрута. Но в сложных случаях таких групп остаётся очень много.
Цена уверенности
На небольшом наборе городов точный расчёт вполне реален; для крупных задач помогают структура дорог, удачные границы и специальные алгоритмы. Однако для общей задачи нет известного метода, который гарантированно находил бы точный минимум за время, растущее достаточно медленно с числом городов.
На практике выбор зависит от цены ошибки. Для курьера или производственного расписания маршрут, который почти оптимален и найден быстро, может быть полезнее математически безупречного ответа, ожидание которого слишком долго. Найти короткий путь — значит предъявить удачный вариант; доказать кратчайший — значит убедиться, что ни один из остальных не лучше.
