Iteracyjne pogłębianie wyszukiwania w głąb

Iteracyjne pogłębianie wyszukiwania w głąb

Klasa	Algorytm wyszukiwania
Struktura danych	Drzewo , wykres
Wydajność w najgorszym przypadku	${\ Displaystyle O (b ^ {d})}$ , gdzie $współczynnikiem$ rozgałęzienia, a głębokość najpłytszego rozwiązania jest ${\ Displaystyle d}$
Złożoność przestrzeni w najgorszym przypadku	${\ Displaystyle O (d)}$

W informatyce , iteracyjne pogłębianie przeszukiwania lub dokładniej iteracyjne pogłębianie przeszukiwania w głąb (IDS lub IDDFS) to strategia przeszukiwania przestrzeni stanów /grafów, w której wersja przeszukiwania w głąb o ograniczonej głębokości jest uruchamiana wielokrotnie z rosnącymi limitami głębokości, aż do cel zostaje znaleziony. IDDFS jest optymalny, podobnie jak przeszukiwanie wszerz , ale zużywa znacznie mniej pamięci; w każdej iteracji odwiedza węzły w drzewie wyszukiwania w tej samej kolejności, co przeszukiwanie w głąb, ale skumulowana kolejność, w której węzły są odwiedzane po raz pierwszy, jest faktycznie wszerz.

Algorytm dla grafów skierowanych

Poniższy pseudokod przedstawia IDDFS zaimplementowany jako rekurencyjny DFS o ograniczonej głębokości (zwany DLS) dla grafów skierowanych . Ta implementacja IDDFS nie uwzględnia już odwiedzonych węzłów i dlatego nie działa dla grafów nieskierowanych .

     0  
            
             


    
        
             funkcja  IDDFS(korzeń)  jest  dla  głębokości  od  do  ∞  do  znalezienia, pozostała ← DLS(korzeń, głębokość)  jeśli  znaleziono ≠  null  to  zwróć  znalezione  inaczej jeśli  nie pozostała  to  zwróć wartość   null  funkcja  DLS(węzeł, głębokość)  jest  jeśli  głębokość = 0  to  jeśli  węzeł jest celem,  a następnie  zwróć  (węzeł,  prawda  )  w przeciwnym razie 
            

    
        
                 return  (  null  ,  true  )  (Nie znaleziono, ale może mieć dzieci)  w przeciwnym razie, jeśli  głębokość > 0  , to  any_remaining ←  false  foreach  child  węzła  do  znalezionego, pozostałe ← DLS(dziecko, głębokość-1)  jeśli  znaleziono ≠ null,  a  następnie  wróć  (znaleziono,  true  )  , jeśli  pozostaje  to  any_remaining ← prawda 
         (Co najmniej jeden węzeł znaleziony na głębokości, niech IDDFS się pogłębi)  return  (  null  , any_remaining) 

Jeśli węzeł docelowy zostanie znaleziony, DLS odwija ​​rekurencję powracającą bez dalszych iteracji. W przeciwnym razie, jeśli na tym poziomie głębokości istnieje co najmniej jeden węzeł, pozostała flaga pozwoli IDDFS na kontynuację.

2-krotki są przydatne jako wartość zwracana, aby zasygnalizować IDDFS dalsze pogłębianie lub zatrzymanie, w przypadku gdy głębokość drzewa i członkostwo w celu są nieznane a priori . Inne rozwiązanie mogłoby zamiast tego używać wartości wartowniczych do reprezentowania nie znalezionych lub pozostałych wyników poziomu .

Nieruchomości

IDDFS łączy efektywność przestrzenną przeszukiwania w głąb i kompletność przeszukiwania wszerz (gdy współczynnik rozgałęzienia jest skończony). Jeśli rozwiązanie istnieje, znajdzie ścieżkę rozwiązania z najmniejszą liczbą łuków.

Ponieważ wielokrotne iteracyjne wizyty pogłębiające mogą wydawać się marnotrawstwem, ale okazuje się, że nie jest to tak kosztowne, ponieważ w drzewie większość węzłów znajduje się na najniższym poziomie, więc nie ma większego znaczenia, jeśli wyższe poziomy są odwiedzane wielokrotnie czasy.

Główną zaletą IDDFS w przeszukiwaniu drzew gier jest to, że wcześniejsze wyszukiwania mają tendencję do ulepszania powszechnie używanych heurystyk, takich jak heurystyka zabójcy i przycinanie alfa-beta , dzięki czemu dokładniejsze oszacowanie wyniku różnych węzłów na końcowym przeszukiwaniu głębokości może wystąpić, a wyszukiwanie kończy się szybciej, ponieważ odbywa się w lepszej kolejności. Na przykład przycinanie alfa-beta jest najskuteczniejsze, jeśli najpierw wyszukuje najlepsze ruchy.

