Algoritmizácia a programovanie - Slovne popísané algoritmy - Metódy hľadania cesty z bludiska :)

1.xV jednoduchom labyrinte vyfarbite slepé uličky a slučky. Do stredu sa potom dostanete zostávajúcimi cestami. Vyberte si najkratšiu z nich.

Táto metóda nie je aplikovateľná v zložitejších prípadoch. 

2.xPri ceste labyrintom sa stále dotýkajte jednou rukou (ľavou alebo pravou) steny.

Je to jednoduchá metóda, ale nehodí sa pre:

• labyrint s dvoma vchodmi a cestou, ktorá vchody spája, ale neprechádza cez stred labyrintu,
• labyrint, v ktorom sa cesty kľukatia okolo stredu. 

3. Francúzsky matematik Charles Pierre Trémaux (1859–1882) vymyslel všeobecnú metódu, pomocou ktorej sa dostanete z každého labyrintu:

3.1xPri ceste labyrintom kreslite čiaru na pravú stenu.

3.2xVždy,  keď prídete k novému rázcestiu, vyberte si hociktorú cestu.

3.3xAk prídete novou cestou k starému rázcestiu alebo do slepej uličky, vráťte sa späť cestou, ktorou ste prišli.

3.4xAk sa budete vracať starou cestou a narazíte na staré rázcestie, choďte ľubovoľnou novou cestou, ak taká existuje. Ak nie, pokračujte niektorou starou cestou. Nikdy však nesmiete vstúpiť do chodby označenej z oboch strán. 

Algoritmus Trémauxa je taký jednoduchý, že ho dokáže použiť každý, i keď cesta z bludiska týmto spôsobom môže trvať dlhší čas.

Hodnotenie užitočnosti článku:

• ← Algoritmizácia a programovanie - Slovne popísané algoritmy - Hra Zápalky :)
• Algoritmizácia a programovanie - Slovne popísané algoritmy - O zločincoch a diamantoch :) →