Problém obchodního cestujícího

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 zadanými body na mapě.

Zadání optimalizační verze problému[editovat | editovat zdroj]

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

Matematická formulace používající pojmosloví teorie grafů: "V daném 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 (či uzlů grafu) 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 uzlů. Klíčová obtíž je tedy v nalezení časově efektivního algoritmu hledání nejkratších cest.

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. Č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.

Zadání rozhodovací verze problému[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Optimalizační verze problému obchodního cestujícího patří mezi tzv. NP-těžké úlohy, tzn. v obecném případě není známo, ani jak pro každý vstup 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 trasy 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 tras vedoucích do již navštívených měst. Tak by prohledal všechny možné trasy 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)! větví.

V praxi se podobná úloha obvykle řeší pouze přibližně (heuristickými algoritmy, např. genetickými algoritmy, tabu prohledáváním atd.). Tím se (za cenu vzdání se nároku na nalezení přesné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[editovat | editovat zdroj]

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.

Související články[editovat | editovat zdroj]