Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami

Úloha prehľadávania je šestica

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

ktorá spĺňa:

1. S je neprázdna množina; jej prvky nazývame stavy;
2. s₀ ∈ S; tento stav nazývame počiatočný stav;
3. A priraďuje každému stavu s ∈ S konečnú množinu A(s) akcií použiteľných v stave s; označme 𝒟 = {(s, a) : s ∈ S, a ∈ A(s)} množinu všetkých dvojíc „stav, v ňom použiteľná akcia“;
4. T : 𝒟 → S je prechodová funkcia; pre (s, a) ∈ 𝒟 je stav s′ = T(s, a) nasledovník stavu s (po akcii a);
5. G ⊆ S je množina cieľových stavov;
6. c : 𝒟 → ℝ⁺ = (0, ∞) je cena akcie: c(s, a) > 0 je cena použitia akcie a v stave s.

Úloha teda presne hovorí, odkiaľ začíname, aké ťahy máme v každom stave k dispozícii, kam ktorý ťah vedie, koľko stojí a kedy sme v cieli.

Nech P = (S, s₀, A, T, G, c) je úloha prehľadávania a k ∈ ℕ₀. Cesta dĺžky k z počiatočného stavu je postupnosť

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

taká, že pre každé i = 1, …, k platí a_i ∈ A(s_i−1) a s_i = T(s_i−1, a_i). (Pre k = 0 je cesta len (s₀).)

Cena cesty π je súčet cien jej akcií:

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

Cesta π je riešenie práve vtedy, keď s_k ∈ G. Označme Π množinu všetkých riešení. Ak je Π ≠ ∅, je optimálna cena

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

(ak minimum existuje; v úlohách s konečne veľa stavmi, ako je naše bludisko, existuje vždy) a riešenie π je optimálne práve vtedy, keď g(π) = C*. Optimálne riešenie je teda riešenie, ktoré nie je drahšie než žiadne iné riešenie.

Osem kociek a prázdne miesto sa dá do deviatich políčok rozmiestniť 9! = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362 880 spôsobmi. Ťahom sa ale dostanete len do polovice z nich: ak zapíšete kocky po riadkoch (bez prázdneho miesta), každý ťah zachová, či je v tom poradí párny, alebo nepárny počet dvojíc „väčšia pred menšou“. Posun vodorovne poradie nezmení vôbec, posun zvisle preskočí kockou dve iné a počet takých dvojíc zmení o 0 alebo o ±2. Do stavu s opačnou paritou sa preto dostať nedá. Že je dosiahnuteľná práve polovica stavov (pri hlavolame 15 s trochu zložitejším invariantom, do ktorého vstupuje aj riadok prázdneho miesta), dokázali W. W. Johnson a W. E. Story v roku 1879.

Hlavolam 8: 9!/2 = 362 880/2 = 181 440 stavov.
Hlavolam 15: 16!/2 = 20 922 789 888 000/2 = 10 461 394 944 000 ≈ 1,05 · 10¹³ stavov — vyše desať biliónov.

Políčko zapíšeme ako dvojicu (r, s) — riadok r ∈ {0, …, 8}, stĺpec s ∈ {0, …, 13}. Označme Z množinu stien (zdí) a B množinu políčok s blatom.

• Stavy: S = ({0, …, 8} × {0, …, 13}) ∖ Z — všetky políčka okrem stien.
• Počiatočný stav: s₀ = (0, 0). Cieľ: G = {(8, 13)}.
• Posuny: ↑ = (−1, 0), → = (0, 1), ↓ = (1, 0), ← = (0, −1). Akcie použiteľné v stave (r, s) ∈ S sú tie, ktoré vedú na políčko vnútri mriežky, ktoré nie je stena: A((r, s)) = {(Δr, Δs) ∈ {↑, →, ↓, ←} : (r + Δr, s + Δs) ∈ S}.
• Prechod: T((r, s), (Δr, Δs)) = (r + Δr, s + Δs), napr. T((r, s), →) = (r, s + 1).
• Cena: c(x, a) = 5, ak T(x, a) ∈ B, inak c(x, a) = 1 — platí sa za políčko, na ktoré vstupujeme.
• Úloha: nájsť riešenie s najmenšou cenou C*.

