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

Iterativní prohlubování A *

Třída	Vyhledávací algoritmus
Datová struktura	Strom , graf
Nejhorší prostorová složitost	${\ displaystyle O (d)}$

Algoritmy pro vyhledávání grafů a stromů
α – β A* B * Backtracking Paprsek Bellman – Ford Nejlepší první Obousměrný Borůvka Pobočka a vázaná BFS britské muzeum D * DFS Dijkstra Edmonds Floyd – Warshall Fringe vyhledávání horolezectví IDA * Iterativní prohlubování Johnson Skokový bod Kruskal Lexikografický BFS LPA * Prim SMA *
Výpisy
Algoritmy grafů Vyhledávací algoritmy Seznam grafových algoritmů
související témata
Dynamické programování Traverz grafu Traverz stromů Hledat hry Barvení grafu
proti t E

Iterativní prohlubování A * ( IDA * ) je algoritmus pro procházení grafu a hledání cesty , který může najít nejkratší cestu mezi určeným počátečním uzlem a jakýmkoli členem sady uzlů cíle ve váženém grafu. Jedná se o variantu iterativního prohlubování hloubkového hledání, která si vypůjčuje myšlenku použít heuristickou funkci k vyhodnocení zbývající ceny, aby se z vyhledávacího algoritmu A * dostal k cíli . 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 končí 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í , kde jsou náklady na cestu od kořene k uzlu a je heuristický odhad nákladů na konkrétní problém cestovat z do cíle. ${\ displaystyle f (n) = g (n) + h (n)}$${\ displaystyle g (n)}$${\ displaystyle n}$${\ displaystyle h (n)}$${\ displaystyle n}$

Algoritmus poprvé popsal Richard Korf v roce 1985.

Popis

Iterative-deepening-A * funguje následovně: při každé iteraci proveďte hloubkové prohledávání, odřízněte větev, když její celková cena překročí danou hranici . 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. ${\ displaystyle f (n) = g (n) + h (n)}$

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

Pseudo kód

path              current search path (acts like a stack)
node              current node (last node in current path)
g                 the cost to reach current node
f                 estimated cost of the cheapest path (root..node..goal)
h(node)           estimated cost of the cheapest path (node..goal)
cost(node, succ)  step cost function
is_goal(node)     goal test
successors(node)  node expanding function, expand nodes ordered by g + h(node)
ida_star(root)    return either NOT_FOUND or a pair with the best path and its cost
 
procedure ida_star(root)
    bound := h(root)
    path := [root]
    loop
        t := search(path, 0, bound)
        if t = FOUND then return (path, bound)
        if t = ∞ then return NOT_FOUND
        bound := t
    end loop
end procedure

function search(path, g, bound)
    node := path.last
    f := g + h(node)
    if f > bound then return f
    if is_goal(node) then return FOUND
    min := ∞
    for succ in successors(node) do
        if succ not in path then
            path.push(succ)
            t := search(path, g + cost(node, succ), bound)
            if t = FOUND then return FOUND
            if t < min then min := t
            path.pop()
        end if
    end for
    return min
end function

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 problémovém grafu, pokud je přípustná heuristická funkce h , tj.

${\ 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“).

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 na aktuální cestě , vyžaduje množství paměti, které 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í , což znamená, že

${\ displaystyle h (n) \ leq \ mathrm {cost} (n, n ') + h (n')}$

pro všechny uzly n a všechny sousedy n‘ o n ; docházejí k závěru, že ve srovnání s vyhledáváním stromu hrubou silou přes problém s exponenciální velikostí dosahuje IDA * menší hloubky vyhledávání (o konstantní faktor), ale ne menšího větvícího faktoru.

Rekurzivní nejlepší vyhledávání 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ů.

Aplikace

Aplikace IDA * se nacházejí v takových problémech, jako je plánování .

Reference