Problém obchodního cestujícího je dosud nevyřešený matematický problém. Spočívá v tom, že máte seznam měst, které potřebujete navštívit, každé jednou, a na konci cesty se opět vrátit domů, do výchozího města. Cesta má být nejkratší. Co je na tomto problému obtížného? Zdánlivě se nabízí jednoduché řešení, propočítat všechny možnosti.
W. J. Cook: Po stopách obchodního cestujícího. Matematika na hranicích možností. Dokořán a Argo, 2012, 258 str., váz.
Problém obchodního cestujícího je dosud nevyřešený matematický problém. Spočívá v tom, že máte seznam měst, které potřebujete navštívit, každé jednou, a na konci cesty se opět vrátit domů, do výchozího města. Cesta má být nejkratší. Co je na tomto problému obtížného? Zdánlivě se nabízí jednoduché řešení, propočítat všechny možnosti. Tato metoda hrubé síly má však malý háček, už při počtu měst blížícím se počtu bývalých okresních měst v Česku je těchto možných tras větší než je počet atomů ve vesmíru. Tento počet atomů odhadl v minulém století Artur Edington, propagátor a podporovate Alberta Einsteina na deset na osmdesátou, tedy jedničku, následovanou 80 nulami. Tento zdánlivě jednoduchý a bezvýznamný problém má docela velký význam nejen pro obchodní cestující, firmy zásobující např. Prodejny, ale také při výrobě integrovaných obvodů, desek plošných spojů, ale také při plánování pohybu Hubbleova teleskopu atd.
Autor knihy náleží do úzkého okruhu nejvýznamnějších matematiků, zabývajících se tímto problémem. Kniha má 12 kapitol, předmluvu, poznámky, seznam literatury a rejstřík. Problém obchodního cestujícího se dotýká výpočtové složitosti. Na matematiky, kteří by našli řešení problému, čeká tučná odměna. Clayův matematický institut vypsal odměnu 1 milión dolarů pro kohokoliv, kdo přijde jako první s efektivním řešením, nebo kdo dokáže, že žádné takové efektivní řešení neexistuje. Problém neustále motivuje nové a nové objevy v oboru aplikované matematiky. O tzv. problémech milénia, tedy o sedmi matematických problémech, na jejichž vyřešení je vypsána odměna po jednom milionu dolarů, vydalo nakladatelství Dokořán knihy Problémy pro třetí tisíciletí.
Lidé se s problémem obchodního cestujícího setkali už mnohem dříve, než se stal předmětem studia matematiků. Profesionální matematici se nesnázemi obchodních cestujících, kazatelů a právníků, kteří potřebovali při svých cestách stanovit nejkratší cestu, příliš nezabývali. Přesto dva matematici vytvořili základy pro budoucí zkoumání problému z matematického hlediska. Byli to Leonhard Euler, který vyřešil hádanku, která trápila obyvatele Královce (dnes Kaliningrad). Obyvatelé města se rádi procházeli městem a při tom přecházeli řeku Pregel přes sedm mostůp, které tehdy existovaly. Hádanka spočívala v tom, najít způsob, jak přejít sedm mostů právě jednou během jediné procházky městem. Euler jednou pro vždy problém vyřešil a vytvořil při tom novou matematickou metodu, teorii grafů. Druhý matematik, Howard Rowan Hamilton měl zálibu v hledání cest v grafech. Sto let po Eulerovi studoval problém cesty, která má projít všech 20 vrcholů pravidelného dvanáctistěnu. Hamilton a Euler hledali cesty, při kterých mohli zanedbat vzdálenosti.
Dnešní typický obchodní cestující má auto vybavené satelitní navigací. Mapový software, který běží na jednotce GPS, často obsahuje modul pro vyřeršení malých úloh obchodního cestujícího kolem deseti měst, což stací pro cesty v rámci jednoho dne.
Podstatná část knihy je věnována historii výzkumu problému a zdokonalovaní a zjemňování metod.
Devátá kapitola „Výpočtová složitost“ se věnuje tím, zda existuje nebo neexistuje polynomiální algoritmus pro omezenou úlohu v celočíselním programování, která je jako taková samozřejmě konečná. Tak alespoň zní motto kapitoly, jehož autorem je Jack Edmonds. Všechna matematická tvrzení musí být formulována, nebo musí být alespoň v principu možné je přesně fotrmulovat, abychom mohli mluvit o jejich řešení. Otázka zní: jak zformalizovat pojem algoritmus: Problém se dostal do popředí na počátku 20. století, kdyžř David Hilbert formuloval problém rozhodnutelnosti. Teorie, která vedla k odpovědi na podobné otázky, je jedním z výsledků matematiky 20. stol. K jejímu vybodování přispěli Kurt Goedel, Alonzo Church a Alan Turing. Turing zavedl Turingův stroj. Jeho definice umožnila matematicky zkoumat algoritmy. S příchodem počítačů začala získávat na důležitosti otázka efektivnosti. Jedna věc je vědět, že Turingův stroj problém vyřeší, a jiná, míst jistotu, že se řešení dozvíme ještě za našeho života. První diskuse týkající se efektivnosti algoritmů se soustředily na problém obchodního cestujícího. Právě citovaný Jack Edmonds se stal zakladatelem teorie výpočtové složitosti.
V kapitole 11 „Estetika“ cituje autor knihy jako motto výrok českého matematika z Univerzity Karlovy Jaroslava Nešetřila: „Matematika byla vždy zdrojem složitých (a pro laiky mystických) struktur“. Kapitola se tak zabývá krásou v matematickém smyslu. Problém obchodního cestujícího inspiroval vznik celé řady poutavých výtvarných děl, které zachytily jeho matematickou podstatu. Kromě Jaroslava Nešetřila, který napsal a vydal v angličtině esej o matematice a umění, autor knihy opakovaně píše zřejmě o dalším českém matematikovi, který asi žije v USA, Vaškovi Chvátalovi, nebývá ovšem obvyklé, aby se v podobných zahraničních knihách nejen o matematice objevovala jména českých vědců, proto jsem se o tom zmínil. Kniha končí kapitolou „O krůček dál“, která má jen dvě stránky. Shrnuje, že problém není uzavřen, a že krása skrytá v problému obchodního cestujícího bude dál lákat matematiky a informatiky.
