Проблем на пътуващия търговец

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

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

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

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

Търговец иска да посети всички градове - A, B, C и D. Кой е най-добрият начин да го направи (най-евтини самолетни билети и минимално време за пътуване)?

Оптимален маршрут на търговец, който посещава 15-те най-големи града в Германия. Показаният маршрут е най-краткият от 43 589 145 600 възможни маршрута.

Уилям Роуън Хамилтън

Поставяне на проблема

Задачата за пътуващия търговец описва търговец, който трябва да пътува между N града. Редът, в който го прави, не го интересува, стига да посети всеки от тях по веднъж по време на пътуването си и да завърши там, където е бил в началото. Всеки град е свързан с други близки градове, или възли, чрез самолети, пътища или железници. Към всяка от тези връзки между градовете са прикрепени една или повече тежести (или разходи). Цената описва колко "трудно" е да се премине през това ребро на графа и може да бъде дадена например чрез цената на самолетен или железопътен билет, или може би чрез дължината на реброто, или времето, необходимо за извършване на обхода. Търговецът иска да поддържа възможно най-ниски разходи за пътуване, както и разстоянието, което изминава.

Проблемът за пътуващия продавач е типичен за голям клас "трудни" оптимизационни проблеми, които от години интригуват математиците и компютърните специалисти. Най-важното е, че той има приложения в науката и техниката. Например при производството на платки е важно да се определи най-добрият ред, в който лазерът ще пробие хиляди дупки. Ефективното решение на този проблем намалява производствените разходи на производителя.

Трудност

По принцип задачата за пътуващия търговец е трудна за решаване. Ако има начин тази задача да се разбие на по-малки съставни задачи, компонентите ще бъдат поне толкова сложни, колкото и първоначалната задача. Това е, което компютърните специалисти наричат NP-трудни проблеми.

Много хора са изследвали този проблем. Най-лесното (и най-скъпото решение) е просто да се опитат всички възможности. Проблемът с това е, че за N града имате (N-1) факторни възможности. Това означава, че само за 10 града има над 180 хил. комбинации за изпробване (тъй като началният град е определен, може да има пермутации на останалите девет). Отчитаме само половината, тъй като всеки маршрут има равен маршрут в обратна посока със същата дължина или цена. 9! / 2 = 181 440

Точните решения на задачата могат да бъдат намерени с помощта на алгоритми с разклонения и граници. В момента това е възможно за до 85 900 града.
Евристичните подходи използват набор от водещи правила за избор на следващия възел. Но тъй като евристиките водят до приближения, те невинаги дават оптималното решение, въпреки че висококачествените допустими евристики могат да намерят полезно решение за част от времето, необходимо за пълно грубо решаване на проблема. Пример за евристика за възел би било сумиране на това колко непосещавани възела са "близо" до свързан възел. Това би могло да насърчи търговеца да посети група близки възли, групирани заедно, преди да премине към друг естествен клъстер в графа. Вижте Алгоритми Монте Карло и Алгоритми Лас Вегас

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

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

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

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

О: TSP се изразява най-лесно като граф, описващ местоположението на набор от възли.

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

О: Проблемът за пътуващия търговец е дефиниран през XIX век от ирландския математик У. Р. Хамилтън и от британския математик Томас Къркман.

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

О: През 30-те години на ХХ в. математиците Карл Менгер от Виена и Харвард го изучават допълнително.

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

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

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

О: В този контекст "по-добро решение" често означава решение, което е по-евтино, по-кратко или по-бързо.

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

О: Менгер е смятал за очевиден алгоритъм за груба сила, когато е изучавал TSP, и е забелязал, че използването на евристиката на най-близкия съсед не винаги дава оптимални резултати.