Math
Задача коммивояжёра
Маршрут, который укорачивается у тебя на глазах — жадный, 2-opt, распутывающий рёбра по одному, отжиг, перелезающий через стену, — против точного оптимума для тринадцати городов и перебора всех маршрутов для восьми.
Что происходит
Сравните построение маршрута по ближайшему соседу, улучшение 2-opt и имитацию отжига на одних городах. Локальный оптимум 2-opt не допускает улучшающего обмена двух рёбер, но не обязан быть глобально кратчайшим маршрутом. Отжиг иногда принимает более длинные маршруты, чтобы выйти из локального минимума, однако конечный запуск не гарантирует оптимума.
Минимальное остовное дерево — нижняя граница длины любого маршрута. Для этих евклидовых расстояний удвоение дерева с сокращением повторных посещений доказывает, что оптимальный маршрут не длиннее удвоенного минимального остова. Эта граница относится к оптимуму и подходящему построению по дереву, а не к любому жадному или промежуточному маршруту.
В небольшой точной задаче используется динамическое программирование Хелда — Карпа по подмножествам: O(N²·2^N) операций вместо перебора всех перестановок. Сцена с восемью городами может перебрать все различные маршруты. Точные алгоритмы не обязаны просматривать большинство перестановок, но для общей задачи коммивояжёра полиномиальный точный алгоритм неизвестен. Сравните найденные эвристиками маршруты с точным эталоном там, где он доступен.
Уравнения модуля
Уравнения
города: N точек в [−1, 1]² от общего генератора (зерно 3); длина маршрута L = Σ |c_k − c_{k+1}| по циклу; (N − 1)!/2 различных маршрутов: 2520 для 8, 2.4·10^8 для 13, 1.0·10^46 для 40
жадный алгоритм: из города 0, всегда в ближайший непосещённый (ничьи решаются по индексу); 12.8105 для сорока городов
2-opt: рёбра (a, b) и (c, d), где a раньше c на маршруте; Δ = |ac| + |bd| − |ab| − |cd|; первая в порядке просмотра пара с Δ < 0 распутывается разворотом отрезка b … c; повторяем, пока такие есть: 16 распутываний, 10.5850 - стена (локальный оптимум)
отжиг: случайная пара (i, j), i < j, j − i ≥ 2; принимается, если Δ ≤ 0, иначе с вероятностью exp(−Δ/T); T₀ = 0.3, T ← 0.9997 T на каждом шаге, 20 000 шагов; зерно 6: лучший 10.4954, принято 462, ухудшающих 231; 2-opt к нему: 10.2673
оценка: MST ≤ L для каждого маршрута (маршрут без одного ребра является остовным деревом), а обход удвоенного дерева даёт L_opt ≤ 2·MST; MST = 8.4480 для сорока точек (дерево из GraphTheory, тот же бросок кубика); 10.2673 / 8.4480 = 1.215
Хелд–Карп: dp[S, k] = кратчайший путь из 0 через множество S, заканчивающийся в k; dp[S + k, k] = min по j из S от dp[S, j] + |jk|; 2^N·N² шагов; 13 городов, зерно 8: оптимум 7.4710, маршрут 0 7 1 3 12 6 8 10 5 4 11 2 9; 2-opt из 50 случайных маршрутов (перемешивание Фишера–Йетса на зёрнах 100 …): 7 достигают его, худший 1.0789 ×, средний 1.0678 ×
перебор: все перестановки 1 … N − 1 в лексикографическом порядке, каждый маршрут по одному разу (первый < последний); 8 городов, зерно 3: 2520 маршрутов, лучший 5.2175 = Хелд–Карп, самый длинный 11.9462, средний 9.1055
