Student World

Problém obchodního cestujícího (travelling salesman problem, TSP) nepřestává fascinovat. Hlubší porozumění úloze pokládá za hrozbu současné kryptografii. Na problému se demonstrují schopnosti i omezení DNA i kvantových počítačů. Zkoumá se analogové řešení (např. mýdlový film), ba i to, zda nějakou schopnost řešit problém nemají včely.

Viz také:

Včely a problém obchodního cestujícího

Obchodní cestující a mýdlové bubliny

Níže zmíněná kniha však popisuje ještě kurióznější přístupy k problému (spolu se základní premisou, že bychom řešení měli vítat, protože problém obchodního cestujícího obecně souvisí s naší schopností efektivně využívat zdroje; ostatně celý problém nevznikl jako kuriozita u „zeleného stolu“, ale vycházel z reálných potřeb – kniha je zajímavá i tím, že popisuje historii TSP).
– obchodní cestující a přenos optického signálu (tj. opět de facto analogový počítač)
– obchodní cestující a šimpanzi – na rozdíl od včel samozřejmě předpokládáme, že šimpanzi řeší úlohu typu sbírání potravy rozmístěné na cestě nějak analogicky jako my, „vědomě“.
– obchodní cestující a děti; zajímavé je, jak se děti postupně s věkem u menšího množství bodů blíží optimálnímu řešení.
– obchodní cestující a duševní poruchy – některé psychické choroby korespondují s neschopností řešit problém.
– asi nejkurióznější je však tato úvaha. Představte si, jak dlouho trvalo, než počítače začaly triumfovat nad lidskými šachisty. „Divné“ je, jak lidé se svými omezenými schopnostmi stále dokáží hrát šachy na trochu srovnatelné úrovni. Přirozeně ne normální lidé, ale ti, kdo se šachům systematicky věnují třeba desítky let. A co kdyby se lidé trénovali k úloze obchodního cestujícího, nedosahovali by také výsledků jen „o málo“ hoších než počítače? Podobně jako u šachů nebo Go mají lidé se zkušeností k problému jakoby intuitivní přístup založený na rozpoznávání geometrických vzorů.
– když to vezmeme do extrému a s velkou nadsázkou: nepřichází prostě trochu paradoxně čas, kdy bude levnější k vyřešení úlohy určitého typu zaměstnat pár lidí než vyvíjet program (asi jako dnes protirobotickou ochranu CAPTCHA vyplňují nejen programy, ale i najatí lidé)? A nakonec, nemohly by se děti ve škole učit právě na příkladech tohoto typu, kdy by současně dělaly něco užitečného (a třeba i placeného)? Nestálo by za to zabývat se obchodním cestujícím jako rekreační hrou – obdobou šachů?

Zdroj: William J. Cook: In Pursuit of the Traveling Salesman, Princeton University Press 2011, 2012

autor Pavel Houser