Průchod bludištěm je pro lidi výzvou už po několik století. Vzpomeňme si například na řecké báje a pověsti, na pověst o Mínotaurovi. Theseus chtěl zachránit Ariadnu a proto musel projít bludiště, najít Minutaura, zabít ho a zase se vrátit zpátky. Aby se v bludišti neztratil, dostal od Ariadny niť, pomocí které si označoval cestu. Když postupoval do neznámých míst bludiště, tak niť odmotával. Když se vracel, tak niť namotával zpátky na klubko. Namotávání niťě ho vyvedlo zpátky před vchod do bludiště.

Asi každý by dokázal pomocí nitě a křídy projít bludiště, ale jak to naučit počítač?1 Bludiště si v počítači reprezentujeme jako graf. Vrcholy, do kterých se lze dostat z výchozího místa nazveme dosažitelné. Pro jednoduchost předpokládejme, že všechny vrcholy bludiště jsou dosažitelné. Později si ukážeme, jak se tohoto předpokladu zbavit.


Efektivní průchod grafu musí splňovat následující body:

  • každou hranou projdeme maximálně jednou (jednou tam a jednou zpět)
  • hranou se vrátíme až když z vrcholu nevede další cesta
  • hranou vedoucí do navštíveného vrcholu se ihned vrátíme

Algoritmus splňující výše uvedené body je konečný a korektní. Konečnost plyne z prvního bodu, protože v každém kroku projdeme po jedné hraně, každou hranu jen jednou a hran je jen konečně mnoho. Korektnost algoritmu v našem případě znamená, že projdeme všechny vrcholy a hrany, které jsou dosažitelné z výchozího vrcholu. Pokud by existoval algoritmem nenavštívený, ale jinak dosažitelný, vrchol $v$, tak se podívejme na cestu $P$ vedoucí z výchozího vrcholu do $v$. Taková cesta musí existovat, protože vrchol $v$ je dosažitelný. Protože začátek cesty $P$ byl navštívený a konec nebyl, tak na cestě existuje neprošlá hrana vedoucí z navštíveného vrcholu do nenavštíveného. To je ale spor s druhým bodem.

Časová složitost algoritmu je $\OO(n+m)$, protože čas za průchod naúčtujeme2 hranám, které procházíme, a případnou práci ve vrcholech vrcholům.3


Efektivní průchod grafu má dvě možné implementace:

  1. Průchod do hloubky (DFS z anglického Depth First Search) — podle tohoto algoritmu postupuje i Theseus. Před bludištěm si uváže jeden konec nitě na strom a vstoupí dovnitř. V prvním vrcholu si vybere jednu možnou cestu/hranu a projde po ní do dalšího vrcholu. Aby Theseus neměl zmatek v tom, které hrany už prošel, tak si všechny hrany, které prochází označuje křídou — a to na obou koncích. V každém vrcholu, do kterého Theseus dorazí, provede následující:
    • Pokud na zemi najde položenou niť, tak ví, že už ve vrcholu byl a že se do něj při namotávání nitě zase vrátí. Odloží tedy další prozkoumávání tohoto vrcholu na později, provede čelem vzad a začne namotávat niť na klubko. To ho dovede zpátky do předchozího vrcholu.
    • Pokud na zemi žádnou niť nenajde, tak se vydá první možnou neprošlou hranou. Pokud by taková hrana neexistovala, tak je vrchol zcela prozkoumán. V tom případě Theseus neztrácí čas a začne namotávat niť na klubko. Tím se dostane zpátky do předchozího vrcholu.

    Tímto postupem prozkoumá celé bludiště a nakonec se vrátí do výchozího vrcholu.

    Jak to provést v počítači? Křídu potřebujeme proto, abychom se nezacyklili. Abychom každou hranu prošli jen jednou. Místo křídy si pro každou hranu zřídíme proměnnou označující, jestli jsme hranu prošli. Klubíčko a niť potřebujeme proto, abychom našli cestu ven z bludiště. Položená niť nám vyznačuje cestu z výchozího vrcholu do aktuálního vrcholu. V počítači nám bude úplně stačit, když si tuto cestu budeme pamatovat jako posloupnost vrcholů na této cestě. Pro uložení této cesty použijeme zásobník. Odmotávání nitě z klubka při postupu do dalšího vrcholu odpovídá přidání vrcholu na zásobník. Namotávání nitě na klubko při návratu zpět odpovídá odebrání vrcholu ze zásobníku.

    Stejně postupuje i backtracking (to je ta metoda “Hrr, na ně! A když to nepůjde, tak coufnem.”). Backtracking je metoda hrubé síly, která vyzkouší všechny možnosti.

  2. Průchod do šířky (BFS z anglického Breadth First Search) — tento průchod (prohledání grafu) si můžeme představit tak, že se do výchozího vrcholu postaví miliarda Číňanů a všichni naráz začnou prohledávat graf. Když se cesta rozdělí, tak se rozdělí i dav řítící se hranou. Předpokládáme, že všechny hrany jsou stejně dlouhé. Graf prozkoumáváme “po vlnách”. V první vlně se všichni Číňané dostanou do vrcholů, do kterých vede z výchozího vrcholu hrana. V druhé vlně se dostanou do vrcholů, které jsou ve vzdálenosti $2$ od výchozího vrcholu. Podobně v $k$-té vlně se všichni Číňané dostanou do vrcholů ve vzdálenosti $k$ od výchozího vrcholu. Kvůli těmto vlnám se někdy průchodu do šířky říká algoritmus vlny. V počítači vlnu nasimulujeme tak, že při vstupu do nového vrcholu uložíme všechny možné cesty do fronty. Frontu průběžně zpracováváme.

    Na následujícím obrázku nalevo je znázorněn průchod do šířky a napravo průchod do hloubky.


