Klávesové zkratky na tomto webu - základní
Přeskočit hlavičku portálu

Získejte 1 000 000 dolarů
za vyřešení hádanky

aktualizováno 
Zní to neuvěřitelně, ale za nalezení nejkratší možné cesty obchodního zástupce mezi několika městy můžete získat milion dolarů. Odměnu vypsal Clayův matematický institut (CMI) v Cambridgi v Massachusetts. Máte šanci milion získat právě vy?
Peníze, investice

Peníze, investice | foto: Profimedia.cz

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.

popisekDAŇOVÉ FORMULÁŘE ONLINE: STAHUJTE ZDE
Opět vám pomáháme s daněmi

Podobně 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.



Hlavní zprávy

Další z rubriky

Simone Giovannozzi
Netradiční zaměstnání: Se psy hledá lanýže a slušně vydělává

Říkají mu Simone Tartufi, tedy Simone Lanýž. To proto, že se živí prodejem aromatických hub. Dodává lanýže do špičkových italských, francouzských, německých...  celý článek

Ilustrační snímek
Vybalancujte čas mezi prací a soukromím. Psycholog radí, jak na to

Věnovat se naplno práci a osobní život potlačit na minimum? Nebo brát zaměstnání jen jako nutnost a žít až večer s rodinou? Ani jedno není správně. Je třeba...  celý článek

Ilustrační snímek
Tři věci, které nejvíce vytáčejí zaměstnance v kancelářích

Někdy je to v kanceláři o nervy a o zdraví. Zvlášť, když vypuknou hádky mezi kolegy kvůli relativním maličkostem. Horko, hluk, vyrušování, co teď nejvíce vadí...  celý článek

Najdete na iDNES.cz



mobilní verze
© 1999–2017 MAFRA, a. s., a dodavatelé Profimedia, Reuters, ČTK, AP. Jakékoliv užití obsahu včetně převzetí, šíření či dalšího zpřístupňování článků a fotografií je bez souhlasu MAFRA, a. s., zakázáno. Provozovatelem serveru iDNES.cz je MAFRA, a. s., se sídlem
Karla Engliše 519/11, 150 00 Praha 5, IČ: 45313351, zapsaná v obchodním rejstříku vedeném Městským soudem v Praze, oddíl B, vložka 1328. Vydavatelství MAFRA, a. s., je členem koncernu AGROFERT.