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. 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. Č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. 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 ${\displaystyle n}$ výpočetních krocích, pokud počet měst činí ${\displaystyle n}$, a rozvětvil by se maximálně do ${\displaystyle (n-1)!}$ 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í.^[1] 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 pokud nějak získáme potenciální řešení (popis cesty), lze snadno (v polynomiálním počtu kroků) ověřit, že se skutečně jedná o platné řešení, tedy že jeho délka je menší než požadovaná mez.

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:

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

• Obrázky, zvuky či videa k tématu Problém obchodního cestujícího na Wikimedia Commons
• On-line služba řešící problém obchodního cestujícího v prostředí Google Map, max. 100 bodů trasy (Přibližně přesné)
• Algoritmy (prezentace a demo ukázky):
  • Část 1. – Algoritmus postupných permutací
  • Část 2. – Algoritmus hledání na trojúhelníkové síti
  • Část 3. – Algoritmus polární trasy
  • Část 4. – Algoritmus Chiméra
  • Část 5. – Fragmentační algoritmus
  • Část 6. – Porovnání algoritmů