Drugą zaletą jest responsywność algorytmu. Ponieważ wczesne iteracje używają małych wartości dla $.$ wykonują się niezwykle szybko Pozwala to algorytmowi na niemal natychmiastowe dostarczanie wczesnych wskazań wyniku, po których następuje udoskonalenie w $wzrostu$ . Gdy jest używany w środowisku interaktywnym, takim jak szachy , funkcja ta umożliwia programowi grę w dowolnym momencie z aktualnie najlepszym ruchem znalezionym w dotychczas zakończonym wyszukiwaniu. Można to sformułować jako korekurencyjnie każdą głębokość wyszukiwania dając lepsze przybliżenie rozwiązania, chociaż praca wykonywana na każdym kroku jest rekurencyjna. Nie jest to możliwe w przypadku tradycyjnego przeszukiwania w głąb, które nie daje wyników pośrednich.

Analiza asymptotyczna

Złożoność czasowa

Złożoność czasowa IDDFS w (dobrze wyważonym) drzewie jest taka sama jak w przypadku wyszukiwania wszerz, tj. ${\ Displaystyle O (b ^ {d})}$ , gdzie ${\ displaystyle b }$ to współczynnik rozgałęzienia, $.$ głębokość celu

Dowód

W iteracyjnym wyszukiwaniu pogłębiającym węzły na głębokości $1$ rozwijane raz, te na głębokości $\ displaystyle d-1}$ aż do korzenia drzewa wyszukiwania, które re - jest rozszerzony razy ${\ displaystyle d + 1} .$ Tak więc całkowita liczba rozszerzeń w iteracyjnym przeszukiwaniu pogłębiającym wynosi

${\ Displaystyle b ^ {d} + 2b ^ {d-1} + 3b ^ {d-2} + \ cdots + (d-1) b ^ {2} + db + (d + 1) = \ suma _ { i=0}^{d}(d+1-i)b^{i}}$

gdzie ${\ Displaystyle b ^ {d}}$ to liczba rozszerzeń na głębokości ${\ Displaystyle d}$ , ${\ Displaystyle 2b ^ {d-1}}$ to liczba rozszerzeń na głębokości ${\ displaystyle d-1}$ i tak dalej. Faktoryzacja daje ${\ displaystyle b ^ {d}}$

${\ Displaystyle b ^ {d} (1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{- D})}$

Teraz niech ${\ Displaystyle x = {\ Frac {1} {b}} = b ^ {- 1}}$ . Następnie mamy

${\ Displaystyle b ^ {d} (1 + 2x +3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})}$

To jest mniej niż nieskończona seria

${\ Displaystyle b ^ {d} (1 + 2x + 3x ^ {2 }+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)}$

do którego się zbiega

