Reisijate müügimehe probleem

Reisijate müügimehe probleem (sageli ka TSP) on klassikaline algoritmiline probleem arvutiteaduse ja operatsioonide uurimise valdkonnas. See keskendub optimeerimisele. Selles kontekstis tähendab parem lahendus sageli lahendust, mis on odavam, lühem või kiirem. TSP on matemaatiline probleem. Seda on kõige lihtsam väljendada graafina, mis kirjeldab sõlmede hulga asukohti.

Reisijate probleemi määratlesid 1800. aastatel iiri matemaatik W. R. Hamilton ja briti matemaatik Thomas Kirkman. Hamiltoni Icosian Game oli meelelahutuslik mõistatus, mis põhines Hamiltoni tsükli leidmisel. TSP üldvormi näib olevat esimest korda uurinud matemaatikud 1930. aastatel Viinis ja Harvardis, eelkõige Karl Menger. Menger määratleb probleemi, kaalub ilmset toorest algoritmi ja täheldab lähima naabri heuristika mitteoptimaalsust:

Tähistame sõnumitooja probleemiga (kuna praktikas peaks seda küsimust lahendama iga postiljon, igatahes ka paljud reisijad) ülesannet leida ﬁntsele hulgale punktidele, mille paariskaugused on teada, kõige lühem marsruut, mis ühendab neid punkte. Loomulikult on see ülesanne lahendatav lõplikult paljude katsetega. Reeglid, mis viiksid katsete arvu alla antud punktide permutatsioonide arvu, ei ole teada. Reegel, et kõigepealt tuleb minna alguspunktist lähimasse punkti, seejärel sellele lähimasse punkti jne, ei anna üldiselt lühimat marsruuti.

Hassler Whitney Princetoni ülikoolis võttis varsti pärast seda kasutusele rändmüüja probleemi.

Müügimees soovib külastada kõiki linnu A, B, C ja D. Milline on parim viis seda teha (kõige odavamad lennupiletid ja minimaalne sõiduaeg)?

Müügimehe optimaalne marsruut, mis külastab Saksamaa 15 suurimat linna. Näidatud marsruut on 43 589 145 600 võimalikust marsruudist kõige lühem.

William Rowan Hamilton

Probleemi esitamine

Müügimehe probleem kirjeldab müügimeest, kes peab reisima N linna vahel. See, millises järjekorras ta seda teeb, ei ole talle oluline, kui ta külastab iga linna üks kord oma reisi jooksul ja lõpetab seal, kus ta alguses oli. Iga linn on ühendatud teiste lähedalasuvate linnadega ehk sõlmpunktidega kas lennuki, maantee või raudtee kaudu. Igale linnade vahelisele ühendusele on lisatud üks või mitu kaalu (või kulu). Kulu kirjeldab, kui "raske" on seda serva graafil läbida, ja see võib olla antud näiteks lennupileti või rongipileti maksumuse, ehk siis serva pikkuse või läbimiseks vajaliku aja järgi. Müügimees soovib hoida nii reisikulud kui ka läbitud vahemaa võimalikult madalad.

Reisiv müügimehe probleem on tüüpiline suurest klassist "rasketest" optimeerimisprobleemidest, mis on matemaatikuid ja arvutiteadlasi juba aastaid intrigeerinud. Kõige tähtsam on see, et sellel on rakendusi teaduses ja tehnikas. Näiteks trükkplaadi valmistamisel on oluline määrata parim järjekord, milles laser puurib tuhandeid auke. Selle probleemi tõhus lahendus vähendab tootja tootmiskulusid.

Raskusaste

Üldiselt on rändmüüja probleemi raske lahendada. Kui seda probleemi on võimalik jagada väiksemateks komponentprobleemideks, siis on need komponendid vähemalt sama keerulised kui algne probleem. Seda nimetavad arvutiteadlased NP-raskeks probleemiks.

Paljud inimesed on seda probleemi uurinud. Kõige lihtsam (ja kõige kallim) lahendus on lihtsalt proovida kõiki võimalusi. Probleemiks on see, et N linna puhul on (N-1) faktoriaalset võimalust. See tähendab, et ainult 10 linna puhul on üle 180 tuhande kombinatsiooni, mida proovida (kuna alguslinn on määratud, võib ülejäänud üheksa linna kohta olla permutatsioone). Me loeme ainult pooled, sest igal marsruudil on tagurpidi sama pikk või sama maksumusega võrdne marsruut. 9! / 2 = 181 440

Probleemi täpseid lahendusi saab leida, kasutades haru ja piirangute algoritme. Praegu on see võimalik kuni 85 900 linna puhul.
Heuristilised lähenemisviisid kasutavad järgmise sõlme valimiseks suunavaid reegleid. Kuid kuna heuristikud on ligikaudsed, ei anna nad alati optimaalset lahendust, kuigi kvaliteetsed vastuvõetavad heuristikud võivad leida kasuliku lahenduse murdosa ajast, mis on vajalik probleemi täielikuks jõhkraks lahendamiseks. Üks näide heuristikast oleks näiteks summeerimine selle kohta, mitu külastamata sõlme on seotud sõlme "lähedal". See võiks julgustada müüjat külastama koos klastrisse koondatud lähedaste sõlmede rühma, enne kui ta liigub graafi teise loomuliku klastri juurde. Vt Monte Carlo algoritmid ja Las Vegase algoritmid.

Küsimused ja vastused

K: Mis on rändkaupmehe probleem?

V: Reisijate müügimehe probleem (TSP) on klassikaline algoritmiline probleem arvutiteaduse ja operatsioonide uurimise valdkonnas. See keskendub optimeerimisele, kusjuures paremad lahendused tähendavad sageli odavamaid, lühemaid või kiiremaid lahendusi.

K: Kuidas on TSP väljendatud?

V: TSP on kõige lihtsamini väljendatav graafina, mis kirjeldab sõlmede kogumi asukohti.

K: Kes määratles esimesena TSP?

V: Reisivate müügimeeste probleemi defineerisid 1800. aastatel iiri matemaatik W. R. Hamilton ja briti matemaatik Thomas Kirkman.

K: Kes uuris seda 1930. aastatel edasi?

V: 1930. aastatel uurisid seda edasi Viinis ja Harvardis töötanud matemaatikud Karl Menger.

K: Mida tutvustas Hassler Whitney varsti pärast seda?

V: Hassler Whitney Princetoni ülikoolis võttis varsti pärast selle määratlust kasutusele nime "rändmüüja probleem".

K: Mida tähendab selles kontekstis "parem lahendus"?

V: Selles kontekstis tähendab parem lahendus sageli lahendust, mis on odavam, lühem või kiirem.

K: Millist algoritmi pidas Menger TSP-d uurides ilmselgeks?

V: Menger pidas TSP-i uurides ilmselget toorest algoritmi ja täheldas, et lähima naabri heuristika kasutamine ei anna alati optimaalset tulemust.