Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi

Úloha prohledávání je šestice

P = (S, s₀, A, T, G, c),

která splňuje:

1. S je neprázdná množina; její prvky nazýváme stavy;
2. s₀ ∈ S; tento stav nazýváme počáteční stav;
3. A přiřazuje každému stavu s ∈ S konečnou množinu A(s) akcí použitelných ve stavu s; označme 𝒟 = {(s, a) : s ∈ S, a ∈ A(s)} množinu všech dvojic „stav, v něm použitelná akce“;
4. T : 𝒟 → S je přechodová funkce; pro (s, a) ∈ 𝒟 je stav s′ = T(s, a) následník stavu s (po akci a);
5. G ⊆ S je množina cílových stavů;
6. c : 𝒟 → ℝ⁺ = (0, ∞) je cena akce: c(s, a) > 0 je cena použití akce a ve stavu s.

Úloha tedy přesně říká, odkud začínáme, jaké tahy máme v každém stavu k dispozici, kam který tah vede, kolik stojí a kdy jsme v cíli.

Nechť P = (S, s₀, A, T, G, c) je úloha prohledávání a k ∈ ℕ₀. Cesta délky k z počátečního stavu je posloupnost

π = (s₀, a₁, s₁, a₂, …, a_k, s_k)

taková, že pro každé i = 1, …, k platí a_i ∈ A(s_i−1) a s_i = T(s_i−1, a_i). (Pro k = 0 je cesta jen (s₀).)

Cena cesty π je součet cen jejích akcí:

g(π) = ∑_i=1^k c(s_i−1, a_i).

Cesta π je řešení, právě když s_k ∈ G. Označme Π množinu všech řešení. Je-li Π ≠ ∅, je optimální cena

C* = min {g(π) : π ∈ Π}

(pokud minimum existuje; v úlohách s konečně mnoha stavy, jako je naše bludiště, existuje vždy) a řešení π je optimální, právě když g(π) = C*. Optimální řešení je tedy řešení, které není dražší než žádné jiné řešení.

Osm kostiček a prázdné místo se dá do devíti políček rozmístit 9! = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362 880 způsoby. Tahem se ale dostanete jen do poloviny z nich: zapíšete-li kostičky po řádcích (bez prázdného místa), každý tah zachová, zda je v tom pořadí sudý, nebo lichý počet dvojic „větší před menší“. Posun vodorovně pořadí nezmění vůbec, posun svisle přeskočí kostičkou dvě jiné a počet takových dvojic změní o 0 nebo o ±2. Do stavu s opačnou paritou se proto dostat nedá. Že je dosažitelná právě polovina stavů (u hlavolamu 15 s trochu složitějším invariantem, do kterého vstupuje i řádek prázdného místa), dokázali W. W. Johnson a W. E. Story v roce 1879.

Hlavolam 8: 9!/2 = 362 880/2 = 181 440 stavů.
Hlavolam 15: 16!/2 = 20 922 789 888 000/2 = 10 461 394 944 000 ≈ 1,05 · 10¹³ stavů — přes deset bilionů.

Políčko zapíšeme jako dvojici (r, s) — řádek r ∈ {0, …, 8}, sloupec s ∈ {0, …, 13}. Označme Z množinu zdí a B množinu políček s bahnem.

• Stavy: S = ({0, …, 8} × {0, …, 13}) ∖ Z — všechna políčka kromě zdí.
• Počáteční stav: s₀ = (0, 0). Cíl: G = {(8, 13)}.
• Posuny: ↑ = (−1, 0), → = (0, 1), ↓ = (1, 0), ← = (0, −1). Akce použitelné ve stavu (r, s) ∈ S jsou ty, které vedou na políčko uvnitř mřížky, které není zeď: A((r, s)) = {(Δr, Δs) ∈ {↑, →, ↓, ←} : (r + Δr, s + Δs) ∈ S}.
• Přechod: T((r, s), (Δr, Δs)) = (r + Δr, s + Δs), např. T((r, s), →) = (r, s + 1).
• Cena: c(x, a) = 5, pokud T(x, a) ∈ B, jinak c(x, a) = 1 — platí se za políčko, na které vstupujeme.
• Úkol: najít řešení s nejmenší cenou C*.

Nechť P = (S, s₀, A, T, G, c) je úloha prohledávání. Pro stav s ∈ S označme množinu jeho následníků

