Проблемът на пътуващия търговец (TSP) — дефиниция, история и решения

Научете всичко за Проблема на пътуващия търговец (TSP): дефиниция, история и модерни алгоритми за оптимизация и практически решения.

Проблемът за пътуващия търговец (често наричан TSP) е класически алгоритмичен проблем в областта на компютърните науки и изследването на операциите. Той е насочен към оптимизацията. В този контекст по-добро решение често означава решение, което е по-евтино, по-кратко или по-бързо. TSP е математически проблем. Той се изразява най-лесно като граф, описващ местоположението на набор от възли.

Дефиниция

Формулиран накратко: имаме крайна група от градове (възли) и разстоянията (или разходите) между всяка двойка градове. Задачата е да се намери най-краткият възможен цикъл, който преминава през всеки град точно веднъж и се връща в началния град. В зависимост от условията има варианти:

• Симетричен TSP: разстоянието от A до B е същото като от B до A.
• Асиметричен TSP: разстоянията могат да са различни в двете посоки (например при посочени еднопосочни пътища).
• Метричен TSP: разстоянията удовлетворяват триъгълното неравенство (d(A,C) ≤ d(A,B)+d(B,C)).

История

Проблемът за пътуващия търговец е дефиниран през XIX в. от ирландския математик У. Р. Хамилтън и от британския математик Томас Къркман. Играта на Хамилтън "Икос" е била развлекателен пъзел, основан на намирането на хамилтонов цикъл. Общата форма на TSP изглежда е била изследвана за първи път от математици през 30-те години на ХХ век във Виена и в Харвард, по-специално от Карл Менгер. Менгер дефинира проблема, разглежда очевидния алгоритъм на грубата сила и наблюдава неоптималността на евристиката на най-близкия съсед:

Със задачата за пощальона (тъй като на практика този въпрос трябва да се решава от всеки пощальон, но и от много пътници) обозначаваме задачата да се намери за fiнално много точки, чиито разстояния по двойки са известни, най-краткият маршрут, свързващ точките. Разбира се, тази задача е решима чрез крайно много опити. Не са известни правила, които биха намалили броя на опитите под броя на пермутациите на дадените точки. Правилото, че първо трябва да се отиде от началната точка до най-близката точка, след това до най-близката до нея точка и т.н., по принцип не води до най-краткия маршрут.

Скоро след това Хаслер Уитни от Принстънския университет въвежда името "проблем на пътуващия търговец". Оттогава проблемът се превръща в едно от най-важните и изучавани предизвикателства в комбинаторната оптимизация.

Сложност и теоретични свойства

• TSP е труден проблем: оптимизационната версия е NP-трудна, а решението на въпрос "има ли тур с дължина ≤ K?" (решимият/решаемият вариант) е NP-пълен.
• Бруталното (изчерпателно) търсене изброява всички пермутации и има сложност O(n!), което става невъзможно при по-големи n.
• Има динамичен програмeн алгоритъм (класическият Bellman–Held–Karp), който решава проблема за време от порядъка O(n^2 2^n) и използва O(n 2^n) памет — значително по-добър от n!, но все още експоненциален.
• За метричния симетричен TSP съществува полиномиален алгоритъм за апроксимация с фактор 1.5 (алгоритъм на Christofides), докато в общия (несиметричен, не метричен) случай аппроксимации с постоянно ограничение не са възможни, освен ако P = NP.

Методи за решаване

Подходите за решаване на TSP могат да се групират в две големи категории: точни алгоритми (дават оптимално решение) и эвристики/метаевристики (дават близки до оптималното решения за по-кратко време).

Точни методи

• Брутална сила: проба на всички пермутации (само за много малки n).
• Динамично програмиране: Bellman–Held–Karp — O(n^2 2^n) време.
• Branch and bound: изрязване на част от дървото на решенията чрез граници за най-добрия възможен маршрут.
• Branch-and-cut / Integer programming: формулиране като цялочислено линейно програмиране и използване на разделяне по разрези (cutting planes). Съвременните имплементации успяват да решат много големи практически инстанции.
• Concorde: един от водещите точни решатели на TSP на практика, използва комбинация от cutting planes, branch-and-bound и други техники.

Евристики и метаевристики

• Най-близък съсед (Nearest Neighbor): бърз, но с лоши гаранции в най-лошия случай.
• 2-opt, 3-opt и k-opt: локални подобрения, които разбиват и пренареждат сегменти от тура, широко използвани за бързо усъвършенстване на решения.
• Lin–Kernighan: мощна и практично ефективна превъплътена k-opt стратегия.
• Критофидес (Christofides): дава гаранция 1.5 за метричния симетричен TSP.
• Метaевристики: генетични алгоритми, simulated annealing (симулирано отгряване), ant colony optimization (оптимизация чрез имитация на мравки) и др. — подходящи за големи практически инстанции, където точните методи са твърде бавни.

Приложения

Въпреки че формулировката на проблема е абстрактна, TSP има много практически приложения и служи като модел за по-сложни задачи:

• Планиране на маршрути и логистика (доставка, маршрутизация на камиони, пощенски услуги).
• Проектиране на печатни платки (оптимизиране на реда на пробиване на дупки).
• Оптимизация в производство и сглобяване.
• Биоинформатика — подзадачи в подравняване и реконструкция на ДНК (неколкократни подобни формулировки).
• Комуникационни мрежи и планиране на тестове.

Разширения и общи случаи

От TSP са произлезли и са изучени много разширения и по-общи проблеми, например:

• Vehicle Routing Problem (VRP): множество превозни средства, капацитети и ограничения на времето.
• Prize-collecting TSP, Orienteering: комбиниране на печалби и разходи при избор кои възли да бъдат посетени.
• Time-dependent TSP: разходите между градове зависят от времето на деня.

Защо TSP е важен

Проблемът на пътуващия търговец е важен както от теоретична, така и от приложна гледна точка: той е класическо доказателство за трудността на комбинаторните оптимизационни задачи и едновременно с това е практичен модел, който мотивира разработването на мощни алгоритми и софтуерни решения, използвани в индустрията. Усъвършенстването на техники за TSP често води до методи, приложими и за други трудни задачи в оптимизацията.

Въпроси и отговори

В: Какво представлява проблемът за пътуващия търговец?

Въпрос: Как се изразява TSP?

В: Кой пръв дефинира TSP?

В: Кой го е изучавал допълнително през 30-те години на ХХ век?

В: Какво въвежда Хаслер Уитни скоро след това?

В: Какво означава "по-добро решение" в този контекст?

Въпрос: Кой алгоритъм е бил смятан за очевиден от Менгер при изучаването на TSP?

Търсене по буква