Задача про подорожогов: NP-складність, на практиці

Проблема, яка здається простою, але не є такою

Задача про туристичного агента (Travelling Salesman Problem) полягає у знаходженні найкоротшого маршруту, який відвідує кожне місто рівно один раз і повертається до початкової точки. Для n міст існує (n-1)!/2 різних можливих турів (ділимо на 2 для напрямку, за звичаєм фіксуючи стартове місто), що росте так вибухово, що перевірка кожного туру методом грубої сили є реальною лише для десятка або кількох міст – вже 15 міст означає понад 43 мільярди турів. TSP є NP-складною: невідомо алгоритму, який би гарантовано вирішував кожний випадок оптимально за часом, що масштабується поліноміально з n, і більшість теоретиків складності вважають, що такого алгоритму не існує. Це не означає, що проблема безвихідна в практиці – це означає, що точні відповіді стають дорогими, тому реальні розв'язувачі обмінюють невелику кількість оптимальності на величезну кількість швидкості.

Найближчий сусід: швидкий, жадібний і доказово неточний

Найпростіший евристичний метод починається з будь-якого міста та повторно відвідує найближче місто, яке ще не було відвідане, поки всі міста не будуть відвідані, а потім повертається до стартового. Це виконується за O(n²) часу і є простим у реалізації, але це короткозоро; ранній жадібний вибір може залишити тур далеко від міст, які потрібно відвідати пізніше, і це можна довести, що тури найближчого сусіда можуть бути в будь-якому випадку гіршими за оптимальні в найгіршому випадку. На типових макетах міст він приземляється на 20–30% вище за довжину оптимального туру — це корисний відправний пункт, а не остаточна відповідь.

2-opt: розв’язування перетинів ребер

2-opt приймає будь-який маршрут і повторно шукає пари ребер, які перетинаються або можуть бути замінені, щоб скоротити загальну довжину: видаляє дві ребра, з’єднує два отримані сегменти шляху іншим способом і зберігає зміни, якщо вони скорочують маршрут.

Для кожної пари ребер (i, i+1) та (j, j+1) у маршруті, i < j: newLength = довжина з сегментом [i+1 .. j] перевернутим якщо newLength < currentLength: застосовує перевертання повторюється до тих пір, поки не існує покращувального обміну (локальний оптимум). Застосовується поверх старту найближчого сусіда, 2-opt зазвичай закриває більшу частину цього прогалу 20–30%, часто потрапляючи в межах кількох відсотків від оптимального на помірних розмірах. Його слабкість полягає в тому, що це локальний пошук: він зупиняється після першого маршруту, де жодне 2-opt обмін не допомагає, що не обов’язково є глобальним оптимумом — воно може бути застряглим у мінімальному місцезнаходженні, оточеному гіршими маршрутами в кожному напрямку, доступному через 2-opt.]

for each pair of edges (i, i+1) and (j, j+1) in the tour, i < j:
  newLength = length with segment [i+1 .. j] reversed
  if newLength < currentLength: apply the reversal
repeat until no improving swap exists (a local optimum)

Симульоване annealing: навмисне уникнення локальних оптимумів

Симульоване annealing (Kirkpatrick, Gelatt & Vecchi, 1983) позичає правило прийняття з статистичної механіки: на кожному кроці пропонується випадкова невелика зміна маршруту (наприклад, swap 2-opt), і вона приймається, якщо покращує маршрут — але також приймається з певною ймовірністю навіть якщо вона погіршує маршрут, де ця ймовірність залежить від того, наскільки гірше робить рух, та від параметра температури, що зменшується протягом виконання.

T = T0 while T > Tmin: candidate = randomSwap(currentTour) delta = length(candidate) - length(currentTour) if delta < 0 or random() < exp(-delta / T): currentTour = candidate // приймається, іноді навіть якщо гірше T *= coolingRate // наприклад, 0.995 за крок На ранніх етапах, коли T висока, алгоритм приймає багато погіршуючих рухів і ефективно досліджує широко, вистрибуючи з локальних оптимумів, які б ув’язнили 2-opt само по собі; коли T охолоджується, він приймає набагато менше погіршуючих рухів і встановлюється на поліпшення, більше схоже на простий 2-opt ближче до кінця виконання. Задостатньо повільного графіка охолодження симульоване annealing гарантовано збігається до глобального оптимуму в межах, де це можливо — гарантія, яка більш теоретична, ніж практична, оскільки за достатньо повільних графіків охолодження може зайняти більше часу, ніж brute force, але на практичних швидкостях охолодження воно надійно перевершує 2-opt само по собі на тій самій інстанції.

T = T0
while T > Tmin:
  candidate = randomSwap(currentTour)
  delta = length(candidate) - length(currentTour)
  if delta < 0 or random() < exp(-delta / T):
    currentTour = candidate      // accept, sometimes even if worse
  T *= coolingRate               // e.g. 0.995 per step

Які реальні перегони показує цей сайт

Спостереження за трьома гонщиками, які рухаються на одній міській карті, робить їхні компроміси видимими безпосередньо: алгоритм найближчого сусіда закінчується першим і найгірше, 2-opt закінчується другим і стабілізується в помітно розв’язаному, але статичному турі, а імітований annealing продовжує помітно змінювати свій тур навіть після того, як 2-opt зупиняється — це постійне блукання, іноді роблячи тур тимчасово довшим, є механізм, який дозволяє йому знаходити тури коротші, ніж досягають 2-opt самостійно.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Travelling Salesman і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.