Úloha existuje v řadě variant, jimž je společné to, že cílem je najít nejkratší (nebo i jedinou či jakoukoli možnou) spojnici mezi x body, přičemž je třeba navštívit každý z nich. V některých verzích úlohy lze každým místem projít jen jednou, jindy se cesty mohou křížit. Jsou verze, kdy existují spojnice mezi všemi místy, v jiných „silnice“ spojují jen některá.
Jaký to má praktický význam? Původně tato úloha nevzešla od zeleného stolu, ale matematikové byli kontaktováni zcela reálnými „uživateli“, i když nemuselo jít samozřejmě zrovna o obchodní cestující, ale třeba o pošťáky.
V současnosti problémy TSP s miliony bodů už nemají tak bezprostřední vazbu ke svému názvu. Nejčastěji se s nimi setkáváme v souvislosti s kryptografií; možnost efektivně řešit problém obchodního cestujícího se pokládá za hrozbu dnešním šifrám (viz dále). V současné době se na toto téma objevila např. kniha Williama J. Cooka, profesora na Georgia Institute of Technology (In Pursuit of the Traveling Salesman, Princeton University Press), která shrnuje některé z přístupů.
NP problém
TSP patří mezi tzv. nedeterministicky polynomiální (NP) úlohy; konkrétně může jít o podskupinu úloh tzv. NP těžkých nebo NP úplných. V zásadě to znamená, že pro tyto problémy platí značná asymetrie – vyřešit je je složité (alespoň současnými algoritmy), naopak správnost řešení lze ověřit řádově rychleji. Pro srovnání, třeba sčítání takovou vlastnost nemá, vypočítat příklad je stejně obtížné jako ho ověřit (udělat zkoušku odečítáním).
Tady už je zřejmé, proč problém obchodního cestujícího podobně jako třeba faktorizace (opět viz dále) má vztah k současné kryptografii; zde právě potřebujeme asymetrii pro šifrování a naopak nemožnost v reálném čase šifru dekódovat bez znalosti klíčů. Současné algoritmy dokážou problém obchodního cestujícího řešit pouze s tzv. exponenciální složitostí. To znamená, že doba řešení v závislosti na velikosti vstupu – počtu bodů – roste exponenciálně. Představíte-li si úlohu o milionech bodů, je jasné, že se v reálném čase lze těžko dopočítat k nějakému řešení. Abychom si udělali alespoň řádovou představu, dosud se i s pomocí superpočítačů podařilo vyřešit pouze úlohy do řádově 100 000 bodů. Nicméně nemohl by přece jen existovat algoritmus, který by úlohu řešil v rychlejším čase? Tato otázka představuje slavný problém P vs. NP, kdy P znamená polynomiálně rostoucí obtížnost (tj. časová obtížnost roste ne s exponentem, ale s nějakou mocninou; postavte si vedle sebe křivky, exponenciála roste mnohem strměji). Problém spadá do speciální disciplíny matematiky a informatiky zvané teorie výpočetní složitosti.
Existuje nějaký polynomiálně složitý algoritmus pro řešení úlohy obchodního cestujícího? Tato úloha patří mezi sedm největších problémů současné matematiky, které jako výzvy pro 21. století vyhlásil v roce 2000 Clay Mathematics Institute v (americké) Cambridge. Řešení každé z úloh je honorováno odměnou 1 milion dolarů. Zatím šest problémů odolává. Jeden z nich, tzv. Poincarého domněnku, vyřešil podivínský ruský matematik Grigorij Perelman, a protože opakovaně odmítl finanční cenu, dostalo se mu v médiích velké publicity. Problém P vs. NP je mimochodem pokládán mezi těmi zbylými za relativně nejsnadnější. Matematik a popularizátor Keith Devlin ve své knize (Problémy pro třetí tisíciletí, Argo a Dokořán 2005) uvádí, že jako jedinou ze sedmi úloh může podle jeho názoru tento problém se štěstím vyřešit i amatér, nebo alespoň dokáže dobře porozumět jeho formulaci.
Vesměs se předpokládá, že žádný polynomiální algoritmus neexistuje a tvůrci šifer tedy (zdánlivě) mohou být klidní. Vinay Deolalikar, výzkumník z laboratoří firmy HP v kalifornském Palo Altu, přišel v roce 2009 s tím, že P je opravdu různé než NP, odborníci ale jeho důkaz neuznali. Musíme si proto ještě trochu počkat. To, že problém bude vyřešen brzy, se ovšem mimochodem očekávalo už v 80. letech. Devlin nicméně uvádí, že i když takový (neexponenciálně složitý) algoritmus objeven nebude, může někdo získat při tomto výzkumu takový vhled do povahy problému, že dokáže navrhovat efektivní heuristiky. Tak se ostatně tyto problémy často řeší už teď; známe celkem rychlé postupy, u nichž víme, že se od optima neliší více než o nějakou maximální odchylku. K řešení obchodního cestujícího je vhodné např. „šlechtit“ genetické algoritmy nebo používat další evoluční techniky vývoje softwaru. Skoro optimální řešení představuje celkem příjemný výsledek: Šifry jsou v bezpečí, naopak optimalizační úlohy z reálného světa dokážeme řešit celkem efektivně. Každopádně problém je dostatečně zajímavý na to, aby inspiroval řadu vědců, hračičků všeho druhu, ale i biologů nebo psychologů. Pojďme se podívat na několik zajímavých, ať už vážně či nevážně míněných řešení.
Kvantové počítače
Kvantové přístupy se k takto paralelním úlohám zdají být jako stvořené. Je pravda, že kvantový počítač o počtu propletených bitů odpovídajících jednotlivým bodům (místům, uzlům) v sobě najednou obsahuje všechny cesty, mezi nimiž tedy musí být i ta hledaná. Nicméně ze systému nedokážeme žádným způsobem řešení přečíst. Ačkoliv se občas můžeme setkat s opačným tvrzením, žádný způsob pro řešení NP úloh na kvantovém počítači dnes nemáme.
V této souvislosti bývá často zmiňována faktorizace. Faktorizace je jiná „asymetrická“ metoda používaná v kryptografii, kdy jednoduchá operace odpovídá vynásobení dvou prvočísel, obtížná rozkladu takto získaného obrovského čísla na prvočísla (samotná faktorizace je tento rozklad). Pro faktorizaci opravdu máme k dispozici kvantový algoritmus fungující v menším než exponenciálním čase, v praxi však dosud není použitelný. Navíc i zde platí, že větší riziko než samotný algoritmus může představovat vhled získaný do problému při jeho hledání a z toho vyplývající tvorba efektivních heuristik. Faktorizace ovšem nepatří z hlediska obtížnosti do stejné třídy úloh jako TSP; alespoň se to dosud nepodařilo dokázat a všeobecně se o tom pochybuje. (Zcela na okraj: Faktorizace se týká jiné ze „sedmi velkých“ úloh Clayova ústavu, tzv. Riemannova hypotéza, která se zabývá hustotou prvočísel.)
Živé organismy
Ještě kurióznější je testovat, jak jsou na tom s řešením úlohy obchodního cestujícího živé organismy. Vědci z britské Royal Holloway University a Queen Mary University přišli s tím, že jednoduché úlohy obchodního cestujícího zvládnou vyřešit i včely se svými miniaturními mozky. Výzkumníci jim přehazovali květy, včely se ovšem dokázaly přizpůsobit a létaly mezi nimi v pořadí, aby mohly celkem urazit co nejmenší vzdálenost. Podobně se na TSP testovali šimpanzi, pro něž motivací rovněž bylo zvládnout při sbírání potravy co nejkratší vzdálenost. Schopnost řešit problém obchodního cestujícího se zkoumá i u dětí, které již samozřejmě mohou při pokusu kreslit na papíře. S věkem přirozeně roste schopnost řešit stále složitější verze úlohy. S neschopností vypořádat se s problémem pak může souviset nejenom snížená inteligence, ale i některé specifické psychické poruchy.
Na závěr opravdu překvapivá Cookova úvaha. Představte si, uvádí, jak dlouho trvalo, než počítače začaly triumfovat nad lidskými šachisty. Když se nad tím zamyslíte, „divné“ je spíše to, jak lidé se svými omezenými schopnostmi stále dokážou hrát šachy na trochu srovnatelné úrovni. Něco podobného platí u Go, kde počítače dosud vůbec netriumfovaly. V obou hrách máme k dispozici kromě počítání i intuitivní přístupy založené na rozpoznávání vzorů a symetrií. Jak by to dopadlo, kdybychom odmalička trénovali řešení úloh obchodního cestujícího? Jak těžké úlohy bychom zvládli? A jak by uspěli zázrační počtáři nebo lidé s fenomenální prostorovou představivostí? Netrénují je už tajné služby na lámání šifer? Nemohlo by to být podobné jako u ochran CAPTCHA – proč vyvíjet složité programy, když můžete zaplatit lidský výpočetní výkon někde ve třetím světě? To je samozřejmě nadsázka, úlohy o milionu bodů jsou zcela mimo lidské možnosti. Tedy – asi. Minimálně jako námět pro sci-fi román se to zdá být nicméně zábavná představa.
PŘEDPLATNÉ
ČLÁNKY DO MAILU