N(s) = {T(s, a) : a ∈ A(s)}.

Algoritmus prohledávání si v každém okamžiku běhu udržuje dvě množiny stavů:

1. okraj (frontier) F ⊆ S — stavy, které algoritmus už objevil (vede do nich nalezená cesta z s₀), ale ještě nerozbalil; na začátku F = {s₀};
2. uzavřené stavy E ⊆ S — stavy, které už rozbalil; na začátku E = ∅.

Rozbalit stav s ∈ F znamená provést tyto dvě změny (v tomto pořadí):

E ← E ∪ {s},   F ← (F ∖ {s}) ∪ (N(s) ∖ E).

Rozbalený stav se tedy přesune z okraje mezi uzavřené a do okraje přibudou ti jeho následníci, kteří ještě nebyli rozbaleni.

Vstup: úloha prohledávání P = (S, s₀, A, T, G, c). Výstup: řešení (cesta z s₀ do některého stavu z G), nebo zpráva „řešení neexistuje“.

Prohledávání do šířky (BFS) je společná kostra výše, ve které je okraj F fronta (FIFO, first in — first out):

1. F ← (s₀), E ← ∅.
2. Je-li F prázdná, skonči: řešení neexistuje.
3. Odeber z F stav s, který do ní přibyl nejdřív.
4. Je-li s ∈ G, skonči a vrať cestu z s₀ do s.
5. Rozbal s: přidej ho do E a každého následníka s′ ∈ N(s), který není v E ani v F, zařaď na konec F. Pokračuj krokem 2.

Vlastnosti. Označme d(s) hloubku stavu s — nejmenší délku cesty z s₀ do s. BFS rozbaluje stavy v neklesajícím pořadí d(s), a proto vrátí řešení s nejmenším počtem akcí. Nechť b = max_{s ∈ S} |A(s)| je větvicí faktor (největší počet následníků stavu) a d hloubka nejmělčího řešení. Pak BFS vygeneruje nejvýš b + b² + … + b^d = O(b^d) stavů a stejně tolik jich drží v paměti.

Cesta BFS má 25 kroků, z toho 3 do bahna: g = 22 · 1 + 3 · 5 = 22 + 15 = 37.

Velikost vlny pro větvicí faktor b = 10: v hloubce d = 5 je to 10 + 100 + 1 000 + 10 000 + 100 000 = 111 110 stavů, v hloubce d = 10 už 11 111 111 110 ≈ 1,1 · 10¹⁰. Kdyby jeden stav zabral v paměti 1 kB, potřebovala by vlna v hloubce 10 přes 11 TB. Každé další patro to zdesetinásobí.

Vstup: úloha prohledávání P = (S, s₀, A, T, G, c). Výstup: řešení, nebo zpráva „řešení neexistuje“.

Prohledávání do hloubky (DFS) je společná kostra výše, ve které je okraj F zásobník (LIFO, last in — first out):

1. F ← (s₀), E ← ∅.
2. Je-li F prázdný, skonči: řešení neexistuje.
3. Odeber z F stav s, který do něj přibyl naposledy (vrchol zásobníku).
4. Je-li s ∈ G, skonči a vrať cestu z s₀ do s.
5. Rozbal s: přidej ho do E a každého následníka s′ ∈ N(s) ∖ E polož na vrchol F. Pokračuj krokem 2.

Vlastnosti. Nechť b je větvicí faktor a m největší hloubka stavového prostoru (největší délka cesty bez opakování stavů, případně ∞). Ve stromové variantě (bez množiny E, opakování stavů se hlídá jen na aktuální větvi) drží DFS v paměti jen aktuální větev a její sourozence: O(b · m) stavů. Čas je v nejhorším případě O(b^m). DFS není optimální a v nekonečném prostoru ani úplné — může sestupovat donekonečna.

Vstup: úloha prohledávání P = (S, s₀, A, T, G, c). Výstup: řešení s nejmenším počtem akcí (pokud nějaké řešení existuje).

Pro ℓ ∈ ℕ₀ označme DLS(ℓ) (depth-limited search) prohledávání do hloubky, které nerozbaluje stavy v hloubce ℓ a větší — cesty delší než ℓ tedy nezkoumá. Iterativní prohlubování (IDDFS):

1. ℓ ← 0.
2. Spusť DLS(ℓ).
3. Našlo-li DLS(ℓ) řešení, skonči a vrať ho.
4. ℓ ← ℓ + 1 a pokračuj krokem 2.