Nech P = (S, s₀, A, T, G, c) je úloha prehľadávania. Pre stav s ∈ S označme množinu jeho nasledovníkov

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

Algoritmus prehľadávania si v každom okamihu behu udržiava dve množiny stavov:

1. okraj (frontier) F ⊆ S — stavy, ktoré algoritmus už objavil (vedie do nich nájdená cesta z s₀), ale ešte nerozbalil; na začiatku F = {s₀};
2. uzavreté stavy E ⊆ S — stavy, ktoré už rozbalil; na začiatku E = ∅.

Rozbaliť stav s ∈ F znamená vykonať tieto dve zmeny (v tomto poradí):

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

Rozbalený stav sa teda presunie z okraja medzi uzavreté a do okraja pribudnú tí jeho nasledovníci, ktorí ešte neboli rozbalení.

Vstup: úloha prehľadávania P = (S, s₀, A, T, G, c). Výstup: riešenie (cesta z s₀ do niektorého stavu z G), alebo správa „riešenie neexistuje“.

Prehľadávanie do šírky (BFS) je spoločná kostra vyššie, v ktorej je okraj F front (FIFO, first in — first out):

1. F ← (s₀), E ← ∅.
2. Ak je F prázdny, skonči: riešenie neexistuje.
3. Odober z F stav s, ktorý doň pribudol najskôr.
4. Ak je s ∈ G, skonči a vráť cestu z s₀ do s.
5. Rozbaľ s: pridaj ho do E a každého nasledovníka s′ ∈ N(s), ktorý nie je v E ani v F, zaraď na koniec F. Pokračuj krokom 2.

Vlastnosti. Označme d(s) hĺbku stavu s — najmenšiu dĺžku cesty z s₀ do s. BFS rozbaľuje stavy v neklesajúcom poradí d(s), a preto vráti riešenie s najmenším počtom akcií. Nech b = max_{s ∈ S} |A(s)| je vetviaci faktor (najväčší počet nasledovníkov stavu) a d hĺbka najplytšieho riešenia. Potom BFS vygeneruje najviac b + b² + … + b^d = O(b^d) stavov a rovnako veľa ich drží v pamäti.

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

Veľkosť vlny pre vetviaci faktor b = 10: v hĺbke d = 5 je to 10 + 100 + 1 000 + 10 000 + 100 000 = 111 110 stavov, v hĺbke d = 10 už 11 111 111 110 ≈ 1,1 · 10¹⁰. Keby jeden stav zabral v pamäti 1 kB, potrebovala by vlna v hĺbke 10 vyše 11 TB. Každé ďalšie poschodie to zdesaťnásobí.

Vstup: úloha prehľadávania P = (S, s₀, A, T, G, c). Výstup: riešenie, alebo správa „riešenie neexistuje“.

Prehľadávanie do hĺbky (DFS) je spoločná kostra vyššie, v ktorej je okraj F zásobník (LIFO, last in — first out):

1. F ← (s₀), E ← ∅.
2. Ak je F prázdny, skonči: riešenie neexistuje.
3. Odober z F stav s, ktorý doň pribudol naposledy (vrchol zásobníka).
4. Ak je s ∈ G, skonči a vráť cestu z s₀ do s.
5. Rozbaľ s: pridaj ho do E a každého nasledovníka s′ ∈ N(s) ∖ E polož na vrchol F. Pokračuj krokom 2.

Vlastnosti. Nech b je vetviaci faktor a m najväčšia hĺbka stavového priestoru (najväčšia dĺžka cesty bez opakovania stavov, prípadne ∞). V stromovej variante (bez množiny E, opakovanie stavov sa stráži len na aktuálnej vetve) drží DFS v pamäti len aktuálnu vetvu a jej súrodencov: O(b · m) stavov. Čas je v najhoršom prípade O(b^m). DFS nie je optimálny a v nekonečnom priestore ani úplný — môže zostupovať donekonečna.

Vstup: úloha prehľadávania P = (S, s₀, A, T, G, c). Výstup: riešenie s najmenším počtom akcií (ak nejaké riešenie existuje).

Pre ℓ ∈ ℕ₀ označme DLS(ℓ) (depth-limited search) prehľadávanie do hĺbky, ktoré nerozbaľuje stavy v hĺbke ℓ a väčšej — cesty dlhšie než ℓ teda neskúma. Iteratívne prehlbovanie (IDDFS):

