Student World

Jakým způsobem se dostat bludištěm, nebo se v něm alespoň neztratit a vrátit se na své místo? Pokud nemáme nic na způsob Ariadniny nitě, obvykle se jako nejbezpečnější algoritmus uvádí pravidlo pravé (respektive levé) ruky. Opravdu nemáme žádnou jinou možnost?

Pravidlo pravé ruky (tj. jít stále s rukou na jedné stěně, eventuálně vždy zahnout na jednu stranu) nám totiž zajišťuje pouze to, že se v bludišti neztratíme. Můžeme najít východ, nicméně s trochou smůly ho můžeme i přehlédnout. Univerzální je proto následující řešení:

– z křižovatky odejít kteroukoliv chodbou, která dosud nebyla použita pro příchod ani pro odchod
– pokud již všechny byly použity, vraťte se a pokračujte stejně dále.

Pokud řešení existuje, bude v tomto případě cesta z bludiště nalezena.

Zdroj: Stanislav Vejmola, Konec záhady hlavolamů, SPN, Praha, 1986 (autor napsal i další knihy s podobnou tematikou, v 90. letech vyšla např. Chvála bludišť – tyto publikace se snaží přístupnou formou a bez přebytku matematické terminologie přiblížit čtenářům matematické systémy, která se používají k řešení bludišťových úloh – tzv. teorii grafů. Do teorie grafů přitom spadá celá řada "typických" úloh, např. Problém obchodního cestujícího, při jehož řešení se poprvé uplatnily DNA počítače :-)).

autor Pavel Houser