Iterativní prohlubování A * - Iterative deepening A*

Iterativní prohlubování A *
Třída	Vyhledávací algoritmus
Datová struktura	Strom, Graf
Nejhorší případ složitost prostoru

Iterativní prohlubování A * (IDA *) je přechod grafu a hledání cesty algoritmus, který dokáže najít nejkratší cesta mezi určeným počátečním uzlem a jakýmkoli členem sady uzlů cíle ve váženém grafu. Je to varianta iterativní prohlubování hloubkového vyhledávání , který si vypůjčuje myšlenku použít heuristickou funkci k vyhodnocení zbývajících nákladů na dosažení cíle z * Vyhledávací algoritmus. Jelikož se jedná o algoritmus pro vyhledávání do hloubky, jeho využití paměti je nižší než v A *, ale na rozdíl od běžného iterativního prohlubujícího se vyhledávání se soustředí na prozkoumání nejslibnějších uzlů a tudíž nechodí do stejné hloubky všude ve stromu vyhledávání. Na rozdíl od A * IDA * nevyužívá dynamické programování a proto často skončí zkoumáním stejných uzlů mnohokrát.

Zatímco standardní iterativní prohlubování hloubka-první vyhledávání používá hloubku vyhledávání jako mezní pro každou iteraci, IDA * používá více informativní ${ displaystyle f (n) = g (n) + h (n)}$ , kde ${ displaystyle g (n)}$ jsou náklady na cestu z kořene do uzlu ${ displaystyle n}$ a ${ displaystyle h (n)}$ je heuristický odhad nákladů na cestu, který závisí na konkrétním problému ${ displaystyle n}$ do cíle.

Algoritmus poprvé popsal Richard Korf v roce 1985.^[1]

Popis

Iterativní-prohlubování-A * funguje následovně: při každé iteraci proveďte hloubkové prohledávání, odřízněte větev, když její celková cena ${ displaystyle f (n) = g (n) + h (n)}$ překračuje danou hodnotu práh. Tato prahová hodnota začíná odhadem nákladů v počátečním stavu a zvyšuje se pro každou iteraci algoritmu. Při každé iteraci je prahovou hodnotou použitou pro další iteraci minimální cena všech hodnot, které překročily aktuální prahovou hodnotu.^[2]

Stejně jako v A * musí mít heuristika určité vlastnosti, aby byla zaručena optimálnost (nejkratší cesty). Vidět Vlastnosti níže.

Pseudo kód

cesta              aktuální vyhledávací cesta (funguje jako zásobník)uzel              aktuální uzel (poslední uzel v aktuální cestě)G                 náklady na dosažení aktuálního uzluF                 odhadované náklady na nejlevnější cestu (root..node..goal)h(uzel)           odhadované náklady na nejlevnější cestu (uzel ... cíl)náklady(uzel, succ)  funkce krokových nákladůis_goal(uzel)     test cílenástupci(uzel)  funkce rozšíření uzlu, rozbalení uzlů seřazených podle g + h (uzel)ida_star(vykořenit)    vrátit buď NOT_FOUND nebo pár s nejlepší cestou a její cenou postup ida_star(vykořenit)    vázaný := h(vykořenit)    cesta := [vykořenit]    smyčka        t := Vyhledávání(cesta, 0, vázaný)        -li t = NALEZENO pak se vraťte (cesta, svázaná)        -li t = ∞ pak se vraťte NENALEZENO vázaný := t    koncová smyčkaukončete postupfunkce Vyhledávání(cesta, G, vázaný)    uzel := cesta.poslední F := G + h(uzel)    -li F > vázaný pak se vraťte F    -li is_goal(uzel) pak se vraťte NALEZENO min := ∞    pro succ v nástupci(uzel) dělat        -li succ ne v cesta pak            cesta.tlačit(succ)            t := Vyhledávání(cesta, G + náklady(uzel, succ), vázaný)            -li t = NALEZENO pak se vraťte NALEZENO -li t < min pak min := t            cesta.pop () konec -li    konec pro    vrátit se minkoncová funkce