1. ℓ ← 0.
2. Spusti DLS(ℓ).
3. Ak DLS(ℓ) našlo riešenie, skonči a vráť ho.
4. ℓ ← ℓ + 1 a pokračuj krokom 2.

Podmienka zastavenia: prvé ℓ, pre ktoré DLS(ℓ) nájde riešenie; to je práve hĺbka d najplytšieho riešenia. (Ak riešenie neexistuje a priestor je nekonečný, algoritmus neskončí.)

Vlastnosti. Nech b je vetviaci faktor a d hĺbka najplytšieho riešenia. Stavy v hĺbke i ∈ {1, …, d} sa vygenerujú (d − i + 1)-krát, celkovo ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) stavov — rovnako ako BFS, ale s pamäťou len O(b · d).

Vstup: úloha prehľadávania P = (S, s₀, A, T, G, c). Výstup: riešenie s najmenšou cenou, alebo správa „riešenie neexistuje“.

Počas behu priraďuje algoritmus každému objavenému stavu n ∈ S číslo g(n) — cenu najlacnejšej doteraz nájdenej cesty z s₀ do n. Okraj F je prioritný front usporiadaný podľa g. Prehľadávanie podľa ceny (UCS, uniform-cost search):

1. F ← {s₀}, g(s₀) ← 0, E ← ∅.
2. Ak je F = ∅, skonči: riešenie neexistuje.
3. Odober z F stav n s najmenším g(n).
4. Ak je n ∈ G, skonči a vráť nájdenú cestu do n (jej cena je g(n)).
5. Pridaj n do E. Pre každú akciu a ∈ A(n) a n′ = T(n, a) ∉ E: ak je n′ ∉ F, alebo g(n) + c(n, a) < g(n′), nastav g(n′) ← g(n) + c(n, a), zapamätaj si n ako predchodcu n′ a vlož n′ do F. Pokračuj krokom 2.

Vlastnosti. Nech existuje ε > 0 také, že c(s, a) ≥ ε pre všetky s ∈ S, a ∈ A(s). Potom UCS rozbaľuje stavy v neklesajúcom poradí g, a preto je úplný aj optimálny. Počet rozbalených stavov je O(b^{1 + ⌊C*/ε⌋}), kde b je vetviaci faktor a ⌊x⌋ dolná celá časť čísla x.

Prvých desať 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. Kým nenarazí na blato, rozbaľuje UCS rovnako ako BFS, pretože každý krok stojí 1 a g je jednoducho hĺbka. Blato potom stav „odsunie“ o 5 namiesto o 1 — do blata sa UCS pozrie, až keď vyčerpá všetko lacnejšie.

Nájdená cesta: 25 krokov po suchu, C* = 25 · 1 = 25. Najmenšia cena akcie je ε = 1 a vetviaci faktor b = 4, horný odhad je teda b^{1 + ⌊C*/ε⌋} = 4²⁶ ≈ 4,5 · 10¹⁵ stavov. V skutočnosti UCS rozbalil 49 políčok: odhad počíta s nekonečným stromom, kde sa nič neopakuje, kým bludisko má len 83 priechodných políčok a uzavreté stavy sa znova nerozbaľujú.

Nech P = (S, s₀, A, T, G, c) je úloha prehľadávania. Pre stav n ∈ S označme h*(n) ∈ ℝ_≥0 ∪ {∞} najmenšiu cenu (presnejšie infimum cien) ciest zo stavu n do niektorého cieľového stavu (cesta je definovaná rovnako ako vyššie, len začína v n namiesto s₀; ak z n do G nevedie žiadna cesta, je h*(n) = ∞). Heuristika je funkcia

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

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

1. prípustná (admissible) práve vtedy, keď ∀n ∈ S : h(n) ≤ h*(n);
2. konzistentná (monotónna) práve vtedy, keď ∀n ∈ S ∀a ∈ A(n) : h(n) ≤ c(n, a) + h(T(n, a)).

Prípustná heuristika teda skutočnú zostávajúcu cenu nikdy nepreceňuje; konzistentná heuristika po žiadnom kroku neklesne o viac, než koľko ten krok stál. Každá konzistentná heuristika je prípustná (veta nižšie).

