Problém obchodního cestujícího

Problém obchodního cestujícího (anglicky Travelling Salesman Problem - TSP) je obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi vrcholy ohodnoceného grafu.

Zadání optimalizační verze problému

Laická formulace: Existuje několik měst, a mezi nimi silnice o daných délkách. Úkolem je najít nejkratší cestu procházející všemi městy a vracející se zpět do výchozího města.

Matematická formulace: V ohodnoceném úplném grafu najděte nejkratší hamiltonovskou kružnici.

Problém nespočívá ani tak ve stanovení libovolného postupu nalezení nejkratší cesty - jeden takový postup je totiž skoro samozřejmý: stačí jednoduše prohledat všechny možné uzavřené cesty mezi danými městy a vybrat nejkratší z nich. Obtíž však je, že s rostoucím počtem měst počet možných cest velice rychle narůstá, a tím se doba potřebná k propočtu hrubou silou na počítačích stává zcela neúnosnou už při několika málo desítkách měst. +more Klíčová obtíž je tedy v nalezení časově efektivního algoritmu hledání nejkratší cesty.

V obecné variantě problému navíc nevyžadujeme, aby v grafu platila trojúhelníková nerovnost. To by v reálném světě znamenalo, že přímá cesta z Prahy do Brna by mohla být delší než „zkratka“ přes Ostravu. +more Často tedy hovoříme o ceně cesty, díky čemuž si tuto neintuitivní situaci můžeme lépe představit. Pokud v grafu trojúhelníková nerovnost platí, říkáme, že se jedná o metrický problém obchodního cestujícího.

Existuje také rozhodovací verze problému obchodního cestujícího, kde otázkou je: „Existuje v daném úplném ohodnoceném grafu hamiltonovská kružnice kratší než x?“

Obtížnost

Optimalizační verze problému obchodního cestujícího patří mezi tzv. NP-těžké úlohy, tzn. +more v obecném případě není známo, ani jak pro každý problém nalézt přesné řešení v rozumném čase, a dokonce ani zda vůbec může existovat algoritmus, který takové řešení najde v čase úměrném nějaké mocnině počtu uzlů.

Že jde o nedeterministicky polynomiální problém, je patrné z toho, že nedeterministický počítač, umožňující v každém kroku rozvětvit výpočet na libovolný počet větví, by mohl začít v některém „městě“, rozdělit propočet délky cesty na tolik větví, kolik z města vede silnic, a v každém z cílových měst postupovat stejně - s výjimkou cest vedoucích do již navštívených měst. Tak by prohledal všechny možné cesty v n výpočetních krocích, pokud počet měst činí n, a rozvětvil by se maximálně do (n - 1). +more větví.

V praxi se podobná úloha obvykle řeší pouze přibližně heuristickými algoritmy, např. genetickými algoritmy, simulovaným žíháním či spojitou Hopfieldovou sítí. +more Tím se (za cenu vzdání se nároku na nalezení optimálního řešení) dosahuje prakticky použitelných časů.

Heuristické algoritmy obecně nijak negarantují, jak moc se získaný výsledek liší od optimální cesty, pro metrický problém obchodního cestujícího však existují prakticky použitelné (polynomiální) algoritmy, které toto dovedou (např. Christofidův algoritmus najde cestu, která je nejhůře o polovinu delší).

Rozhodovací verze problému je NP-úplná, tedy existuje nedeterministický Turingův stroj (nedeterministický algoritmus), který vydá jak odpověď ANO, tak odpověď NE vždy po maximálně „polynomiálním počtu kroků“.

Příklad nejkratší okružní cesty

Mějme města A, B, C, D, vzdálená od sebe podle následujícího obrázku:

Příklad

Nejkratší okružní cesta obchodního cestujícího je A → B → C → D → A (případně v opačném směru A → D → C → B → A), na které urazí vzdálenost 35 + 12 + 30 + 20 = 97.

Reference

Související články

Problém čínského listonoše

Externí odkazy

[url=http://gebweb. net/optimap/]On-line služba řešící problém obchodního cestujícího v prostředí Google Map, max. +more 100 bodů trasy (Přibližně přesné)[/url] * Algoritmy (prezentace a demo ukázky): ** Část 1. - [url=https://www. youtube. com/watch. v=HA9pbu-tCVE]Algoritmus postupných permutací[/url] ** Část 2. - [url=https://www. youtube. com/watch. v=yQBkARJls8M]Algoritmus hledání na trojúhelníkové síti[/url] ** Část 3. - [url=https://www. youtube. com/watch. v=-yr0JlcwFxI]Algoritmus polární trasy[/url] ** Část 4. - [url=https://www. youtube. com/watch. v=3_l3SwRAP7s]Algoritmus Chiméra[/url] ** Část 5. - [url=https://www. youtube. com/watch. v=DqF63m0b0tU]Fragmentační algoritmus[/url] ** Část 6. - [url=https://www. youtube. com/watch. v=2ajNfeSFIEE]Porovnání algoritmů[/url].

Kategorie:NP-úplné problémy Kategorie:Úlohy s grafy