Student World

Hned na úvod: bludištěm je v tomto článku myšlena síť s větvením, nikoliv zakroucená cesta typu říčního meandru, která sice na první pohled vypadá složitě a nepřehledně, ale bloudícímu poutníkovi (bez ohledu na to, zda se jedná o člověka či počítačový program) nedává v žádném okamžiku možnost volby.
Zcela obecný návod na to, jak vybloudit z labyrintu, zřejmě neexistuje, koneckonců labyrint ani žádný východ umožňovat vůbec nemusí a všechny chodby mohou nakonec končit slepě. Jednotlivé metody si tedy jako cíl samozřejmě kladou vybloudění z bludiště, nicméně jako minimální variantu nabízejí bezpečný návrat na výchozí místo (tedy něco jako obdoba remízy v případě šachových programů). Použitou metodou je prohledávání stavového prostoru.
Pokud naproti tomu známe bludiště jako celek, můžeme ho znázornit jako graf (opět viz náš vložený článek). Uzly grafu jsou pak křižovatky, konce slepých cest, východy a uzavřené (odjinud nedostupné) prostory. Hrany našeho grafu jsou veškeré spojnice (cesty).

Pravidlo jedné ruky
Nejčastěji se pro vybloudění z bludiště uvádí postup "pravidla jedné ruky" to znamená, že na všech křižovatkách musíte vždy zabočit na stejnou stranu. Toto řešení nicméně není zcela univerzální, protože pomíjí situaci, kdy se východ z bludiště nachází v místech se specifickou topologií (v rámci příslušné terminologie se tato místa označují tzv. ostrovy).

Univerzálnější postupy
Z báje o Théseovi je samozřejmě známé použití nitě. Na každé křižovatce se pak postupuje tak, že se vydáte chodbou, kde je minimum nití (ideálně žádná, neboť to je místo, kde jste dosud nebyli). Samozřejmě, nit lze nahradit např. určitým systémem poznámek psaných na zeď (stejně jako při použití nitě lze v jedné variantě nit zpět namotávat, i při psaní na zeď lze buď zprávy pouze zezdola připisovat, nebo je při návratu na stejné místo mazat/škrtat).
Něco podobného činí příslušné algoritmy. Úloha je v tomto případě ulehčena tím, že funkce se samy rekurzivně vyvolávají. Další ulehčení je pak dáno faktem, že v rámci matematické reprezentace bludiště lze samozřejmě snadno pracovat s nástroji typu "nekonečné" nitě, jejichž nasazení v reálném světě je naopak poněkud problematické.
Zájemcům o tuto problematiku mohu doporučit mj. knihu Stanislava Vejmoly Chvála bludišť (Státní pedagogické nakladatelství, Praha, 1991), kde najdeme popis řady variant prohledávání bludiště hledání cesty od vchodu do bludiště, prozkoumávání bludiště, kde jsme již zabloudili, algoritmy, jejichž cílem je nejen z bludiště vybloudit, ale navíc se jako kritérium úspěšnosti používá rychlost nalezení východu (ta může být zase měřena buď počtem úseků, nebo jejich délkou atd., atd.).

Generování bludišť
Jakýmsi inverzním postupem k problému vybloudění je naopak generování bludišť. Ta se pak mohou použít např. v počítačových i nepočítačových hrách typu RPG (Role Playing Games). Cílem hráče zde ovšem není pouze najít cestu bludištěm, ale spíše se vypořádat s úkoly a nástrahami, které do jeho jednotlivých částí lokalizoval tvůrce hry. Vlastní tvorba bludiště ve smyslu jeho topologie je tedy pouze jednou z částí tvorby scénáře hry.
Existuje celá řada programů generujících podle zvolených podmínek nějaké bludiště. Některé z těchto programů jsou volně stažitelné prostřednictvím Internetu, často včetně podrobně okomentovaného zdrojové-ho kódu. K tomu se samozřej-mě přidává řada víceméně grafických programů pro následnou úpravu prvotně vytvořeného bludiště.
Podívejme se na několik relevantních internetových adres, kde se můžeme setkat s tvorbou bludišť:

http://www.jofo.ee/labyrinth/medium.html Toto je jedna ze stránek, kde se počítačově generují labyrinty, autor slibuje, že při každé návštěvě stránky jiný. Bludiště bohužel není interaktivní.
http://www.speakeasy.org/~cruiser1/labyrnth/java.htm Javový applet tvoří labyrinty. Lze získat i zdrojový kód programu.
http://www.speakeasy.org/~cruiser1/labyrnth.htm Zde kromě programu na vytváření labyrintů najdeme i jeho bratříčka, který tvoří puzzle, dále odkazy na další podobně orientované stránky.
http://www.amz.com/maze/2n.html Zde můžete přímo on-line procházet labyrintem.
http://www.pom.wb.utwente.nl/staff/hans/index.htm I odtud si lze stáhnout program generující labyrinty. Jsou zde také odkazy týkající se algoritmů pro programy této kategorie.
http://www.speakeasy.org/~cruiser1/labyrnth/algrithm.htm Charakter a dělení labyrintů a jejich topologie, jednotlivé typy, 2D, 3D i vícedimenzionální. Najdeme zde návody na kreslení bludišť i mimo počítače.

Malé shrnutí a slovníček některých pojmů
Ve své původně zamýšlené verzi se tento článek měl jmenovat "Inteligentní algoritmy pro deskové hry". Je jasné, že to obnáší podstatně širší pole, kde jsou šachové programy pouze jednou z aplikací.
Spadají sem samozřejmě programy pro jiné stolní deskové hry (dáma, piškvorky, GO apod.). V tomto článku se soustředíme na algoritmy pro nalezení optimální cesty z bludiště. I to je však pouze jedna z aplikací.
Obecně nám zde jde o všechny inteligentní (nebo "inteligentní") systémy se schopností vytvářet si vnitřní strojový model světa a pracovat s ním. Ve většině úloh máme přitom definován počáteční stav a požadovaný koncový stav (buď výčtem těchto stavů jako v případě nějaké jednodušší skládačky, nebo podmínkami, které konečný stav musí splňovat v šachové partii např. mat, v bludišti stav mimo chodby). Mezi počátkem a koncem leží svět "řešení úloh" (míněno jako termín z oblasti umělé inteligence).
Množina všech stavů prostředí se přitom označuje jako stavový prostor a reprezentuje se orientovaným grafem. Graf přitom v tomto případě zahrnuje útvar složený z bodů (neboli uzlů) a jejich spojnic (nebo hran).
Často (např. v šachách) nemáme předem k dispozici žádný jednoznačný výpočetní postup, který by nás dovedl k cíli. V takových případech se postupuje metodou prohledávání stavového prostoru.
V rámci tohoto oboru se lze setkat i s celou řadou souvisejících pojmů (produkční systém, báze dat, produkční pravidla, řídicí mechanismus). Zájemce lze odkázat na další prameny (stránky na Internetu existuje ale i řada prací v tištěné podobě), které se věnují problematice umělé inteligence a to v poněkud vědečtější a vážnější rovině, než jsme to udělali my

autor Pavel Houser