Pogłębianie iteracyjne A* - Iterative deepening A*
Klasa | Algorytm wyszukiwania |
---|---|
Struktura danych | drzewo , wykres |
Najgorsza złożoność przestrzeni |
Pogłębianie iteracyjne A* ( IDA* ) to algorytm przechodzenia przez graf i wyszukiwania ścieżki , który może znaleźć najkrótszą ścieżkę między wyznaczonym węzłem początkowym a dowolnym elementem zestawu węzłów celu w grafie ważonym. Jest to wariant iteracyjnego pogłębiania wyszukiwania w głąb, który zapożycza ideę użycia funkcji heurystycznej do oceny pozostałego kosztu dotarcia do celu z algorytmu wyszukiwania A* . Ponieważ jest to algorytm wyszukiwania w głąb, jego zużycie pamięci jest niższe niż w A*, ale w przeciwieństwie do zwykłego iteracyjnego wyszukiwania pogłębiającego, koncentruje się na eksploracji najbardziej obiecujących węzłów, a zatem nie sięga do tej samej głębokości wszędzie w drzewie wyszukiwania. W przeciwieństwie do A*, IDA* nie wykorzystuje programowania dynamicznego i dlatego często kończy się eksploracją tych samych węzłów wiele razy.
Podczas gdy standardowe iteracyjne wyszukiwanie z pogłębianiem na pierwszym miejscu wykorzystuje głębokość wyszukiwania jako punkt odcięcia dla każdej iteracji, IDA* wykorzystuje bardziej informacyjny , gdzie jest koszt podróży od korzenia do węzła i jest heurystycznym oszacowaniem kosztu podróżuj od celu.
Algorytm został po raz pierwszy opisany przez Richarda Korfa w 1985 roku.
Opis
Iterative-deepening-A* działa w następujący sposób: w każdej iteracji wykonaj wyszukiwanie w głąb, odcinając gałąź, gdy jej całkowity koszt przekroczy określony próg . Ten próg zaczyna się od oszacowania kosztu w stanie początkowym i wzrasta z każdą iteracją algorytmu. W każdej iteracji próg używany do następnej iteracji jest minimalnym kosztem wszystkich wartości, które przekroczyły bieżący próg.
Podobnie jak w A*, heurystyka musi mieć określone właściwości, aby zagwarantować optymalność (najkrótsze ścieżki). Zobacz Właściwości poniżej.
Pseudo kod
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
Nieruchomości
Podobnie jak A*, IDA* gwarantuje znalezienie najkrótszej ścieżki prowadzącej z danego węzła początkowego do dowolnego węzła celu na grafie problemu, jeśli funkcja heurystyczna h jest dopuszczalna , to znaczy
dla wszystkich węzłów n , gdzie h * jest prawdziwym kosztem najkrótszej ścieżki od n do najbliższego celu ("heurystyka doskonała").
IDA* przydaje się, gdy problemem jest ograniczona pamięć. Wyszukiwanie* utrzymuje dużą kolejkę niezbadanych węzłów, które mogą szybko zapełnić pamięć. W przeciwieństwie do tego, ponieważ IDA* nie zapamiętuje żadnego węzła poza tymi na bieżącej ścieżce , wymaga ilości pamięci, która jest tylko liniowa w długości rozwiązania, które konstruuje. Jego złożoność czasowa jest analizowana przez Korf et al. przy założeniu, że heurystyczne oszacowanie kosztów h jest spójne , co oznacza, że
dla wszystkich węzłów n i wszystkich sąsiadów n' z n ; doszli do wniosku, że w porównaniu z przeszukiwaniem drzewa metodą brute-force nad problemem o wielkości wykładniczej, IDA* osiąga mniejszą głębokość wyszukiwania (przy stałym współczynniku), ale nie mniejszy współczynnik rozgałęzienia.
Rekurencyjne wyszukiwanie typu „najlepszy-pierwszy” to kolejna wersja wyszukiwania A* o ograniczonej pamięci, która może być w praktyce szybsza niż IDA*, ponieważ wymaga mniej ponownego generowania węzłów.
Aplikacje
Zastosowania IDA* można znaleźć w takich problemach jak planowanie .