Nech P = (S, s₀, A, T, G, c) je úloha prehľadávania a h : S → ℝ_≥0 konzistentná heuristika. Potom h je prípustná, t. j. h(n) ≤ h*(n) pre každé n ∈ S.

Dôkaz. Nech n ∈ S. Ak je h*(n) = ∞, nerovnosť platí triviálne. Inak vezmime ľubovoľnú cestu z n do cieľa: n = n₀, n₁, …, n_k ∈ G, kde n_i = T(n_i−1, a_i) a c_i = c(n_i−1, a_i) pre i = 1, …, k. Konzistenciu použijeme k-krát za sebou:

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

V cieli je h(n_k) = 0, takže h(n) je najviac cena tejto cesty. To platí pre každú cestu z n do cieľa, teda aj pre tú najlacnejšiu, ktorej cena je h*(n). Teda h(n) ≤ h*(n). ∎

Opačne to neplatí: prípustná heuristika konzistentná byť nemusí.

Vstup: úloha prehľadávania P = (S, s₀, A, T, G, c) a heuristika h : S → ℝ_≥0. Výstup: riešenie, alebo správa „riešenie neexistuje“.

Pažravé hľadanie (greedy best-first search) je spoločná kostra vyššie, v ktorej je okraj F prioritný front podľa

f(n) = h(n):

1. F ← {s₀}, E ← ∅.
2. Ak je F = ∅, skonči: riešenie neexistuje.
3. Odober z F stav n s najmenším h(n) — stav, ktorý je podľa odhadu najbližšie k cieľu.
4. Ak je n ∈ G, skonči a vráť cestu z s₀ do n.
5. Rozbaľ n: pridaj ho do E a každého nasledovníka n′ ∈ N(n), ktorý nie je v E ani v F, vlož do F. Pokračuj krokom 2.

Doterajšia cena g(n) sa neberie do úvahy. Vlastnosti: pažravé hľadanie nie je optimálne; so strážením opakovaných stavov (množinou E) je v konečnom priestore ú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.

Pažravé hľadanie ide rovno doprava a dole, kým h klesá. V siedmom kroku h na chvíľu stúpne (zo 16 na 17), pretože z (2, 3) ďalej doprava ani dole nevedie cesta (steny) a v okraji už nie je žiadne políčko s menším h. O dva kroky neskôr vstúpi do blata na (4, 2), pretože tadiaľ h znova klesá. Cenu 5 za krok do blata vôbec nevidí: priorita je len h, žiadne g.

Vstup: úloha prehľadávania P = (S, s₀, A, T, G, c) a heuristika h : S → ℝ_≥0. Výstup: riešenie, alebo správa „riešenie neexistuje“.

A* je UCS (kroky 1–5 jeho definície vyššie, vrátane udržiavania g), v ktorom je okraj F prioritný front podľa

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

namiesto podľa g(n): v kroku 3 sa z F odoberá stav s najmenším f(n). Hodnota f(n) je odhad ceny celej cesty zo štartu cez n do cieľa. Algoritmus skončí, len čo odoberie z F cieľový stav (alebo keď je F prázdny).

Veta. Nech h je konzistentná heuristika a ceny akcií sú ≥ ε pre nejaké ε > 0. Potom hodnoty f pozdĺž každej cesty neklesajú, A* rozbaľuje stavy v neklesajúcom poradí f a prvý rozbalený cieľový stav leží na optimálnej ceste s cenou C*. Rozbalí pritom každý stav s f(n) < C* a žiadny s f(n) > C*.

Pre h ≡ 0 je A* to isté čo UCS; bez g by to bolo pažravé hľadanie.

Nech h je konzistentná heuristika, f = g + h, n ∈ S, a ∈ A(n), n′ = T(n, a) a cesta do n′ vedie cez n, takže g(n′) = g(n) + c(n, a). Potom f(n′) ≥ f(n).

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

kde nerovnosť je presne konzistencia h(n) ≤ c(n, a) + h(n′). ∎

Z toho (tu len náčrtom) vyplýva, že A* rozbaľuje stavy v neklesajúcom poradí f: keby neskôr rozbalil stav s menším f, musel by naň viesť okraj so stavom s ešte menším f, ktorý mal prísť na rad skôr. Keď sa teda prvýkrát rozbalí cieľ (kde h = 0 a f = g), žiadna lacnejšia cesta už nezostáva.

