Были ли курсы по задачам коммивояжера

Что проверяют

Вопрос про курсы на самом деле про то, знаете ли вы задачи комбинаторной оптимизации и отличаете ли точные методы от эвристик. Следом обычно дают прикладной поворот: как бы вы построили маршруты для курьеров на тысячу адресов.

Как отвечать

Сначала честно про обучение: был ли курс по исследованию операций, дискретной оптимизации или алгоритмам, где разбирали задачу коммивояжера. Если не было, так и скажите и переходите к тому, что знаете и где применяли. Примеры и цифры приводите только свои: пересказ чужого кейса вскрывается на первом уточнении.

Затем каркас по сути:

• постановка: найти кратчайший цикл, проходящий через все вершины по одному разу. Задача NP-трудная, полиномиальный точный алгоритм не известен;
• точные методы: перебор это O(n!), динамика Хелда и Карпа даёт O(n²·2ⁿ) по времени и O(n·2ⁿ) по памяти, на практике это пара десятков городов. Дальше работают метод ветвей и границ и целочисленное программирование, солвер Concorde точно решал экземпляры на десятки тысяч точек;
• приближения: для метрического случая алгоритм Кристофидеса гарантирует маршрут не длиннее 1,5 оптимума;
• эвристики: ближайший сосед для стартового решения, затем локальные улучшения 2-opt и 3-opt, эвристика Лина и Кернигана (реализация LKH), имитация отжига, генетические и муравьиные алгоритмы;
• инструменты: на Python Google OR-Tools с модулем маршрутизации, для небольших графов хватает приближённых алгоритмов из networkx.

В реальной логистике чистый TSP почти не встречается: нужны вместимость машин, временные окна, несколько курьеров. Это уже задача маршрутизации транспорта (VRP), и OR-Tools решает её из коробки. Нейросетевые подходы к TSP упомянуть можно, но в проде обычно выигрывают классические солверы.

Где спотыкаются

Называют задачу «нерешаемой». Она решается точно, просто время растёт экспоненциально, а на практике хватает хорошего приближения.

Предлагают ускорить перебор параллельными вычислениями. Против роста n! десяток ядер ничего не меняет.

Путают жадный алгоритм ближайшего соседа с приближённым алгоритмом с гарантией. У ближайшего соседа нет гарантии в постоянный множитель от оптимума.