Vlastnosti

Stejně jako A * je IDA * zaručeno, že najde nejkratší cestu vedoucí z daného počátečního uzlu k libovolnému cílovému uzlu v grafu problému, pokud heuristická funkce $h$ je přípustný,^[2] to je

{ displaystyle h (n) leq h ^ {*} (n)}

pro všechny uzly $n$ , kde $h *$ je skutečná cena nejkratší cesty od $n$ k nejbližšímu cíli („dokonalá heuristika“).^[3]

IDA * je výhodné, když je problém omezen pamětí. Hledání * udržuje velkou frontu neprozkoumaných uzlů, které mohou rychle zaplnit paměť. Naproti tomu IDA * si nepamatuje žádný uzel kromě těch v aktuálním cesta, to vyžaduje množství paměti to je pouze lineární v délce řešení, které vytváří. Jeho časovou složitost analyzuje Korf et al. za předpokladu, že heuristický odhad nákladů $h$ je konzistentní, znamenající, že

{ Displaystyle h (n) leq mathrm {cost} (n, n ') + h (n')}

pro všechny uzly $n$ a všichni sousedé $n '$ z $n$ ; docházejí k závěru, že ve srovnání s vyhledáváním stromu hrubou silou nad problémem s exponenciální velikostí dosahuje IDA * menší hloubku vyhledávání (o konstantní faktor), ale ne menší větvící faktor.^[4]

Rekurzivní vyhledávání typu „první“ je další paměťově omezená verze vyhledávání A *, která může být v praxi rychlejší než IDA *, protože vyžaduje méně regenerace uzlů.^[3]^:282–289

Aplikace

Aplikace IDA * se nacházejí v problémech jako plánování.^[5]

Reference

^ Korf, Richard E. (1985). „Hloubka první iterativní prohlubování: optimální přípustné hledání stromu“ (PDF). Umělá inteligence. 27: 97–109. doi:10.1016/0004-3702(85)90084-0.
^ ^A ^b Korf, Richard E. (1985). „Hloubka první iterativní prohlubování“ (PDF): 7. Citovat deník vyžaduje | deník = (Pomoc)
^ ^A ^b Bratko, Ivan (2001). Programování Prolog pro umělou inteligenci. Pearson Education.
^ Korf, Richard E .; Reid, Michael; Edelkamp, Stefan (2001). „Časová složitost iterativního prohlubování-A“. Umělá inteligence. 129 (1–2): 199–218. doi:10.1016 / S0004-3702 (01) 00094-7.
^ Bonet, Blai; Geffner, Héctor C. (2001). "Plánování jako heuristické vyhledávání". Umělá inteligence. 129 (1–2): 5–33. doi:10.1016 / S0004-3702 (01) 00108-4. hdl:10230/36325.

[1] Korf, Richard E. (1985). „Hloubka první iterativní prohlubování: optimální přípustné hledání stromu“ (PDF). Umělá inteligence. 27: 97–109. doi:10.1016/0004-3702(85)90084-0.

[re1985_7-2] A ^b Korf, Richard E. (1985). „Hloubka první iterativní prohlubování“ (PDF): 7. Citovat deník vyžaduje | deník = (Pomoc)

[ppai-3] A ^b Bratko, Ivan (2001). Programování Prolog pro umělou inteligenci. Pearson Education.

[4] Korf, Richard E .; Reid, Michael; Edelkamp, Stefan (2001). „Časová složitost iterativního prohlubování-A“. Umělá inteligence. 129 (1–2): 199–218. doi:10.1016 / S0004-3702 (01) 00094-7.

[5] Bonet, Blai; Geffner, Héctor C. (2001). "Plánování jako heuristické vyhledávání". Umělá inteligence. 129 (1–2): 5–33. doi:10.1016 / S0004-3702 (01) 00108-4. hdl:10230/36325.

[1]

[2]

[3]

[4]

[5]