Podmínka zastavení: první ℓ, pro které DLS(ℓ) najde řešení; to je právě hloubka d nejmělčího řešení. (Neexistuje-li řešení a prostor je nekonečný, algoritmus neskončí.)

Vlastnosti. Nechť b je větvicí faktor a d hloubka nejmělčího řešení. Stavy v hloubce i ∈ {1, …, d} se vygenerují (d − i + 1)krát, celkem ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) stavů — stejně jako BFS, ale s pamětí jen O(b · d).

Vstup: úloha prohledávání P = (S, s₀, A, T, G, c). Výstup: řešení s nejmenší cenou, nebo zpráva „řešení neexistuje“.

Během běhu přiřazuje algoritmus každému objevenému stavu n ∈ S číslo g(n) — cenu nejlevnější dosud nalezené cesty z s₀ do n. Okraj F je prioritní fronta uspořádaná podle g. Prohledávání podle ceny (UCS, uniform-cost search):

1. F ← {s₀}, g(s₀) ← 0, E ← ∅.
2. Je-li F = ∅, skonči: řešení neexistuje.
3. Odeber z F stav n s nejmenším g(n).
4. Je-li n ∈ G, skonči a vrať nalezenou cestu do n (její cena je g(n)).
5. Přidej n do E. Pro každou akci a ∈ A(n) a n′ = T(n, a) ∉ E: je-li n′ ∉ F, nebo g(n) + c(n, a) < g(n′), nastav g(n′) ← g(n) + c(n, a), zapamatuj si n jako předchůdce n′ a vlož n′ do F. Pokračuj krokem 2.

Vlastnosti. Nechť existuje ε > 0 takové, že c(s, a) ≥ ε pro všechna s ∈ S, a ∈ A(s). Pak UCS rozbaluje stavy v neklesajícím pořadí g, a proto je úplné i optimální. Počet rozbalených stavů je O(b^{1 + ⌊C*/ε⌋}), kde b je větvicí faktor a ⌊x⌋ dolní celá část čísla x.

Prvních deset rozbalení s hodnotou g: (0, 0) g = 0; (0, 1) g = 1; (1, 0) g = 1; (0, 2) g = 2; (2, 0) g = 2; (0, 3) g = 3; (3, 0) g = 3; (1, 3) g = 4; (4, 0) g = 4; (2, 3) g = 5. Dokud nenarazí na bahno, rozbaluje UCS stejně jako BFS, protože každý krok stojí 1 a g je prostě hloubka. Bahno pak stav „odsune“ o 5 místo o 1 — do bahna se UCS podívá, až když vyčerpá všechno levnější.

Nalezená cesta: 25 kroků po suchu, C* = 25 · 1 = 25. Nejmenší cena akce je ε = 1 a větvicí faktor b = 4, horní odhad je tedy b^{1 + ⌊C*/ε⌋} = 4²⁶ ≈ 4,5 · 10¹⁵ stavů. Ve skutečnosti UCS rozbalil 49 políček: odhad počítá s nekonečným stromem, kde se nic neopakuje, kdežto bludiště má jen 83 průchozích políček a uzavřené stavy se znovu nerozbalují.

Nechť P = (S, s₀, A, T, G, c) je úloha prohledávání. Pro stav n ∈ S označme h*(n) ∈ ℝ_≥0 ∪ {∞} nejmenší cenu (přesněji infimum cen) cest ze stavu n do některého cílového stavu (cesta je definovaná stejně jako výše, jen začíná v n místo s₀; nevede-li z n do G žádná cesta, je h*(n) = ∞). Heuristika je funkce

h : S → ℝ_≥0  taková, že  ∀n ∈ G : h(n) = 0.

Hodnotu h(n) chápeme jako odhad h*(n). Heuristika h je

1. přípustná (admissible), právě když ∀n ∈ S : h(n) ≤ h*(n);
2. konzistentní (monotónní), právě když ∀n ∈ S ∀a ∈ A(n) : h(n) ≤ c(n, a) + h(T(n, a)).

Přípustná heuristika tedy skutečnou zbývající cenu nikdy nepřecení; konzistentní heuristika po žádném kroku neklesne o víc, než kolik ten krok stál. Každá konzistentní heuristika je přípustná (věta níže).

