Neinformovane-prohledavani.md

# 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](Stavovy-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í](Informovane-prohledavani) 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.** ```mermaidflowchart 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čí. | Vlastnost | Hodnota ||---|---|| Úplnost | **ne** || Optimálnost | **ne** || Čas | `O(b^m)` || Paměť | `O(b·m)` - lineární | 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). | Vlastnost | Hodnota ||---|---|| Úplnost | **ano** (pro konečné `b`) || Optimálnost | **ano**, podle délky cesty || Čas | `O(b^d)` || Paměť | `O(b^d)` - exponenciální | 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`: | Hloubka | Uzlů | Čas | Paměť ||---|---|---|---|| 2 | 1 100 | 0,11 s | 1 MB || 4 | 111 100 | 11 s | 106 MB || 6 | 10^7 | 19 min | 10 GB || 8 | 10^9 | 31 h | 1 TB || 10 | 10^11 | 129 dnů | 101 TB | 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](Stavovy-prostor#elementární-versus-kompoziční-operátor-a-proč-na-tom-záleží), 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š.** | Vlastnost | Hodnota ||---|---|| Úplnost | **ano** (konečné `b`) || Optimálnost | **ano** (rovnoměrná cena) || Čas | `O(b^d)` || Paměť | `O(b·d)` - lineární | 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 | Vlastnost | DFS | DLS | BFS | UCS | IDS ||---|---|---|---|---|---|| Úplnost | ne | ano* | ano* | ano* | **ano*** || Optimálnost | ne | ne | ano* | ano* | **ano*** || Čas | `O(b^m)` | `O(b^ℓ)` | `O(b^d)` | `O(b^(C*/ε))` | `O(b^d)` || Prostor | `O(b·m)` | `O(b·ℓ)` | `O(b^d)` | `O(b^(C*/ε))` | **`O(b·d)`** | 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 | Příznak | Kde je problém ||---|---|| Program se zacyklí | chybí evidence navštívených stavů; DFS a DLS se do cyklu vždycky vrátí || `MemoryError` nebo swapování | BFS nebo UCS na hlubokou úlohu - přepiš na IDS || Vrátí platné, ale zbytečně dlouhé řešení | použil jsi DFS tam, kde jsi chtěl optimalitu || Vrátí nejkratší, ale ne nejlevnější řešení | použil jsi BFS na graf s různými cenami hran - chce to UCS || „Nenalezeno", ale řešení existuje | DLS s příliš malým `ℓ` || IDS je pomalejší než BFS | strom má malý faktor větvení (`b` blízko 1), pak se opakování neamortizuje | ## 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í](Informovane-prohledavani)** - totéž, ale s odhadem vzdálenosti k cíli, tedy A*- **[Lokální prohledávání](Lokalni-prohledavani)** - když tě cesta nezajímá a chceš jen dobrou konfiguraci- **[Hry a herní strom](Hry-a-herni-strom)** - prohledávání, do kterého mluví protihráč- **[Dekompozice a AND/OR grafy](Dekompozice-a-AND-OR-grafy)** - druhá cesta, jak se vyrovnat s velkým prostorem