Neinformované prohledávání

Prohledávání do šířky najde vždycky nejkratší cestu. Zní to jako jasná volba - a je to důvod, proč se v praxi tak často nepoužije. Při faktoru větvení deset a hloubce deset potřebuje 101 TB paměti. Ne času. Paměti. Program neskončí špatně, on vůbec nedoběhne, protože ho operační systém zabije dřív.

Tohle je celá pointa téhle stránky. Pět metod, které se tu probírají, se neliší tím, co najdou. Většina z nich najde totéž. Liší se tím, kolik toho musí mít naráz v paměti, a to je jediné číslo, které v reálné úloze rozhoduje.

Předpokládá to stavový prostor - hlavně zápis (X, Y, R) a význam parametrů b, d, m, ℓ. Kde se využívá odhad vzdálenosti k cíli, je řeč o informovaném prohledávání a to je jiná stránka.

Co znamená „neinformované"

Algoritmus zná jen tři věci: počáteční stav, cílový test a přechodovou funkci. Nemá nic, čím by odhadl, jestli je jeden stav blíž k cíli než druhý.

To vypadá jako handicap a je to tak. Zároveň je to ale jediné, co občas máš - u úlohy, kde neumíš vzdálenost k cíli odhadnout, ti nezbývá nic jiného. A hlavně: informované metody jsou postavené přesně na těchhle a liší se jen tím, podle čeho vybírají další uzel.

Všech pět metod má stejnou kostru. Drží se seznam uzlů k rozvinutí (fronta, anglicky frontier), z něj se vždycky jeden vybere, otestuje se na cíl a jeho následníci se přidají zpátky. Celý rozdíl mezi DFS, BFS a UCS je v tom, ze kterého konce fronty se bere.

flowchart TD
    A[fronta obsahuje počáteční stav] --> B{fronta prázdná?}
    B -->|ano| C[řešení neexistuje]
    B -->|ne| D[vyber uzel z fronty]
    D --> E{je to cíl?}
    E -->|ano| F[vrať cestu]
    E -->|ne| G[expanduj: přidej následníky do fronty]
    G --> B

Ten diagram platí pro všech pět metod bez jediné změny. Metody se liší výhradně implementací kroku „vyber uzel z fronty".

DFS: zásobník a nekonečná větev

Prohledávání do hloubky expanduje vždy nejlevější a nejhlubší neexpandovaný uzel. Implementuje se zásobníkem (LIFO) nebo prostě rekurzí, což je důvod, proč ho většina lidí napíše dřív, než se ho naučí.

Ta lineární paměť je celý důvod, proč DFS pořád existuje. V paměti drží jen aktuální větev a sourozence uzlů na ní, nic víc.

Hlavní problém je nekonečná větev. Když stavový prostor obsahuje cyklus nebo nekonečně dlouhou cestu, DFS do ní zaleze a nikdy se nevrátí. Řešení není tam dole, ale program to nezjistí, protože se nikdy nepodívá vedle.

Optimálnost neplatí ani u konečných stromů. DFS vrátí první nalezené řešení, ne nejlepší. Když je vlevo cesta o dvaceti krocích a vpravo o dvou, dostaneš tu dvacetikrokovou.

DLS: zarážka a její nepříjemný důsledek

Depth-Limited Search řeší nekonečnou větev nejhloupějším možným způsobem: zavede limit ℓ a hlouběji nejde. Čas O(b^ℓ), paměť O(b·ℓ).

Tím se ale otevře nová díra:

Neúspěch má dva výklady. Když DLS vrátí „nenašel jsem", nevíš, jestli řešení neexistuje, nebo jestli je jen hlouběji než ℓ. To jsou dvě úplně různé informace a algoritmus je nerozliší.

Z toho plyne, kde přesně DLS selhává:

• ℓ < d - řešení je hlouběji než limit, metoda ho nenajde a není úplná.
• ℓ > d - metoda může najít hlubší řešení dřív než to mělké, takže není optimální.

Trefit ℓ = d bys musel znát d předem, a kdybys ho znal, nemáš co hledat. Právě tenhle rozpor vyřeší IDS o kousek níž.

BFS: nejkratší cesta za cenu, kterou nezaplatíš

Prohledávání do šířky expanduje vždy nejlevější uzel s nejmenší hloubkou, takže prochází stavový prostor po vrstvách. Implementace je fronta (FIFO).

Pozor na to slovo v optimálnosti: podle délky cesty. BFS najde cestu s nejmenším počtem kroků, ne s nejmenší cenou. Když hrany stojí různě, BFS vrátí levnou trasu jen náhodou.

Kolik to doopravdy stojí

Tohle je nejužitečnější tabulka na téhle stránce. Pro b ≈ 10:

Podívej se na řádek pro hloubku 6. Devatenáct minut je otravné, ale zvládnutelné. Deset gigabajtů na běžném notebooku znamená, že se to začne odkládat na disk a těch devatenáct minut se změní na hodiny. Paměť narazí dřív než čas a je to u BFS pravidlo, ne výjimka.

Zapamatuj si to i takhle: paměť je u BFS O(b^d), u DFS O(b·d). Ta jediná změna mocniny na násobení je rozdíl mezi 101 TB a několika stovkami kilobajtů.

UCS: když hrany nestojí stejně

Uniform-cost Search je BFS přepsané pro obecné ohodnocení hran. Každý uzel n má cenu g(n) naměřenou od startu a fronta je uspořádaná podle g - tedy prioritní fronta, ne obyčejná FIFO.

Vlastnosti: úplnost a optimálnost ano, ale s podmínkou. Cena každé hrany musí být alespoň nějaké ε > 0. Čas i paměť jsou O(b^(C*/ε)), kde C* je cena optimálního řešení.

Ten exponent C*/ε je nepříjemný. Neříká hloubku cíle, ale kolik nejlevnějších kroků by se do ceny optimálního řešení vešlo. Když máš v grafu jednu hranu za 0,001 a řešení stojí 100, exponent je sto tisíc, i kdyby byl cíl tři kroky daleko.

Odtud plyne i ta podmínka ε > 0. Hrany s nulovou cenou by algoritmus nechaly donekonečna kroužit po cestě, která nic nestojí a nikam nevede.

Kdy použít UCS místo BFS: vždycky, když operátory nestojí stejně. Příkladem je hra 4 kameny ze stavového prostoru, kde přeskok přes dvě figury stojí 2 a ostatní tahy 1. BFS by tam vracelo řešení s nejmenším počtem tahů, což nemusí být to nejlevnější.

IDS: metoda, která opakuje práci a vyplatí se to

Iterative Deepening je jednoduchý nápad, který zní jako plýtvání: pouštěj DLS pořád dokola s limitem ℓ = 0, 1, 2, 3, ..., dokud něco nenajdeš.

Podívej se na ta čísla ještě jednou. Čas jako BFS, paměť jako DFS, a přitom je to úplné i optimální. To je celý důvod, proč je IDS doporučená neinformovaná strategie pro velké stavové prostory.

První reakce každého bývá, že opakované procházení mělkých vrstev musí být drahé. Není, a důvod je v tom, že stromy jsou dole širší než nahoře. Poslední vrstva má b^d uzlů, předposlední b^(d-1), tedy b-krát méně. Práce v ní odvedená se tedy počítá jen jako zlomek celku.

Konkrétně při b = 10 a d = 5 vygeneruje BFS zhruba 111 100 uzlů, IDS zhruba 123 450. Přeplácíš deset procent času a ušetříš pět řádů paměti.

Souhrnná tabulka

Hvězdička znamená „za určitých podmínek" - typicky konečný faktor větvení b a u cen ε > 0. U BFS a IDS platí optimálnost jen při rovnoměrné ceně hran.

Který si vybrat

Ceny hran nejsou stejné → UCS. Nic jiného ti optimální řešení nedá.

Ceny jsou stejné a prostor je velký → IDS. Je to výchozí volba a v drtivé většině případů správná.

Ceny jsou stejné a prostor je malý → BFS. Když se ti to do paměti vejde, je to jednodušší na napsání a nedělá práci dvakrát.

Potřebuješ jakékoliv řešení co nejrychleji a strom je konečný → DFS. Typicky u generování konfigurací, kde je každý list řešením.

DLS samo o sobě → prakticky nikdy. Používá se jako vnitřek IDS. Samostatně jen tam, kde limit vyplývá z fyziky úlohy - třeba počet tahů, který v dané hře může vůbec nastat.

Co se na tom nejčastěji rozbije

Co si odnést

Rozhoduje paměť, ne čas. O(b^d) versus O(b·d) je jediné číslo, které v reálné úloze poznáš.

Všechny metody mají stejnou kostru. Liší se výhradně tím, ze kterého konce fronty berou uzel.

BFS je optimální podle délky, ne podle ceny. Na graf s různě drahými hranami patří UCS.

DLS má dvojznačný neúspěch. Nevíš, jestli řešení není, nebo je hlouběji.

IDS je výchozí volba. Čas jako BFS, paměť jako DFS, úplné i optimální. Opakovaná práce stojí zhruba deset procent.

Kam dál

• Informované prohledávání - totéž, ale s odhadem vzdálenosti k cíli, tedy A*
• Lokální prohledávání - když tě cesta nezajímá a chceš jen dobrou konfiguraci
• Hry a herní strom - prohledávání, do kterého mluví protihráč
• Dekompozice a AND/OR grafy - druhá cesta, jak se vyrovnat s velkým prostorem