Problém obchodného cestujúceho
Problém cestujúceho predavača (často nazývaný TSP) je klasický algoritmický problém v oblasti informatiky a operačného výskumu. Je zameraný na optimalizáciu. V tomto kontexte lepšie riešenie často znamená riešenie, ktoré je lacnejšie, kratšie alebo rýchlejšie. TSP je matematický problém. Najjednoduchšie sa vyjadruje ako graf opisujúci umiestnenie množiny uzlov.
Problém obchodného cestujúceho definovali v 19. storočí írsky matematik W. R. Hamilton a britský matematik Thomas Kirkman. Hamiltonova Ikosova hra bola rekreačná hádanka založená na hľadaní Hamiltonovho cyklu. Zdá sa, že všeobecnú podobu TSP prvýkrát študovali matematici v 30. rokoch 20. storočia vo Viedni a na Harvarde, najmä Karl Menger. Menger definuje problém, uvažuje o zjavnom algoritme hrubej sily a pozoruje neoptimálnosť heuristiky najbližšieho suseda:
Problémom posla (keďže v praxi by túto otázku mal riešiť každý poštár, každopádne aj mnohí cestujúci) označujeme úlohu nájsť pre finitívne veľa bodov, ktorých párové vzdialenosti sú známe, najkratšiu trasu spájajúcu tieto body. Samozrejme, táto úloha je riešiteľná konečne mnohými pokusmi. Pravidlá, ktoré by stlačili počet pokusov pod počet permutácií daných bodov, nie sú známe. Pravidlo, že najprv treba ísť z východiskového bodu do najbližšieho bodu, potom do bodu, ktorý je k nemu najbližšie, atď. vo všeobecnosti nevedie k najkratšej trase.
Hassler Whitney na Princetonskej univerzite krátko nato zaviedol názov problém obchodného cestujúceho.
Obchodník chce navštíviť všetky mestá, A, B, C a D. Aký je najlepší spôsob, ako to urobiť (najlacnejšie letenky a minimálny čas cestovania)?
Optimálna trasa predajcu, ktorý navštívi 15 najväčších miest v Nemecku. Zobrazená trasa je najkratšia zo 43 589 145 600 možných trás.
William Rowan Hamilton
Uvedenie problému
Problém obchodného cestujúceho opisuje obchodného cestujúceho, ktorý musí cestovať medzi N mestami. Poradie, v akom tak urobí, ho nezaujíma, pokiaľ počas svojej cesty navštívi každé z nich raz a skončí tam, kde bol prvýkrát. Každé mesto je spojené s inými blízkymi mestami alebo uzlami lietadlom, cestou alebo železnicou. Každé z týchto spojení medzi mestami má priradenú jednu alebo viac váh (alebo nákladov). Náklady opisujú, aké "náročné" je prejsť túto hranu grafu, a môžu byť dané napríklad cenou letenky alebo lístka na vlak, prípadne dĺžkou hrany alebo časom potrebným na jej prekonanie. Predajca chce, aby náklady na cestu, ako aj vzdialenosť, ktorú prekoná, boli čo najnižšie.
Problém obchodného cestujúceho je typický pre veľkú triedu "ťažkých" optimalizačných problémov, ktoré už roky zaujímajú matematikov a informatikov. Najdôležitejšie je, že má aplikácie vo vede a technike. Napríklad pri výrobe dosiek plošných spojov je dôležité určiť najlepšie poradie, v akom laser vyvŕta tisíce dier. Efektívne riešenie tohto problému znižuje výrobné náklady výrobcu.
Obtiažnosť
Problém obchodného cestujúceho je vo všeobecnosti ťažko riešiteľný. Ak existuje spôsob, ako tento problém rozdeliť na menšie čiastkové problémy, budú tieto čiastkové problémy minimálne rovnako zložité ako pôvodný problém. Informatici to nazývajú NP-ťažké problémy.
Tento problém skúmalo mnoho ľudí. Najjednoduchšie (a najdrahšie riešenie) je jednoducho vyskúšať všetky možnosti. Problémom je, že pre N miest máte (N-1) faktorovú možnosť. To znamená, že len pre 10 miest existuje viac ako 180 tisíc kombinácií, ktoré treba vyskúšať (keďže je definované počiatočné mesto, na zvyšných deväť môžu existovať permutácie). Počítame len polovicu, pretože každá trasa má rovnakú trasu v opačnom smere s rovnakou dĺžkou alebo nákladmi. 9! / 2 = 181 440
- Presné riešenia problému sa dajú nájsť pomocou algoritmov vetiev a hraníc. V súčasnosti je to možné až pre 85 900 miest.
- Heuristické prístupy využívajú súbor usmerňujúcich pravidiel pre výber ďalšieho uzla. Keďže však výsledkom heuristiky sú aproximácie, neposkytnú vždy optimálne riešenie, hoci kvalitná prípustná heuristika môže nájsť užitočné riešenie za zlomok času potrebného na úplné riešenie problému hrubou silou. Príkladom heuristiky pre uzol môže byť súčet toho, koľko nenavštívených uzlov je "blízko" pripojeného uzla. To by mohlo predajcu povzbudiť, aby navštívil skupinu blízkych uzlov zoskupených dohromady pred presunom na iný prirodzený zhluk v grafe. Pozri algoritmy Monte Carlo a algoritmy Las Vegas
Otázky a odpovede
Otázka: Čo je to problém obchodného cestujúceho?
Odpoveď: Problém cestujúceho predavača (TSP) je klasický algoritmický problém v oblasti informatiky a operačného výskumu. Zameriava sa na optimalizáciu, pričom lepšie riešenia často znamenajú lacnejšie, kratšie alebo rýchlejšie riešenia.
Otázka: Ako sa vyjadruje TSP?
Odpoveď: TSP sa najjednoduchšie vyjadruje ako graf opisujúci umiestnenie množiny uzlov.
Otázka: Kto prvý definoval TSP?
Odpoveď: Problém obchodného cestujúceho definovali v roku 1800 írsky matematik W. R. Hamilton a britský matematik Thomas Kirkman.
Otázka: Kto ho ďalej skúmal v 30. rokoch 20. storočia?
Odpoveď: V 30. rokoch 20. storočia ho ďalej študovali matematici Karl Menger vo Viedni a na Harvarde.
Otázka: Čo zaviedol Hassler Whitney krátko potom?
Odpoveď: Hassler Whitney na Princetonskej univerzite zaviedol názov "problém obchodného cestujúceho" krátko po jeho definícii.
Otázka: Čo v tomto kontexte znamená "lepšie riešenie"?
Odpoveď: V tomto kontexte lepšie riešenie často znamená riešenie, ktoré je lacnejšie, kratšie alebo rýchlejšie.
Otázka: Aký algoritmus považoval Menger pri štúdiu TSP za samozrejmý?
Odpoveď: Menger pri štúdiu TSP považoval za zrejmý algoritmus hrubej sily a pozoroval, že použitie heuristiky najbližšieho suseda neprináša vždy optimálne výsledky.
