Сравнение подходов для TSP на $20$ вершинах (кратко, с оценками).
1) Динамическое программирование по подмножествам (Held–Karp)
- Точность: точный метод — всегда даёт оптимум.
- Время: асимптотика $O(n^2{2}^n)$. Для $n=20$: примерно $20^2\cdot 2^{20}\approx 419,430,400$ элементарных операций (порядок $10^8$–$10^9$ операций) — обычно выполнимо за доли секунды–несколько секунд на современном CPU.
- Память: $O(n{2}^n)$. Для $n=20$: $20\cdot 2^{20}=20,971,520$ состояний; при хранении стоимости в 8 байт — ≈$167,772,160$ байт ≈$160$ MiB.
- Комментарий: предсказуемые ресурсы; хорош для одиночных задач при доступной памяти.
2) Ветвление и границы (Branch & Bound, B&B)
- Точность: точный метод при полном обходе; на практике даёт оптимум если успеет завершиться.
- Время: худший случай экспоненциальный; на практике с хорошими нижними/верхними границами и эвристикой часто значительно быстрее DP и может решать $n=20$ за доли секунды–секунды. Однако для «трудных» экземпляров возможен резкий рост времени.
- Память: зависит от числа одновременно держимых узлов (может быть от малых значений до экспоненциального). Практически — десятки МБ при разумном ограничении.
- Ключевые приёмы: сильная начальная верхняя граница (Lin–Kernighan / 2-opt), хорошая нижняя граница (редуцированное 1-tree), приоритизация ветвей, отсечение по относительной погрешности.
3) Метаэвристики (генетические алгоритмы, simulated annealing и др.)
- Точность: нет гарантий оптимальности; на практике для $n=20$ часто дают решения вблизи оптимума (типично $1\%$–$5\%$ от оптимума, часто лучше — <$1\%$, особенно с локальным улучшением).
- Время: гибкое контрольируемое — от миллисекунд до минут в зависимости от числа итераций/популяции. Очень быстрые при малых итерациях.
- Память: малая — $O(n)$ на решение; при популяции размера $p$ — $O(pn)$. Пример: $p=100\Rightarrow 100\cdot 20=2000$ записей.
- Комментарий: хороши для большого числа инстансов или жёсткого лимита времени; легко параллелятся, дают хорошие стартовые решения для точных методов.
Рекомендованная смешанная стратегия для промышленных ограничений (временной лимит, ограниченная память, требуемая надёжность)
1. Требования и ресурсы: явно задайте $T_{max}$ (время), $M_{max}$ (память) и приемлемую относительную погрешность $\epsilon$. Остановка по правилу $\frac{UB-LB}{UB}\le \epsilon$, где $UB$ — текущая лучшая стоимость, $LB$ — нижняя граница.
2. Быстрый старт (0–10% бюджета времени)
- Запустите быстрый эвристический поиск: nearest neighbour + 2-opt + Lin–Kernighan (LK). Получите $U{B}_0$. Очень мало памяти, быстро.
3. Попытка точного решения (если память и время позволяют)
- Если $M_{max}\ge$ память для DP (для $n=20$ это ≈$160$ MiB), и вы хотите гарантированный оптимум — выполните Held–Karp DP (точный) и завершите.
- Иначе запустите B&B с инциализацией верхней границы $U{B}_0$ и сильной нижней границей (редуцированное 1-tree). Дайте B&B ограничение времени $T_b\le T_{max}$. При достижении $T_b$ верните лучший $UB$.
4. Гибрид при жёстких временных лимитах
- Если $T_{max}$ очень мал: используйте метаэвристику (GA или SA) с локальным улучшением (2-opt / LK) для получения качественных решений; параллельно запускайте лёгкий B&B/ограниченный поиск, чтобы попытаться улучшить инциндент.
- Для многократных инстансов: поддерживайте пул хороших решений (GA) и используйте их как старт для B&B/локального поиска на каждом новом экземпляре.
5. Параллелизация и инженерные приёмы
- B&B: параллелить ветвление, синхронизировать общий лучший $UB$.
- GA/SA: натурально параллельны (популяция/мутаторы).
- Сжатие DP: если память критична, храните только необходимые подмножества или используйте внешнюю память / mmap; при $n=20$ чаще не нужно.
- Журналирование прогресса: фиксируйте $UB$, $LB$, относительную погрешность и оставшееся время, чтобы можно было принять решение остановки.
Краткая рекомендация по выбору
- Нужен гарантированный оптимум и память доступна: Held–Karp DP для $n=20$.
- Нужен оптимум, память ограничена, но допустимо время: B&B с сильными границами, стартуя с LK.
- Жёсткий временной лимит или множество задач: метаэвристики + локальный поиск; при возможности запуск ограниченного B&B в фоне для улучшения/доказывания оптимальности.
Если нужно, могу дать конкретный пайплайн с параметрами (популяция, время на этапы, критерии остановки) под ваши $T_{max}$, $M_{max}$ и целевую $\epsilon$.