Nech 𝒜 je algoritmus, ktorý na vstupe dostane úlohu prehľadávania P a vráti riešenie, alebo správu „riešenie neexistuje“. Algoritmus 𝒜 je

1. úplný práve vtedy, keď pre každú úlohu P, ktorá má aspoň jedno riešenie (Π ≠ ∅), 𝒜 po konečnom počte krokov skončí a vráti riešenie π ∈ Π;
2. optimálny práve vtedy, keď pre každú úlohu P s Π ≠ ∅ vráti riešenie π s cenou g(π) = C*.

Parametre, od ktorých závisí čas a pamäť (pre úlohu P = (S, s₀, A, T, G, c)):

1. b = max_{s ∈ S} |A(s)| — vetviaci faktor;
2. d — hĺbka najplytšieho riešenia (najmenšia dĺžka cesty z s₀ do G);
3. m — najväčšia hĺbka priestoru (najväčšia dĺžka cesty z s₀ bez opakovania stavov, prípadne ∞);
4. C* — optimálna cena a ε > 0 — dolná hranica cien akcií.

Pre funkcie u, v ≥ 0 týchto parametrov píšeme u = O(v) práve vtedy, keď existujú konštanty K > 0 a x₀ také, že u(x) ≤ K · v(x) pre všetky x ≥ x₀. O(·) teda udáva, ako čas (počet vygenerovaných stavov) alebo pamäť (počet stavov držaných naraz) najviac rastú s týmito parametrami, až na konštantný násobok.

Nech S je neprázdna množina stavov, f : S → ℝ funkcia (účelová funkcia) a N : S → 2^S zobrazenie, ktoré každému stavu s ∈ S priradí konečnú neprázdnu množinu N(s) ⊆ S ∖ {s} (okolie stavu s, jeho prvky sú susedia). Úloha lokálneho hľadania je nájsť stav

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

prípadne aspoň stav s čo najväčšou hodnotou f. Stav s ∈ S je

1. lokálne maximum práve vtedy, keď ∀s′ ∈ N(s) : f(s) ≥ f(s′);
2. globálne maximum práve vtedy, keď ∀s′ ∈ S : f(s) ≥ f(s′).

Každé globálne maximum je aj lokálne, opačne to neplatí.

Horolezecký algoritmus (hill climbing). Vstup: S, f, N ako vyššie a počiatočný stav s ∈ S. Výstup: lokálne maximum.

1. Vyber s′ ∈ argmax_{t ∈ N(s)} f(t) (najlepšieho suseda).
2. Ak je f(s′) ≤ f(s), skonči a vráť s — je to lokálne maximum.
3. Inak s ← s′ a pokračuj krokom 1.

Stav je číslo s ∈ ⟨0, 1⟩, okolie sú dva body o 0,02 vľavo a vpravo: N(s) = {s − 0,02, s + 0,02}. Krajina má dva vrcholy (lokálny pri s = 0,25, globálny pri 0,72) a horolezec vychádza z s = 0,05.

V každom riadku je pravý sused najvyšší, a tak sa ide doprava. V poslednom riadku sú obaja susedia (0,582) nižšie než f(0,25) = 0,600 a algoritmus skončí — na lokálnom maxime, hoci globálne maximum má f(0,72) = 0,950.

Vstup: S, f, N ako pri lokálnom hľadaní, počiatočný stav s ∈ S, počiatočná teplota T₀ > 0, koeficient ochladzovania q ∈ (0, 1) a minimálna teplota T_min ∈ (0, T₀). Výstup: stav s ∈ S.

1. T ← T₀.
2. Ak je T ≤ T_min, skonči a vráť s.
3. Vyber náhodne (rovnomerne) suseda s′ ∈ N(s) a vypočítaj Δ = f(s′) − f(s).
4. Ak je Δ > 0, polož s ← s′. Ak je Δ ≤ 0, polož s ← s′ s pravdepodobnosťou exp(Δ/T), inak s ponechaj.
5. T ← q · T a pokračuj krokom 2.

„Teplota“ T teda postupne klesá k nule a s ňou aj ochota prijať horšieho suseda. (Ochladzovanie T ← q · T je najbežnejšia voľba, používajú sa aj iné rozvrhy.)