Problém obchodního cestujícího

Jak objet svět co nejkratší cestou?

Na mapě a glóbu máte možnost stát se obchodním cestujícím. Ten potřebuje najít co nejkratší okružní trasu přes všechna města vyznačená kolíčky. Trasa se znázorňuje lankem ukazujícím její délku a značkou vyznačující nejkratší možnou cestu. Problém je možné řešit tak, že vyzkoušíme délku všech možných cest a z nich vybereme tu nejkratší, tato metoda se označuje jako řešení problému hrubou silou. Počet těchto cest však s rostoucím počtem měst velmi rychle roste. Například pro 28 měst dostaneme neuvěřitelných 5 444 434 725 209 176 080 384 000 000 možností.

Sdílejte!

Vytvořte si pracovní list

Úkoly k exponátu

Chcete obohatit svou návštěvu VIDA! expozice? Nachystali jsme pro vás k jednotlivým exponátům úkoly, ze kterých si můžete vytvářet pracovní listy. Jejich součástí bude i mapa expozice, díky které pak u nás konkrétní exponáty hravě najdete. Vyvinuli jsme tuto službu primárně pro učitele a jejich žáky a studenty, ale využít ji může kdokoli. Tak vzhůru do světa poznání!

Věkové doporučení

Věkové doporučení: 2 třída - 5 třída

Zjisti, kolik světadílů navštíví náš obchodní cestujcí.

Věkové doporučení: 6 třída - 9 třída

Zkus odhadnout, jaké země musíš při řešení problému tohoto obchodního cestujícího navštívit?

Věkové doporučení: Střední škola - Dospělý

Zkus vyhledat co nejhorší řešení pro obchodního cestujícího, tedy co nejdelší celkovou trasu. Obchodník musí navštívit všechna města a žádné z nich nesmí navštívit více než jednou.

Odebírejte NEWSLETTER

Vymýšlíme pořád něco nového a vy o tom můžete vědět mezi prvními, stačí tady teď nechat svůj e-mail.

VIDA! Program

272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234