Problem komiwojażera
The Traveling Salesman Problem (często nazywany TSP) jest klasycznym problemem algorytmicznym w dziedzinie informatyki i badań operacyjnych. Jest on ukierunkowany na optymalizację. W tym kontekście, lepsze rozwiązanie często oznacza rozwiązanie tańsze, krótsze lub szybsze. TSP jest problemem matematycznym. Najłatwiej wyrazić go w postaci wykresu opisującego lokalizację zbioru węzłów.
Problem wędrownego sprzedawcy został zdefiniowany w XIX wieku przez irlandzkiego matematyka W. R. Hamiltona i brytyjskiego matematyka Thomasa Kirkmana. Hamilton's Icosian Game była rekreacyjną zagadką opartą na znalezieniu cyklu Hamiltona. XX wieku w Wiedniu i na Harvardzie, w szczególności przez Karla Mengera. Menger definiuje problem, rozważa oczywisty algorytm brutalnej siły i obserwuje nieoptymalność najbliższego otoczenia heurystycznego:
Przez problem posłańca rozumiemy (ponieważ w praktyce pytanie to powinno być rozwiązane przez każdego listonosza, a w każdym razie także przez wielu podróżnych) zadanie znalezienia, dla dokładnie wielu punktów, których odległości parami są znane, najkrótszej trasy łączącej te punkty. Oczywiście, problem ten można rozwiązać za pomocą skończonej liczby prób. Nie są znane zasady, które zepchnęłyby liczbę prób poniżej liczby permutacji danych punktów. Zasada, że najpierw należy przejść z punktu startowego do najbliższego punktu, a następnie do najbliższego itd., generalnie nie daje najkrótszej trasy.
Hassler Whitney z Princeton University wprowadził wkrótce potem problem z nazwiskiem podróżującego sprzedawcy.
Sprzedawca chce odwiedzić wszystkie miasta, A, B, C i D. Jaki jest najlepszy sposób, aby to zrobić (najtańsze bilety lotnicze, i minimalny czas podróży)?
Optymalna droga handlowca odwiedzającego 15 największych miast w Niemczech. Pokazana trasa jest najkrótszą z 43 589 145 600 możliwych.
William Rowan Hamilton
Przedstawienie problemu
The Travelling Salesman Problem opisuje sprzedawcę, który musi podróżować między N miastami. Kolejność, w jakiej to robi, jest czymś, co go nie interesuje, o ile odwiedza każdego z nich raz w trakcie podróży i kończy tam, gdzie był na początku. Każde miasto jest połączone z innymi bliskimi miastami, węzłami, samolotami, drogą lądową lub kolejową. Do każdego z tych połączeń między miastami dołączony jest jeden lub więcej ciężarków (lub kosztów). Koszt opisuje, jak "trudno" jest przeciągnąć tę krawędź na wykresie i może być podany np. przez koszt biletu lotniczego lub kolejowego, a może przez długość tej krawędzi, lub czas potrzebny do ukończenia trawersy. Sprzedawca chce, aby zarówno koszty podróży, jak i odległość, jaką pokonuje, były jak najniższe.
Problem podróżnych sprzedawców jest typowy dla dużej klasy "trudnych" problemów z optymalizacją, które od lat intrygują matematyków i informatyków. Co najważniejsze, ma on zastosowanie w nauce i inżynierii. Na przykład, w produkcji płytek drukowanych, ważne jest, aby określić najlepszą kolejność, w której laser będzie wiercił tysiące otworów. Skuteczne rozwiązanie tego problemu zmniejsza koszty produkcji ponoszone przez producenta.
Trudność
Ogólnie rzecz biorąc, problem podróżnych sprzedawców jest trudny do rozwiązania. Jeśli istnieje sposób, aby rozbić ten problem na mniejsze problemy z komponentami, będą one co najmniej tak skomplikowane jak oryginalne. To jest to, co informatycy nazywają problemami NP-hard.
Wiele osób badało ten problem. Najłatwiejszym (i najdroższym) rozwiązaniem jest po prostu spróbować wszystkich możliwości. Problem polega na tym, że dla N miast masz (N-1) możliwości czynnikowe. Oznacza to, że tylko dla 10 miast jest ponad 180 tys. kombinacji do wypróbowania (od momentu zdefiniowania miasta początkowego, na pozostałych 9 mogą być permutacje). Liczymy tylko połowę, ponieważ każda trasa ma taką samą trasę na odwrót o tej samej długości lub koszcie. 9! / 2 = 181 440
- Dokładne rozwiązania problemu można znaleźć za pomocą algorytmów branżowych i powiązanych. Obecnie jest to możliwe nawet dla 85 900 miast.
- Podejścia heurystyczne wykorzystują zestaw zasad przewodnich przy wyborze kolejnego węzła. Ponieważ jednak heurystyka skutkuje przybliżeniami, nie zawsze daje optymalne rozwiązanie, chociaż wysokiej jakości heurystyka dopuszczalna może znaleźć użyteczne rozwiązanie w ułamku czasu potrzebnego na pełną siłę oddziaływania problemu. Przykładem heurystyki dla danego węzła byłoby zsumowanie, ile niesprawdzonych węzłów znajduje się "blisko" połączonego węzła. Mogłoby to zachęcić sprzedawcę do odwiedzenia grupy węzłów znajdujących się blisko siebie, zgrupowanych razem przed przejściem do innego naturalnego zgrupowania na wykresie. Zobacz algorytmy Monte Carlo i algorytmy Las Vegas
Pytania i odpowiedzi
P: Co to jest problem podróżującego komiwojażera?
A: Problem podróżującego komiwojażera (TSP) jest klasycznym problemem algorytmicznym w dziedzinie informatyki i badań operacyjnych. Koncentruje się na optymalizacji, przy czym lepsze rozwiązania oznaczają często rozwiązania tańsze, krótsze lub szybsze.
P: Jak wyraża się TSP?
O: TSP najłatwiej wyrazić jako graf opisujący położenie zbioru węzłów.
P: Kto pierwszy zdefiniował TSP?
O: Problem podróżującego komiwojażera został zdefiniowany w XIX wieku przez irlandzkiego matematyka W. R. Hamiltona i brytyjskiego matematyka Thomasa Kirkmana.
P: Kto badał go dalej w latach 30-tych?
O: W latach trzydziestych XX wieku badali ją matematycy Karl Menger w Wiedniu i na Harvardzie.
P: Co wprowadził wkrótce potem Hassler Whitney?
O: Hassler Whitney z Uniwersytetu Princeton wprowadził nazwę "problem wędrującego komiwojażera" wkrótce po jego zdefiniowaniu.
P: Co oznacza w tym kontekście "lepsze rozwiązanie"?
O: W tym kontekście lepsze rozwiązanie często oznacza rozwiązanie, które jest tańsze, krótsze lub szybsze.
P: Jaki algorytm został uznany przez Mengera za oczywisty podczas badania TSP?
O: Menger podczas badania TSP uznał za oczywisty algorytm brute-force i zauważył, że stosowanie heurystyki najbliższego sąsiada nie zawsze daje optymalne wyniki.
