Problem potujočega prodajalca (TSP): definicija, optimizacija in zgodovina
Problem potujočega prodajalca (TSP): jasna definicija, ključne metode optimizacije in zanimiva zgodovina. Preberite vodnik za razumevanje problemov in rešitev.
Problem potujočega prodajalca (pogosto imenovan TSP) je klasičen algoritemski problem na področju računalništva in operacijskih raziskav. Osredotoča se na optimizacijo poti oziroma reda obiska točk (»mest« ali lokacij). V najpogostejši formalni različici so vhod podatki utežen, popoln graf, ki opisuje lokacije množice vozlišč (vsako vozlišče predstavlja mesto) in uteži med njimi predstavljajo razdalje ali stroške. Cilj je poiskati Hamiltonov cikel — krožno pot, ki obišče vsako vozlišče natanko enkrat in se vrne v izhodiščno vozlišče — z minimalno skupno utežjo.
Formalna opredelitev
Tipična formulacija: podan je nabor mest {1,…,n} in matrika stroškov c(i,j) za vsak par mest. TSP zahteva najti permutacijo π nad {1,…,n}, ki minimizira vsoto c(π(k),π(k+1)) za k=1…n (s π(n+1)=π(1)), torej najkrajši Hamiltonov cikel. Če je c(i,j)=c(j,i) govorimo o simetričnem TSP; če to ne velja, je problem asimetričen. Posebna podrazličica je metrični TSP, kjer uteži izpolnjujejo trikotno neenakost (c(i,j) ≤ c(i,k)+c(k,j)).
Zgodovina in zgodnji prispevki
Koreni problema segajo v 19. stoletje: problem sta opredelila irski matematik W. R. Hamilton in britanski matematik Thomas Kirkman. Hamiltonova Ikozijska igra je bila rekreativna uganka, ki je temeljila na iskanju Hamiltonovega cikla. Splošno obliko TSP so sistematično preučevali matematiki v 20. stoletju — v tridesetih letih so se z vprašanjem ukvarjali tudi na Dunaju in na Harvardu, med drugim Karl Menger, ki je opredelil problem, predstavil očiten brutosilogoritem in opozoril, da hevristika najbližjega soseda ni nujno optimalna:
S problemom sporočevalca (ker naj bi v praksi to vprašanje reševal vsak poštar, vsekakor pa tudi številni potniki) označujemo nalogo, da za fizično veliko točk, katerih parne razdalje so znane, najdemo najkrajšo pot, ki povezuje te točke. Seveda je ta naloga rešljiva s koničnim številom poskusov. Pravil, ki bi število poskusov potisnila pod število permutacij danih točk, ne poznamo. Pravilo, da je treba najprej iti od izhodiščne točke do najbližje točke, nato do točke, ki je tej najbližja, itd., na splošno ne daje najkrajše poti.
Hassler Whitney na Univerzi Princeton je kmalu zatem uvedel ime problem potujočega prodajalca.
Računska zahtevnost
Odločitvena različica problema ("ali obstaja pot z dolžino ≤ K") je NP-popolna, optimizacijska različica pa je NP-težka. Posledica je, da po trenutnem znanju ni znanega polinomskega algoritma, ki bi vedno našel optimalno rešitev za splošne primere. Zaradi tega se v praksi uporabljajo kombinacije eksaktnih metod, aproksimacijskih algoritmov in heuristik.
Algoritmi za TSP
- Eksaktni algoritmi: preiskava vseh permutacij (bruto sila) ima časovno zahtevnost O(n!) in je uporabna le za zelo majhne n. Boljši eksaktni pristopi so dinamično programiranje (Held–Karp algoritem) z kompleksnostjo O(n^2 2^n) in metode veja-in-meje (branch-and-bound), rezalne ravnine (cutting planes) ter napredni komercialni reševalci (Concorde ipd.), ki uporabljajo kombinacijo teh tehnik.
- Aproksimacijski algoritmi: za metrični TSP obstajajo algoritmi z zagotovilom kvalitete rešitve; najbolj znan je Christofidesov algoritem, ki daje 1.5-approx (tj. rešitev ni slabša od 1.5-kratnika optimalne). Za asimetrični metrični primer so znane druge aproksimacije z večjim faktorjem.
- Hevristike in lokalno iskanje: v praksi se pogosto uporabljajo hitre, praktične metode brez teoretičnega optimalnostnega zagotovila: najbližji sosed, gradnja poteze po različni strategiji (greedy), izboljšave s 2-opt, 3-opt in Lin–Kernighan lokalnimi izboljšavami, genetski algoritmi, simulirano ohlajanje in tabu search. Te metode pogosto dajejo zelo dobre rešitve za velike instance v razumnem času.
Praktične aplikacije
TSP ni le teoretična igra — uporablja se v številnih realnih problemih in prilagoditvah, med njimi:
- optimizacija poti za dostavo in transport (logistika, dostavna vozila),
- načrtovanje proizvodnje in vrtanja v industriji (npr. minimiziranje premikov pri risanju ali vrtanju tiskanin),
- analiza in urejanje zaporedij v biologiji (posledice za probleme, kot je urejanje genetskih podatkov in sorodni problemi),
- telekomunikacije in načrtovanje omrežij (iskanje učinkovitih krožnih poti),
- razni kombinirani problemski modeli, kot je vehicle routing problem (VRP), ki razširja TSP z dodatnimi omejitvami.
Sklepne opombe
TSP je ena od temeljnih problemov optimizacije in teorije računanja: povezuje kombinatoriko, grafično teorijo, računsko kompleksnost in praktične metode optimizacije. Čeprav za splošni primer ni znan polinomski algoritem, so za mnoge praktične instance na voljo zelo zmogljivi eksaktni reševalci in heuristike, ki omogočajo reševanje velikih primerov z zadostno natančnostjo za industrijske potrebe.
Prodajalec želi obiskati vsa mesta A, B, C in D. Kako to najbolje storiti (najcenejše letalske vozovnice in najmanj časa za potovanje)?
Optimalna pot prodajalca, ki obišče 15 največjih mest v Nemčiji. Prikazana pot je najkrajša izmed 43 589 145 600 možnih poti.
William Rowan Hamilton
Navedba problema
Problem potujočega prodajalca opisuje prodajalca, ki mora potovati med N mesti. Zaporedje, v katerem to počne, ga ne zanima, dokler med potovanjem ne obišče vsakega od njih enkrat in konča tam, kjer je bil na začetku. Vsako mesto je povezano z drugimi bližnjimi mesti ali vozlišči z letali, cestami ali železnico. Vsaka od teh povezav med mesti ima eno ali več uteži (ali stroškov). Strošek opisuje, kako "težko" je prečkati ta rob na grafu, in je lahko podan na primer s ceno letalske ali železniške vozovnice, lahko pa tudi z dolžino roba ali časom, potrebnim za dokončanje prehoda. Prodajalec želi, da so stroški potovanja in razdalja, ki jo prepotuje, čim nižji.
Problem potujočega prodajalca je značilen za velik razred "težkih" optimizacijskih problemov, ki že leta zanimajo matematike in računalničarje. Najpomembneje je, da se uporablja v znanosti in tehniki. Pri izdelavi tiskanega vezja je na primer pomembno določiti najboljši vrstni red, v katerem bo laser izvrtal na tisoče lukenj. Učinkovita rešitev tega problema zmanjša proizvodne stroške proizvajalca.
Težavnost
Na splošno je problem potujočega prodajalca težko rešiti. Če obstaja način, kako ta problem razdeliti na manjše sestavne probleme, bodo ti vsaj tako zapleteni kot prvotni problem. Računalničarji temu pravijo NP-težki problemi.
To težavo so preučevali številni ljudje. Najlažja (in najdražja) rešitev je preprosto preizkusiti vse možnosti. Težava pri tem je, da je za N mest na voljo (N-1) faktorialnih možnosti. To pomeni, da je za samo 10 mest na voljo več kot 180 tisoč kombinacij (ker je začetno mesto določeno, lahko obstajajo permutacije za preostalih devet mest). Štejemo le polovico, saj ima vsaka pot enako pot v obratni smeri z enako dolžino ali stroški. 9! / 2 = 181 440
- Natančne rešitve problema je mogoče najti z algoritmi z vejami in omejitvami. To je trenutno mogoče za do 85.900 mest.
- Hevristični pristopi uporabljajo niz vodilnih pravil za izbiro naslednjega vozlišča. Ker pa so hevristične metode približki, ne dajejo vedno optimalne rešitve, čeprav lahko kakovostne dopustne hevristične metode najdejo uporabno rešitev v delčku časa, ki je potreben za popolno reševanje problema z grobo silo. Primer hevristike za vozlišče bi bil seštevek, koliko neobiskanih vozlišč je "blizu" povezanega vozlišča. To bi lahko prodajalca spodbudilo, da obišče skupino bližnjih vozlišč, ki so združena skupaj, preden se premakne na drugo naravno gručo v grafu. Glej algoritme Monte Carlo in algoritme Las Vegas
Vprašanja in odgovori
V: Kaj je problem potujočega prodajalca?
O: Problem potujočega prodajalca (TSP) je klasičen algoritemski problem na področju računalništva in operacijskih raziskav. Osredotoča se na optimizacijo, pri čemer boljše rešitve pogosto pomenijo cenejše, krajše ali hitrejše rešitve.
V: Kako je izražen TSP?
O: TSP se najlažje izrazi kot graf, ki opisuje lokacije množice vozlišč.
V: Kdo je prvi opredelil TSP?
O: Problem potujočega prodajalca sta v 19. stoletju opredelila irski matematik W. R. Hamilton in britanski matematik Thomas Kirkman.
V: Kdo ga je podrobneje preučeval v tridesetih letih 20. stoletja?
O: V tridesetih letih 20. stoletja sta ga nadalje preučevala matematika Karl Menger na Dunaju in Harvardu.
V: Kaj je kmalu zatem uvedel Hassler Whitney?
O: Hassler Whitney na Univerzi Princeton je kmalu po definiciji uvedel ime "problem potujočega prodajalca".
V: Kaj v tem kontekstu pomeni "boljša rešitev"?
O: V tem kontekstu boljša rešitev pogosto pomeni rešitev, ki je cenejša, krajša ali hitrejša.
V: Kateri algoritem je Menger pri preučevanju TSP označil za samoumevnega?
O: Menger je pri preučevanju TSP menil, da je očiten algoritem grobe sile, in opazil, da uporaba hevristike najbližjega soseda ne daje vedno optimalnih rezultatov.
Iskati