Math
Задача комівояжера
Маршрут, що коротшає на твоїх очах — жадібний, 2-opt, що розплутує ребра по одному, відпал, що перелазить через стіну, — проти точного оптимуму для тринадцяти міст і перебору всіх маршрутів для восьми.
Що відбувається
Порівняйте будівництво найближчого сусіда, поліпшення 2-opt і симульоване відновлення в тих самих містах. A 2-opt локальний оптимум не має покращуючого обміну двома ребрами; це не обов'язково має бути найкоротший тур у світі. Відпалювання іноді приймає довші тури, щоб уникнути місцевих мінімумів, не гарантуючи оптимальності в кінцевому запуску.
Мінімальний діапазон дерева є нижньою межею на кожному турі. Для цих евклідівських відстаней, подвоєння дерева і скорочення повторних відвідин доводить, що оптимальний маршрут найчастіше вдвічі більше мінімального дерева. Ця межа стосується оптимальної і відповідної деревоподібної конструкції; вона не обмежує кожного жадібного або середнього мандрівника.
Маленька точна сцена використовує динамічне програмування Held-Karp над підмножинами, з часом 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-опт: ребра (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-опт на ньому: 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-опт із 50 випадкових маршрутів (тасування Фішера–Йейтса на зернах 100 …): 7 досягають його, найгірший 1.0789 ×, середній 1.0678 ×
повний перебір: кожна перестановка 1 … N − 1 у лексикографічному порядку, кожен маршрут один раз (перший < останній); 8 міст, зерно 3: 2520 маршрутів, найкращий 5.2175 = Хелд–Карп, найдовший 11.9462, середній 9.1055
