Problém obchodního cestujícího

Z Wikipedie, otevřené encyklopedie

Problém obchodního cestujícího 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ě.

[editovat] Zadání

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ů: Jak v daném ohodnoceném úplném grafu efektivně najít 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.

[editovat] Obtížnost

Tato úloha patří mezi tzv. NP-úplné úlohy, tzn. v obecném případě není známo ani jak 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ů.