Problem trgovskega potnika
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. V tem kontekstu boljša rešitev pogosto pomeni rešitev, ki je cenejša, krajša ali hitrejša. TSP je matematični problem. Najlažje ga izrazimo kot graf, ki opisuje lokacije množice vozlišč.
Problem potujočega prodajalca sta v 19. stoletju 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. Zdi se, da so splošno obliko TSP prvič preučevali matematiki v tridesetih letih 20. stoletja na Dunaju in na Harvardu, zlasti Karl Menger. Menger je opredelil problem, obravnaval očiten algoritem za reševanje z grobo silo in opazil, da hevristika najbližjega soseda ni 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.
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.