Nechť P = (S, s₀, A, T, G, c) je úloha prohledávání a h : S → ℝ_≥0 konzistentní heuristika. Pak h je přípustná, tj. h(n) ≤ h*(n) pro každé n ∈ S.

Důkaz. Nechť n ∈ S. Je-li h*(n) = ∞, nerovnost platí triviálně. Jinak vezměme libovolnou cestu z n do cíle: n = n₀, n₁, …, n_k ∈ G, kde n_i = T(n_i−1, a_i) a c_i = c(n_i−1, a_i) pro i = 1, …, k. Konzistenci použijeme kkrát za sebou:

h(n₀) ≤ c₁ + h(n₁) ≤ c₁ + c₂ + h(n₂) ≤ … ≤ c₁ + … + c_k + h(n_k).

V cíli je h(n_k) = 0, takže h(n) je nejvýš cena této cesty. To platí pro každou cestu z n do cíle, tedy i pro tu nejlevnější, jejíž cena je h*(n). Tedy h(n) ≤ h*(n). ∎

Opačně to neplatí: přípustná heuristika konzistentní být nemusí.

Vstup: úloha prohledávání P = (S, s₀, A, T, G, c) a heuristika h : S → ℝ_≥0. Výstup: řešení, nebo zpráva „řešení neexistuje“.

Hladové hledání (greedy best-first search) je společná kostra výše, ve které je okraj F prioritní fronta podle

f(n) = h(n):

1. F ← {s₀}, E ← ∅.
2. Je-li F = ∅, skonči: řešení neexistuje.
3. Odeber z F stav n s nejmenším h(n) — stav, který je podle odhadu nejblíž cíli.
4. Je-li n ∈ G, skonči a vrať cestu z s₀ do n.
5. Rozbal n: přidej ho do E a každého následníka n′ ∈ N(n), který není v E ani v F, vlož do F. Pokračuj krokem 2.

Dosavadní cena g(n) se nebere v úvahu. Vlastnosti: hladové hledání není optimální; s hlídáním opakovaných stavů (množinou E) je v konečném prostoru úplné.

Rozbalená políčka s hodnotou h: (0, 0) 21 → (0, 1) 20 → (0, 2) 19 → (0, 3) 18 → (1, 3) 17 → (2, 3) 16 → (2, 2) 17 → (3, 2) 16 → (4, 2) 15 → (4, 3) 14.

Hladové hledání jde rovnou doprava a dolů, dokud h klesá. V sedmém kroku h na chvíli vzroste (ze 16 na 17), protože z (2, 3) dál doprava ani dolů nevede cesta (zdi) a v okraji už žádné políčko s menším h není. O dva kroky později vstoupí do bahna na (4, 2), protože tudy h zase klesá. Cenu 5 za krok do bahna vůbec nevidí: priorita je jen h, žádné g.

Vstup: úloha prohledávání P = (S, s₀, A, T, G, c) a heuristika h : S → ℝ_≥0. Výstup: řešení, nebo zpráva „řešení neexistuje“.

A* je UCS (kroky 1–5 jeho definice výše, včetně udržování g), ve kterém je okraj F prioritní fronta podle

f(n) = g(n) + h(n)

místo podle g(n): v kroku 3 se z F odebírá stav s nejmenším f(n). Hodnota f(n) je odhad ceny celé cesty ze startu přes n do cíle. Algoritmus skončí, jakmile odebere z F cílový stav (nebo když je F prázdná).

Věta. Nechť h je konzistentní heuristika a ceny akcí jsou ≥ ε pro nějaké ε > 0. Pak hodnoty f podél každé cesty neklesají, A* rozbaluje stavy v neklesajícím pořadí f a první rozbalený cílový stav leží na optimální cestě s cenou C*. Rozbalí přitom každý stav s f(n) < C* a žádný s f(n) > C*.

Pro h ≡ 0 je A* totéž co UCS; bez g by to bylo hladové hledání.

Nechť h je konzistentní heuristika, f = g + h, n ∈ S, a ∈ A(n), n′ = T(n, a) a cesta do n′ vede přes n, takže g(n′) = g(n) + c(n, a). Pak f(n′) ≥ f(n).

Důkaz. f(n′) =g(n) + c(n, a) + h(n′) ≥ g(n) + h(n) = f(n),

kde nerovnost je přesně konzistence h(n) ≤ c(n, a) + h(n′). ∎