$^ {2}}}}$${\ Displaystyle b ^ {d} (1-x) ^ {- 2} = b ^ {d} {\ Frac {1} (1-x$${\ displaystyle abs (x) <1}$ , za

To znaczy mamy

${\ Displaystyle b ^ {d} (1 + 2x + 3x ^ {2} + \ cdots + (d-1) x ^ {d-2} + dx ^ {d-1} + (d + 1) x ^ {d}) \ równoważnik b ^ {d} (1-x) ^ {- 2}}$ za ${\ displaystyle abs (x) <1$

ponieważ ${\ Displaystyle (1-x) ^ {- 2}}$ lub $}}$${\ Displaystyle \ lewo (1- {\ Frac {1} {b}} \ po$$)$ jest stałą niezależną od $głębokości$ ), jeśli (tj. jeśli współczynnik rozgałęzienia , biegnący czas pierwszego iteracyjnego poszukiwania pogłębiającego w głąb wynosi ${\ Displaystyle O (b ^ {d})}$ .

Przykład

Dla ${\ Displaystyle b = 10}$ i ${\ Displaystyle d = 5}$ liczba to

${\ Displaystyle \ suma _ {i = 0} ^ {5} (5 + 1-i) 10 ^{i}=6+50+400+3000+20000+100000=123456}$

Podsumowując, iteracyjne wyszukiwanie pogłębiające od głębokości $aż$$11$ głębokości $głąb$ tylko o około węzłów niż pojedyncze wyszukiwanie wszerz lub w ograniczone wyszukiwanie do głębokości $\$ kiedy $displaystyle b = 10}$ .

Im wyższy współczynnik rozgałęzienia, tym niższy narzut wielokrotnie rozwijanych stanów, ale nawet gdy współczynnik rozgałęzienia wynosi 2, iteracyjne przeszukiwanie pogłębiające zajmuje tylko około dwa razy więcej czasu niż pełne przeszukiwanie wszerz. Oznacza to, że złożoność czasowa iteracyjnego pogłębiania jest nadal ${\ Displaystyle O (b ^ {d})}$ .

Złożoność przestrzeni

Złożoność przestrzenna IDDFS $_$$_$ gdzie .

Dowód

Ponieważ IDDFS w dowolnym momencie jest zaangażowany w przeszukiwanie w głąb, musi przechowywać tylko stos węzłów reprezentujący gałąź drzewa, którą rozwija. $Ponieważ$ znajduje rozwiązanie o optymalnej długości, maksymalna głębokość tego stosu wynosi , $zatem$ to

Ogólnie rzecz biorąc, iteracyjne pogłębianie jest preferowaną metodą wyszukiwania, gdy istnieje duża przestrzeń poszukiwań, a głębokość rozwiązania nie jest znana.

Przykład

Dla poniższego wykresu:

przeszukiwanie w głąb rozpoczynające się od A, zakładając, że lewe krawędzie na pokazanym grafie są wybrane przed prawymi i zakładając, że wyszukiwanie zapamiętuje poprzednio odwiedzone węzły i nie będzie ich powtarzać (ponieważ jest to mały graf), odwiedzi węzły w następującej kolejności: A, B, D, F, E, C, G. Krawędzie przechodzące w tym przeszukiwaniu tworzą drzewo Trémaux , strukturę mającą ważne zastosowania w teorii grafów .

Wykonanie tego samego wyszukiwania bez zapamiętywania wcześniej odwiedzonych węzłów powoduje odwiedzanie węzłów w kolejności A, B, D, F, E, A, B, D, F, E itd. na zawsze, złapanych w A, B, D, F , cykl E i nigdy nie osiągając C lub G.

Iteracyjne pogłębianie zapobiega tej pętli i dotrze do następujących węzłów na następujących głębokościach, zakładając, że przebiega od lewej do prawej, jak powyżej:

• 0: A
• 1: A, B, C, E

(Pogłębianie iteracyjne widziało teraz C, podczas gdy konwencjonalne przeszukiwanie w głąb nie.)

• 2: A, B, D, F, C, G, E, F

(Nadal widzi C, ale pojawiło się później. Widzi również E inną ścieżką i dwukrotnie zapętla się z powrotem do F.)

• 3: A, B, D, F, E, C, G, E, F, B

W przypadku tego wykresu, gdy zostanie dodana większa głębokość, dwa cykle „ABFE” i „AEFB” po prostu wydłużą się, zanim algorytm się podda i spróbuje innej gałęzi.

Powiązane algorytmy

Podobna do iteracyjnego pogłębiania jest strategia wyszukiwania zwana iteracyjnym przeszukiwaniem wydłużającym, która działa z rosnącymi limitami kosztu ścieżki zamiast z limitami głębokości. Rozszerza węzły w kolejności rosnącego kosztu ścieżki; dlatego pierwszym celem, jaki napotyka, jest cel o najniższym koszcie ścieżki. Ale iteracyjne wydłużanie pociąga za sobą znaczny narzut, co czyni go mniej użytecznym niż iteracyjne pogłębianie.

Pogłębianie iteracyjne A* to wyszukiwanie typu najlepszy pierwszy, które wykonuje iteracyjne pogłębianie na podstawie wartości „ f ” podobnych do tych obliczanych w algorytmie A* .

Dwukierunkowe IDDFS

IDDFS ma dwukierunkowy odpowiednik, który naprzemiennie przeprowadza dwa wyszukiwania: jedno rozpoczynające się od węzła źródłowego i poruszające się wzdłuż skierowanych łuków, a drugie rozpoczynające się od węzła docelowego i przebiegające wzdłuż skierowanych łuków w przeciwnym kierunku (od węzła głównego łuku do węzeł ogonowy). Proces wyszukiwania najpierw sprawdza, czy węzeł źródłowy i docelowy są takie same, a jeśli tak, zwraca trywialną ścieżkę składającą się z pojedynczego węzła źródłowego/docelowego. W przeciwnym razie proces wyszukiwania do przodu rozszerza węzły potomne węzła źródłowego (ustaw ${\ displaystyle A}$$) , proces$$się$ węzły nadrzędne węzła docelowego (zestaw ) $i$ sprawdza się, czy . Jeśli tak, zostanie znaleziona najkrótsza ścieżka. W przeciwnym razie głębokość wyszukiwania jest zwiększana i wykonywane są te same obliczenia.

Jednym z ograniczeń algorytmu jest to, że najkrótsza ścieżka składająca się z nieparzystej liczby łuków nie zostanie wykryta. Załóżmy, że mamy najkrótszą ścieżkę $, t \ rangle.} Gdy głębokość osiągnie$$wstecz$$.$ przeskoki wzdłuż łuków, wyszukiwanie do przodu rozpocznie się od i wyszukiwanie będzie kontynuowane od ${\ displaystyle v}$ do ${\ displaystyle u}$ . Obrazowo granice poszukiwań będą się wzajemnie przenikać, a zamiast tego zostanie zwrócona nieoptymalna ścieżka składająca się z parzystej liczby łuków. Zilustrowano to na poniższych schematach:

Dwukierunkowe IDDFS

Jeśli chodzi o złożoność przestrzeni, algorytm koloruje najgłębsze węzły w procesie wyszukiwania do przodu, aby wykryć istnienie środkowego węzła, w którym spotykają się dwa procesy wyszukiwania.

$, że jeśli$ źródłowy i docelowy znajdują się w różnych silnie połączonych komponentach, łuku pozostawiając $wchodząc$ , $wyszukiwanie$ się nie zakończy.

Złożoność czasu i przestrzeni

Czas działania dwukierunkowego IDDFS jest określony wzorem

${\ Displaystyle 2 \ suma _ {k = 0} ^ {n/2} b ^ {k}}$

a złożoność przestrzeni jest dana przez

${\ Displaystyle b ^ {n/2},}$

gdzie $jest$ węzłów w najkrótszej ścieżce ${\ displaystyle s, t}$ . Ponieważ złożoność czasu działania iteracyjnego pogłębiania przeszukiwania w głąb wynosi ${\ Displaystyle \ suma _ {k = 0} ^ {n} b ^ {k}$ }

${\ Displaystyle {\ Frac {\ suma _ {k = 0} ^ {n} b ^ {k}} {2 \ suma _ {k = 0} ^ {n/2} b ^ {k}}} = { \frac {\frac {1-b^{n+1}}{1-b}}{2{\frac {1-b^{n/2+1}}{1-b}}}}={ \frac {1-b^{n+1}}{2(1-b^{n/2+1})}}={\frac {b^{n+1}-1}{2(b^ {n/2+1}-1)}}\około {\frac {b^{n+1}}{2b^{n/2+1}}}=\Theta (b^{n/2}) .}$

Pseudo kod

 Funkcja  Build-Path(s, μ, B)  to  π ← Znajdź najkrótszą ścieżkę (s, μ)  (Rekursywnie oblicz ścieżkę do węzła przekaźnikowego)  usuń ostatni węzeł z π  return  π ${\ Displaystyle \ circ}$ B  (Dołącz stos przeszukiwania wstecz) 

    
        
     funkcja  Depth-Limited-Search-Forward (u, Δ, F)  jest taka,  że ​​jeśli  Δ = 0  , to  fa ← fa ${\ Displaystyle \ cup}$ {u}  (Zaznacz węzeł)  return  foreach  child  of  u  do  Depth-Limited-Search-Forward(child, Δ − 1, F) 

        
            
     funkcja  Depth-Limited-Search-Backward(u, Δ, B, F)  jest  poprzedzona u do B  jeśli  Δ = 0  to  jeśli  u  w  F  to  powrót  u  (Osiągnięto zaznaczony węzeł, użyj go jako węzła przekaźnikowego)  usuń węzeł główny B  zwróć null  foreach  parent  of  u  do  μ ← Depth-Limited-Search-Backward(parent, Δ − 1, B, F)  if  μ   
            ${\ Displaystyle \ neq}$ null  , a następnie  wróć  μ usuń węzeł główny B, zwróć   null 

 funkcję 
   
        
                Znajdź najkrótszą ścieżkę (s, t)  jest  , jeśli  s = t,  a następnie  wróć  <s> F, B, Δ ← ∅, ∅, 0  na zawsze wykonaj  wyszukiwanie do przodu z ograniczeniem głębokości (s, Δ, F)  foreach  δ = Δ, Δ + 1  do  μ ← wyszukiwanie z ograniczeniem głębokości do tyłu (t, δ, B, F)  jeśli  μ ${\ Displaystyle \neq }$ null, a następnie  wróć  Build-Path(s, μ, B)  (Znaleziono węzeł przekaźnikowy)  F, Δ ← ∅, Δ + 1