Problém obchodního cestujícího

Tweet

aneb chcete miliony dolarů?

Představte si, že jste obchodní cestující z Rumburku. A máte navštívit Varnsdorf a Jiřetín. Jak to udělat co nejúsporněji? No prostě pojedete z Rumburku do Jiřetína, pak do Varnsdorfu a zpět do Rumburku. Nebo obráceně. Nejdřív vyrazíte směr Varnsdorf, po něm vás čeká Jiřetín a cíl je opět Rumburk. Jednoduché, nemyslíte? Ale dokážete to zobecnit? Ne pro dvě, ale pro x měst.

Představte si totiž, že potřebujete jet ještě do Nového Boru a Děčína. Jak to vymyslet tak, aby jste každé město navštívili jen jednou, jeli co nejkratší cestou a ještě se vrátili zpět do výchozího místa?

JistÄ›, lze to vypočítat matematicky. U dvou mÄ›st máme 2×1 kombinací, tedy 2 možnosti (tzn. nejdřív JiÅ™etín a až pak Varnsdorf, nebo obrácenÄ›), ale u 4 mÄ›st už je to 4x3x2x1, tedy 24 možnosti a to nemluvím o situaci, kdy potÅ™ebujete navÅ¡tívit 15 mÄ›st, kdy na vás čeká již neuvěřitelných 1 307 674 368 000 kombinací, tedy více jak jeden bilion. A to je právÄ› ten problém. Prověření takového množství kombinací již prostÄ› není technicky možné, i nejvýkonÄ›jší počítače by to počítali roky (nejrychlejší stroj na svÄ›tÄ› by 17 mÄ›st zvládl asi za 10 let).

Tento matematický oříšek je jedním ze sedmi dosud nevyÅ™eÅ¡ených problémů a odolává Å™eÅ¡ení již od roku 1930. Pokud máte nápad, jak jej vyÅ™eÅ¡it tak si ho určitÄ› nenechávejte pro sebe. Nejen že budete nesmírnÄ› úspěšný a známý ze dne na den, ale hlavnÄ› získáte sluÅ¡né bohatství. Stačí zajet do Cambridge do Massachusetts kde oznámíte na ClayovÄ› matematickém institutu vyÅ™eÅ¡ení „travelling salesman“ problému a získáte 1 milion dolarů. Navíc už pro vás nebude problém vyÅ™eÅ¡it Eternity II puzzle, které se skládá z 256 dílků a za jehož Å™eÅ¡ení získáte 2 miliony dolarů. To už stojí za trochu pÅ™emýšlení, ne?