Tzv. „travelling salesman problem“ patří mezi sedm dosud nezodpovězených otázek matematiky. Milionovou odměnu nabízí CMI za rozluštění každé ze sedmi nejdůležitějších otevřených oblastí.
„Travelling salesman problem“ patří svým využitím spíše do sféry obchodu a výroby než matematiky. Uplatnit se dá všude tam, kde je nutné zkombinovat více možností. Například vybrat nejkratší možnou cestu obchodního zástupce mezi více městy, sestavit automobil co nejrychlejší kombinací jednotlivých úkonů a vlastně i složit okamžitě libovolné puzzle. Hádanka odolává vyřešení již několik desetiletí. Problém poprvé formuloval vídeňský matematik Karl Menger v roce 1930.
Úspěšný řešitel ušetří světovým firmám obrovské peníze za pohonné hmoty a ušetří čas při výrobě. V současné době se používají při podobných operacích jen odhady.
Co však vypadá snadné, tak lehké není. Jestliže máme daný počet měst a náklady na cestování od jednoho města k druhému, jaká je nejlevnější okružní cesta, při které navštívíme všechna města přesně jednou a vrátíme se do výchozího bodu? U dvou měst má obchodní zástupce dvě možnosti, v jakém pořadí města navštívit. Nejdříve pojede do A, pak do B anebo naopak, matematicky 2! = 2 x 1 = 2.
U tří měst si může vybrat ze 3 x 2 x 1 = 6 možností,
u čtyř měst 4 x 3 x 2 x 1 = 24 možností,
u pěti měst 5 x 4 x 3 x 2 x 1 = 120 možností
a tak dále.
U deseti měst se dostáváme k 3 628 800 možným trasám. Počet kombinací narůstá tak rychle, že již u sedmnácti měst by prověření a porovnání všech možných kombinací trvalo počítači více než v praxi těžko realizovatelných deset let. Přitom kombinace sedmnácti kroků ve výrobě či sedmnácti měst k navštívení je v dnešní době běžným číslem.
DAŇOVÉ FORMULÁŘE ONLINE: STAHUJTE ZDEPodobně funguje i starý trik se šachovnicí. Na první políčko položíte jedno zrnko rýže, na druhé dvakrát tolik, tj. dvě zrnka, na další políčko čtyři, na další osm a tak dále. Velmi brzy se dostanete od jednoho zrníčka k tunám rýže. Zkuste si to. U obchodního zástupce je nárůst ještě dramatičtější, protože nenásobíte počet možných tras konstantní dvojkou, ale stále vyšším a vyšším číslem (u dvou měst dvojkou, u třech trojkou a tak dále).
Na stejném principu vyhlásila firma Ertl Toys v roce 1999 odměnu milion liber za složení puzzle Eternity. Opět šlo o zkoušení kombinací. Na první pohled se skládačka nelišila od běžných hlavolamů, obsahovala dvěstědevět jednobarevných dílků. Mnoho řešitelů se pokoušelo o software, ale skončili na neuvěřitelně dlouhém množství času, které by bylo k prověření správné kombinace potřeba. Náhodné zkoušení všech pozic by trvalo se současnou technikou milióny let. Puzzle bylo jednorázově složeno dvěma řešiteli pomocí správného odhadu, počítačů a velké dávky štěstí. Ale obecné řešení stále neexistuje.
Neřešitelnost se využívá také u mnoha bezpečnostních kódů a šifer současnosti. S rozluštěním hádanky, zjednodušením a zrychlením výpočtu, by padla i část zabezpečení internetu. Kódování založené na velkém množství kombinací se používá při šifrování zpráv i elektronickém podepisování.
Příklad je jednoduše pochopitelný. Jedná se o jediný ze sedmi matematických příkladů současnosti, kde matematik Keith Devlin uvádí, že má šanci i laik s dobrým nápadem. Možná je potřeba nová myšlenka a typ počítače fungující na úplně jiném principu než dnes. Odměna je vypsána za samotné vyřešení i za dokázání, že příklad zjednodušit nelze a žádný jednodušší způsob, jak velké množství kombinací prověřit, neexistuje. V tomto případě by došlo k obrovské úspoře energie a času mozků, které by se již problémem nemusely zabývat.