Který průchod grafu je lepší? Jak kdy a jak na co. To záleží na tom, jak vypadá graf, který prohledáváme. Někdy je výhodnější jedna metoda o proti druhé, protože budeme potřebovat výrazně méně paměti na uložení zásobníku/fronty. Jindy je to naopak.

Příklad: Dostaneme bludiště, které má tvar čtvercové sítě o rozměrech $n\times n$, a jsou v něm pouze obvodové zdi. Je to takové fotbalové hřiště s mantinely. Někde v bludišti jsme ztratili míč, protože se udělala hrozná mlha. V mlze je vidět jen o malinko víc než na jedno políčko bludiště. Chtěli bychom projít celé bludiště, navštívit každé políčko, a míč najít.4 Vchod do bludiště je pravém horním rohu.

Při použití DFS, ve kterém z každého prozkoumávaného políčka zkoušíme cesty v pořadí nahoru, doprava, dolů a doleva, bude neustále možné pokračovat dále. A to tak dlouho, dokud nezaplníme skoro všechna políčka. Jednoduše řečeno, průchod bludištěm bude vypadat jako dlouhá cesta naskládaná zig-zag po celém bludišti. (Pokud to není jasné, tak si zkuste průchod odkrokovat.) Všechna políčka budou na zásobníku a proto budeme potřebovat zásobník velikosti $\OO(n^2)$. Při použití BFS budeme bludiště procházet v soustředných vlnách a bude nám stačit fronta velikosti $4n$ (nejvýše obvod bludiště). Ve fotbalové analogii to odpovídá vytvoření rojnice.

Takto se zdá, že z paměťových důvodů je lepší použít BFS. Toto zdání ale klame. Podívejme se na další příklad.

Příklad: Jsme na dovolené a bydlíme v hotelu. Hotel má $5$ pater, do kterých se dostaneme výtahem. Na každém patře je dlouhá chodba se dveřmi do $20$ pokojů. Potřebovali bychom zjistit, na kterém pokoji bydlí ta hezká slečna, co jsme ji viděli u snídaně, ale nevíme jak se jmenuje. Rozhodneme se proto projít celý hotel a slečnu najít. Potřebujeme projít všechny místnosti hotelu a v každé nechat vzkaz. Pokud použijeme DFS, vystačíme si se zásobníkem velikosti $3$ (výtah, chodba, pokoj). Při použití BFS budeme potřebovat tak velkou frontu, kolik je v hotelu pokojů, tedy $100$.

Výhodnou BFS je, že prochází vrcholy v pořadí podle nejkratší vzdálenosti od počátku. Pokud tedy hledáme nejkratší cestu, nejmenší počet tahů apod., tak je výhodnější použít BFS.

Příklad: (Koza, vlk a zelí) Na břehu řeky má převozník kozu, vlka a zelí. Do loďky se mu vejde jen jedno zvíře nebo zelí. Jak má převézt kozu, vlka a zelí na druhý břeh, když na žádném břehu nesmí nechat nehlídaného vlka s kozou (vlk by sežral kozu) ani kozu se zelím (koza by snědla zelí)?

Vrcholy grafu jsou stavy které označují, kdo je na kterém břehu. Například VZ|KP značí, že na prvním břehu zůstal vlk se zelím a na druhém břehu převozník s kozou. Přechod po hraně grafu odpovídá převozu zvířete, zelí nebo přejezdu převozníka na protější břeh. Například na začátku jsme se převozem kozy dostali ze stavu KVZP| do VZ|KP. Řešení úlohy lze najít průchodem tohoto grafu a nalezením cesty do vrcholu |KVZP.

Při hledání dalších stavů a kreslení obrázku nevidíme, jak to bude vypadat dál. Chová se to jako opravdové bludiště. Takovéto úlohy se vyskytují celkem často. Graf je “skrytý” a odpovídá možným větvením programu.

Prohledáváme takzvaný “stavový prostor” programu. Pozor, často se necháme zmýlit tím, co je “stav”. Stav zachycuje celou situaci. V předchozí úloze nebylo stavem jen to zvíře, které převážíme přes řeku (koza nebo vlk či zelí). Stav musí obsahovat polohu všech zvířátek a zelí, včetně převozníka.


Podobnou úlohou je proskákání šachovnice šachovým koněm tak, abychom každé políčka navštívili právě jednou. V této úloze není stavem jen poloha naposledy položeného koně a počet umístěných koní. Stavem je “fotka” celé šachovnice. To je poloha všech dosud umístěných koní.

V řadě úloh nám ujasnění si toho, co je stav, pomůže k nalezení řešení.