Keliaujančio pirklio uždavinys
Keliaujančio pardavėjo problema (dažnai vadinama TSP) yra klasikinis algoritminis uždavinys informatikos ir operacijų tyrimų srityje. Ji orientuota į optimizavimą. Šiame kontekste geresnis sprendimas dažnai reiškia sprendimą, kuris yra pigesnis, trumpesnis arba greitesnis. TSP yra matematinė problema. Ją lengviausia išreikšti grafu, kuriame aprašomos mazgų aibės vietos.
XIX a. keliaujančio pardavėjo problemą apibrėžė airių matematikas W. R. Hamiltonas ir britų matematikas Thomas Kirkmanas. Hamiltono Ikoso žaidimas buvo pramoginis galvosūkis, pagrįstas Hamiltono ciklo radimu. Atrodo, kad bendrąją TSP formą XX a. trečiajame dešimtmetyje Vienoje ir Harvarde pirmą kartą tyrinėjo matematikai, ypač Karlas Mengeris. Mengeris apibrėžia problemą, svarsto akivaizdų brutalios jėgos algoritmą ir pastebi artimiausio kaimyno euristikos neoptimalumą:
Pašnekovo uždaviniu (nes praktiškai šį klausimą turėtų spręsti kiekvienas paštininkas, bet kokiu atveju ir daugelis keliautojų) vadiname uždavinį rasti trumpiausią maršrutą, jungiantį fiziškai daug taškų, kurių poriniai atstumai yra žinomi. Žinoma, šis uždavinys išsprendžiamas baigtinai daug bandymų. Taisyklės, dėl kurių bandymų skaičius būtų mažesnis už duotų taškų permutacijų skaičių, nėra žinomos. Taisyklė, kad iš pradinio taško pirmiausia reikia eiti į artimiausią tašką, tada į artimiausią tašką ir t. t., apskritai neduoda trumpiausio maršruto.
Netrukus Prinstono universitete Hassleris Whitney pristatė keliaujančio pardavėjo problemos pavadinimą.
Pardavėjas nori aplankyti visus miestus: A, B, C ir D. Koks geriausias būdas tai padaryti (pigiausi lėktuvo bilietai ir trumpiausias kelionės laikas)?
Optimalus 15 didžiausių Vokietijos miestų lankančio pardavėjo maršrutas. Parodytas maršrutas yra trumpiausias iš 43 589 145 600 galimų maršrutų.
Viljamas Rovanas Hamiltonas
Problemos įvardijimas
Keliaujančio pardavėjo uždavinys aprašo pardavėją, kuris turi keliauti tarp N miestų. Jam nerūpi, kokia tvarka jis tai darys, jei tik kelionės metu aplankys kiekvieną iš jų po vieną kartą ir baigs kelionę ten, kur buvo iš pradžių. Kiekvienas miestas yra sujungtas su kitais artimais miestais, arba mazgais, lėktuvais, keliais arba geležinkeliais. Kiekvienam iš šių ryšių tarp miestų priskiriamas vienas ar daugiau svorių (arba sąnaudų). Sąnaudos nusako, kaip "sunku" kirsti šią grafo briauną, ir gali būti išreikštos, pavyzdžiui, lėktuvo ar traukinio bilieto kaina, arba galbūt briaunos ilgiu, arba laiku, kurio reikia norint ją kirsti. Pardavėjas nori, kad kelionės išlaidos ir nuvažiuojamas atstumas būtų kuo mažesni.
Keliaujančio pardavėjo problema yra tipiška didelės klasės "sunkių" optimizavimo problemų, kurios jau daugelį metų domina matematikus ir informatikus, problema. Svarbiausia yra tai, kad ji taikoma mokslo ir inžinerijos srityse. Pavyzdžiui, gaminant spausdintinę plokštę, svarbu nustatyti geriausią tvarką, kuria lazeris išgręš tūkstančius skylučių. Efektyvus šios problemos sprendimas sumažina gamintojo gamybos sąnaudas.
Sudėtingumas
Apskritai keliaujančio pardavėjo uždavinį sunku išspręsti. Jei yra būdas suskaidyti šį uždavinį į mažesnius komponentinius uždavinius, komponentai bus ne mažiau sudėtingi nei pradinis uždavinys. Tai informatikos specialistai vadina NP sunkiais uždaviniais.
Šią problemą tyrinėjo daugybė žmonių. Paprasčiausias (ir brangiausias) sprendimas - tiesiog išbandyti visas galimybes. Problema ta, kad N miestų atveju turite (N-1) faktorių galimybių. Tai reiškia, kad tik 10 miestų galima išbandyti daugiau kaip 180 tūkstančių kombinacijų (kadangi pradinis miestas yra apibrėžtas, gali būti likusių devynių miestų permutacijų). Skaičiuojame tik pusę, nes kiekvienas maršrutas turi tokį pat maršrutą atvirkščiai, kurio ilgis arba kaina yra tokia pati. 9! / 2 = 181 440
- Tikslius uždavinio sprendinius galima rasti naudojant šakų ir ribų algoritmus. Šiuo metu tai įmanoma iki 85 900 miestų.
- Euristiniuose metoduose kitam mazgui parinkti naudojamas pagrindinių taisyklių rinkinys. Tačiau kadangi euristikos rezultatai yra apytiksliai, jos ne visada duoda optimalų sprendimą, nors kokybiškos leistinos euristikos gali surasti naudingą sprendimą per dalį laiko, reikalingo visiškam problemos išsprendimui brutalia jėga. Euristikos pavyzdys mazgui būtų suma, kiek neaplankytų mazgų yra "arti" sujungto mazgo. Tai galėtų paskatinti pardavėją aplankyti artimų mazgų grupę, susitelkusią kartu, ir tik tada pereiti prie kito natūralaus grafo klasterio. Žr. Monte Karlo algoritmus ir Las Vegaso algoritmus
Klausimai ir atsakymai
K: Kas yra keliaujančio pardavėjo problema?
A: Keliaujančio pardavėjo problema (angl. Traveling Salesman Problem, TSP) yra klasikinis algoritminis uždavinys informatikos ir operacijų tyrimų srityje. Jame daugiausia dėmesio skiriama optimizavimui, o geresni sprendimai dažnai reiškia pigesnius, trumpesnius arba greitesnius sprendimus.
K: Kaip išreiškiama TSP?
A: TSP lengviausia išreikšti kaip grafą, kuriame aprašomos mazgų aibės vietos.
K: Kas pirmasis apibrėžė TSP?
A: Keliaujančio pardavėjo problemą XIX a. apibrėžė airių matematikas W. R. Hamiltonas ir britų matematikas Thomas Kirkmanas.
K: Kas ją toliau tyrinėjo XX a. trečiajame dešimtmetyje?
A: XX a. trečiajame dešimtmetyje ją toliau tyrinėjo Vienos ir Harvardo matematikai Karlas Mengeris.
K: Ką netrukus po to įvedė Hasleris Vitnis?
A: Hassler Whitney Prinstono universitete netrukus po apibrėžimo įvedė "keliaujančio pardavėjo problemos" pavadinimą.
K: Ką šiame kontekste reiškia "geresnis sprendimas"?
A: Šiame kontekste geresnis sprendimas dažnai reiškia pigesnį, trumpesnį ar greitesnį sprendimą.
Klausimas: Kokį algoritmą Mengeris, nagrinėdamas TSP, laikė akivaizdžiu?
Atsakymas: Mengeris, tirdamas TSP, akivaizdžiu laikė brutalios jėgos algoritmą ir pastebėjo, kad naudojant artimiausio kaimyno euristiką ne visada gaunami optimalūs rezultatai.