Z toho (zde jen náčrtem) plyne, že A* rozbaluje stavy v neklesajícím pořadí f: kdyby později rozbalil stav s menším f, musel by na něj vést okraj se stavem s ještě menším f, který měl přijít na řadu dřív. Když se tedy poprvé rozbalí cíl (kde h = 0 a f = g), žádná levnější cesta už nezbývá.

Nechť 𝒜 je algoritmus, který na vstupu dostane úlohu prohledávání P a vrátí řešení, nebo zprávu „řešení neexistuje“. Algoritmus 𝒜 je

1. úplný, právě když pro každou úlohu P, která má aspoň jedno řešení (Π ≠ ∅), 𝒜 po konečném počtu kroků skončí a vrátí řešení π ∈ Π;
2. optimální, právě když pro každou úlohu P s Π ≠ ∅ vrátí řešení π s cenou g(π) = C*.

Parametry, na kterých závisí čas a paměť (pro úlohu P = (S, s₀, A, T, G, c)):

1. b = max_{s ∈ S} |A(s)| — větvicí faktor;
2. d — hloubka nejmělčího řešení (nejmenší délka cesty z s₀ do G);
3. m — největší hloubka prostoru (největší délka cesty z s₀ bez opakování stavů, případně ∞);
4. C* — optimální cena a ε > 0 — dolní mez cen akcí.

Pro funkce u, v ≥ 0 těchto parametrů píšeme u = O(v), právě když existují konstanty K > 0 a x₀ tak, že u(x) ≤ K · v(x) pro všechna x ≥ x₀. O(·) tedy udává, jak čas (počet vygenerovaných stavů) nebo paměť (počet stavů držených najednou) nejvýš rostou s těmito parametry, až na konstantní násobek.

Nechť S je neprázdná množina stavů, f : S → ℝ funkce (účelová funkce) a N : S → 2^S zobrazení, které každému stavu s ∈ S přiřadí konečnou neprázdnou množinu N(s) ⊆ S ∖ {s} (okolí stavu s, jeho prvky jsou sousedé). Úloha lokálního hledání je najít stav

s* ∈ argmax_{s ∈ S} f(s) = {s ∈ S : ∀s′ ∈ S : f(s) ≥ f(s′)},

případně aspoň stav s co největší hodnotou f. Stav s ∈ S je

1. lokální maximum, právě když ∀s′ ∈ N(s) : f(s) ≥ f(s′);
2. globální maximum, právě když ∀s′ ∈ S : f(s) ≥ f(s′).

Každé globální maximum je i lokální, opačně to neplatí.

Horolezecký algoritmus (hill climbing). Vstup: S, f, N jako výše a počáteční stav s ∈ S. Výstup: lokální maximum.

1. Vyber s′ ∈ argmax_{t ∈ N(s)} f(t) (nejlepšího souseda).
2. Je-li f(s′) ≤ f(s), skonči a vrať s — je to lokální maximum.
3. Jinak s ← s′ a pokračuj krokem 1.

Stav je číslo s ∈ ⟨0, 1⟩, okolí jsou dva body o 0,02 vlevo a vpravo: N(s) = {s − 0,02, s + 0,02}. Krajina má dva vrcholy (lokální u s = 0,25, globální u 0,72) a horolezec vychází z s = 0,05.

V každém řádku je pravý soused nejvyšší, a tak se jde doprava. V posledním řádku jsou oba sousedé (0,582) nižší než f(0,25) = 0,600 a algoritmus skončí — na lokálním maximu, přestože globální maximum má f(0,72) = 0,950.

Vstup: S, f, N jako u lokálního hledání, počáteční stav s ∈ S, počáteční teplota T₀ > 0, koeficient ochlazování q ∈ (0, 1) a minimální teplota T_min ∈ (0, T₀). Výstup: stav s ∈ S.

1. T ← T₀.
2. Je-li T ≤ T_min, skonči a vrať s.
3. Vyber náhodně (rovnoměrně) souseda s′ ∈ N(s) a spočítej Δ = f(s′) − f(s).
4. Je-li Δ > 0, polož s ← s′. Je-li Δ ≤ 0, polož s ← s′ s pravděpodobností exp(Δ/T), jinak s ponech.
5. T ← q · T a pokračuj krokem 2.

„Teplota“ T tedy postupně klesá k nule a s ní i ochota přijmout horšího souseda. (Ochlazování T ← q · T je nejběžnější volba, používají se i jiné rozvrhy.)