Pogłębianie iteracyjne A*

Pogłębianie iteracyjne A*

Klasa	Algorytm wyszukiwania
Struktura danych	Drzewo , wykres
Złożoność przestrzeni w najgorszym przypadku	${\ Displaystyle O (d)}$

Pogłębianie iteracyjne A* ( IDA* ) to algorytm przechodzenia grafu i wyszukiwania ścieżki , który może znaleźć najkrótszą ścieżkę między wyznaczonym węzłem początkowym a dowolnym elementem zbioru węzłów docelowych w grafie ważonym. Jest to wariant iteracyjnego pogłębiania przeszukiwania w głąb , który zapożycza pomysł wykorzystania funkcji heurystycznej do oceny pozostałego kosztu dotarcia do celu z algorytmu wyszukiwania A* . Ponieważ jest to algorytm przeszukiwania w głąb, jego wykorzystanie pamięci jest mniejsze niż w A*, ale w przeciwieństwie do zwykłego iteracyjnego wyszukiwania pogłębiającego, koncentruje się on na eksploracji najbardziej obiecujących węzłów, a zatem nie dociera 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ę wielokrotnym eksplorowaniem tych samych węzłów.

Podczas gdy standardowe iteracyjne pogłębianie w głąb wyszukiwania wykorzystuje głębokość wyszukiwania jako punkt odcięcia dla każdej iteracji, IDA * używa bardziej informacyjnego $(n)}$${\ displaystyle f (n) = g ( n) +$$\ Displaystyle h (n) }$ , gdzie ${\ Displaystyle g (n)}$ to koszt podróży od korzenia do węzła $)$ h $dla$ problemu heurystycznym oszacowaniem kosztu podróży od do celu.

Algorytm został po raz pierwszy opisany przez Richarda Korfa w 1985 roku.

Opis

Iteracyjne pogłębianie-A * działa w następujący sposób: przy każdej iteracji przeszukuj najpierw w głąb, odcinając gałąź, gdy jej całkowity koszt ${\ displaystyle f (n) =g(n)+h(n)}$ przekracza określony próg . Próg ten zaczyna się od oszacowania kosztu w stanie początkowym i wzrasta dla każdej iteracji 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

              
               
                 
                 



 ścieżka  bieżąca ścieżka wyszukiwania (działa jak stos)  węzeł  bieżący węzeł  (ostatni węzeł w bieżącej ścieżce)  g  koszt dotarcia do bieżącego węzła  f  szacowany koszt najtańszej ścieżki (root..node..goal)  h  (  węzeł  )  szacowany koszt najtańsza ścieżka (node..goal)  cost  (  node  ,  succ  )  krok cost function  is_goal  (  node  )  cel test  następcy  (  node  ) 

 
 
          funkcja rozwijania węzłów, rozwiń węzły uporządkowane według g + h(węzeł)  ida_star  (  root  )  zwróć albo NOT_FOUND albo parę z najlepszą ścieżką i jej  procedurą kosztową   ida_star  (  root  )  bound  :=  h  (  root  )  path  := [  root  ]  pętla  t  :=  szukaj  (  ścieżka  , 0,  granica  )  jeśli  t  = ZNALEZIONO  to wróć  
         
    


    
      (ścieżka, granica)  jeśli  t  = ∞  to zwróć  NOT_FOUND  granica  :=  t  koniec pętli  koniec procedury  wyszukiwanie  funkcji  (  ścieżka  ,  g  ,  granica  )  węzeł  :=  ścieżka  .last  f  :=  g  +  h  (  węzeł  )  jeśli  f  >  granica  to powrót  f  jeśli  is_cel  (    
             
              węzeł  )  następnie zwróć  ZNALEZIONO  min  := ∞  dla  succ  w  następnikach  (  węzeł  )  zrób  jeśli  succ  nie  w  ścieżce  to  ścieżka  .push(  succ  )  t  :=  szukaj  (  ścieżka  ,  g  +  koszt  (  węzeł  ,  succ  ),  powiązany  )  jeśli  t    
             
    
     
 = ZNALEZIONO  następnie zwróć  ZNALEZIONO  if  t  <  min  then  min  :=  t  ścieżka  .pop()  end  if  end for  return  min  end funkcja 

Nieruchomości

Podobnie jak A*, IDA* gwarantuje znalezienie najkrótszej ścieżki prowadzącej od danego węzła początkowego do dowolnego węzła docelowego na grafie problemu, jeśli funkcja heurystyczna h jest dopuszczalna , tj.

${\ Displaystyle h (n) \ równoważnik h ^ {*} (n)}$

dla wszystkich węzłów n , gdzie h * jest prawdziwym kosztem najkrótszej ścieżki od n do najbliższego celu („doskonała heurystyka”).

IDA* jest korzystne, gdy problemem jest ograniczona pamięć. Wyszukiwanie * utrzymuje dużą kolejkę niezbadanych węzłów, które mogą szybko zapełnić pamięć. Z drugiej strony, ponieważ IDA* nie zapamiętuje żadnego węzła oprócz tych znajdujących się na bieżącej ścieżce , wymaga ilości pamięci , która jest liniowa tylko w długości konstruowanego rozwiązania. Jego złożoność czasową analizują Korf i in. przy założeniu, że heurystyczne oszacowanie kosztów h jest spójne , co oznacza, że

$\ Displaystyle h (n) \ równoważnik \ operatorname {koszt} (n, n ') + h (n')}$

dla wszystkich węzłów n i wszystkich sąsiadów n' z n ; dochodzą do wniosku, że w porównaniu z przeszukiwaniem drzewa metodą brute-force nad problemem o wykładniczej wielkości, IDA* osiąga mniejszą głębokość wyszukiwania (o stały współczynnik), ale nie mniejszy współczynnik rozgałęzienia.

Wyszukiwanie rekurencyjne od najlepszego do pierwszego to kolejna ograniczona pamięcią wersja wyszukiwania A*, która w praktyce może być szybsza niż IDA*, ponieważ wymaga mniejszej regeneracji węzłów.

Aplikacje

Zastosowania IDA* znajdują zastosowanie w takich problemach jak planowanie .