Mohli by problém obchodního cestujícího řešit lidé?
Neživá příroda | 14.12.11
Představte si, jak dlouho trvalo, než počítače začaly triumfovat nad lidskými šachisty. 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?
Sdílet
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
Další články z rubriky
Související články
Nahrává se..
Videa
Chobotnice mění průhlednost stejně rychle jako displej Amazon Kindle
Maskování chobotnice se svou rychlostí vyrovná...
Komentáře
30.01.12, 07:29 mmmmmmmmmm
pro Pavla k deti
První chmel, první pivo na nádraží v Podbořanech. Vesnice bez pitné vody, (všude chlorové vápno) po práci na dvoře fronta kluků na lok rumu z láhve přinesené učitelem, večer na pivo do sousední vsi. Šestnáctka film promítaná vojáky z Doupova, táborák. Spolužačka co mně (v rodném městě) prodala vedle sebe lístek na Extasi (mládeži nepřístupno) zpívá všem jako zjevení na kraji lesa Plují lodi do Triany.
To mně bylo necelých čtrnáct. Chmel se sklízel pěkně ručičkama. O rok později jsem pracoval v lomu na silniční kámen na ranní (od čtyř ráno) a ve slunečním žáru zajímavou odpolední směnu. Večer jsem v blízké hospodě vyžahl dvě piva na ex. A žiju. Měl jsem nádherné dětství.
27.01.12, 20:26 mmmmmmmmmm
tak to zkus a řekni
Bez mapy se ti to asi nepovede. Člověče, na základě těch vzdáleností je to přece totéž jako z čisel, to člověk podle tebe samého řešit snad vůbec ani nemůže.
Ale může. Akorát potřebuje tu mapu, když narazí. Teda tu mapu nepotřebuje furt, jako když silniční vzdálenosti, čili ta čísla nemá. Teď jak tohle převést na počítač blbec.
TO JE, OČ TU BĚŽÍ.
Chytráci tvrdí, že nedeterministický počítač rozvětví výpočet vždycky na tolik větví, kolik je z města silnic. Za prvé takový počítač není vůbec nedeterministický, za druhé tohle z čísel vyčteš, ale tak pracně, že tě to přejde. Potřebuješ zas tu mapu...
Možná se mýlím, ale myslím, že nejkratší cesta je nejbližší kružnici. To je jeden z dokonalých tvarů. Simulace tohohle by snad na počítači taky šla, ale pěkně děkuju.
27.01.12, 03:53 pavelhouser
no nevim
u tech desitek mest nejake reseni najdete, asi i docela dobre, ale zda skutecne nejlepsi, to tedy pochybuju. (ps: bez mapy si ji muzete nakreslit na zaklade tech vzdalenosti; ba musite, jen z cisel to clovek resit snad vubec ani nemuze...)
24.01.12, 08:44 mmmmmmmmmm
TSP řeší člověk levou zadní.
Vezmi mapu a uvidíš. A to docela rychle i při několika desítkách měst. Pokud ti ovšem nějaký matematický fundamentalista tu mapu nesebere a nenechá ti jen silniční vzdálenosti.
15.12.11, 16:58 pavelhouser
deti
to napadlo pavla housera, a ano, mela to byt provokace. ovsem vychazejici z vlastni zkusenosti se skolskym procesem, jak jsem se tesil, az budu moci chodit na brigady a neco si vydelat. jak jsem chtel resit neco "neznameho", hrat sachy vs. pocitat stupidni vzorecky. jak me bavilo krajet cibuli vs sedet v lavici. se mluvi o "detske praci" jako o zlocinu, a pritom je zde ten desivy skolni proces, kde vas nazenou do tridy a nuti poslouchat nejake kecy, co si clovek muze precist sam. jeste zduraznuji, ze zmena rezimu na tom dle mych zkusenosti zmenila velmi malo. mozna dnes, nejake to domaci vzdelavani, wiki, uceni formou pocitacovych her... (nebo ta encyklopedie, jak byla v knize Diamantovy vek)
no, jeste by nekdo mohl vymyslet provokativni uvahu, jak ten, kdo deti do skoly neposila, se chova naopak k nim prospesne :-)
14.12.11, 13:12 MartinP
!?!
> 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)?
Proboha, to napadlo Williama Cooka, nebo Pavla Housera?!? Dotyčný asi nemá moc dobrý vztah k dětem... :-(
Napsat vlastní komentář
Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.