Jaki jest sens algorytmu IDA * vs A *

Question

Nie rozumiem, jak oszczędza się pamięć w trybie IDA*. Z tego, jak rozumiem, że IDA* jest A* z iteracyjnym pogłębianiem.

Jaka jest różnica między ilością pamięci A* używa vs IDA*.

Czy ostatnia iteracja IDA* zachowuje się dokładnie tak jak A* i używa tej samej ilości pamięci. Kiedy śledzę IDA* zdaję sobie sprawę, że musi również zapamiętać priorytetową kolejkę węzłów, które są poniżej progu f(n).

Rozumiem, że pierwsza funkcja wyszukiwania głębi pomaga w głębszym wyszukiwaniu, pozwalając mu na wykonanie pierwszej operacji, takiej jak wyszukiwanie, bez konieczności zapamiętywania każdego węzła. Ale myślałem, że A* zachowuje się już jak głębia, ponieważ po drodze ignoruje niektóre pod-drzewa. W jaki sposób Iteracyjne pogłębianie powoduje, że zużywa on mniej pamięci?

Kolejne pytanie to Głębokie pierwsze wyszukiwanie z iteracyjnym pogłębieniem pozwala znaleźć najkrótszą ścieżkę, dzięki czemu zachowuje się jak pierwsza szerokość. Ale A* zwraca już optymalną najkrótszą ścieżkę (biorąc pod uwagę, że heurystyka jest dopuszczalna). W jaki sposób pomaga to iteracyjne pogłębienie. Czuję, że ostatnia iteracja IDA * jest identyczna z A*.

Answer 1

W przeciwieństwie do A*, nie trzeba przechowywać zestawu próbnych węzłów, które zamierzasz odwiedzić, dlatego zużycie pamięci jest dedykowane tylko lokalnym zmiennym funkcji rekursywnej.

Chociaż ten algorytm jest niższe zużycie pamięci, to ma swoje wady:

odróżnieniu *, IDA * nie wykorzystuje dynamiczne programowanie i dlatego często kończy się badające same węzły, wiele razy. (IDA* In Wiki)

Funkcja heurystyczna musi jeszcze zostać określone w Twoim przypadku, aby nie skanować cały wykres, ale pamięć skanu jest wymagana w każdym momencie jest tylko ścieżka, którą aktualnie skanowanie bez okolicznych węzłów.

Oto demo pamięci wymaganej w każdym algorytmie:

W algorytmie tym A* wszystkich węzłów i ich okolic węzłów musi być zawarte w „potrzebie przejdź do "listy podczas gdy w IDA* otrzymujesz kolejne węzły" leniwie ", gdy dojdziesz do jego węzła podglądu, więc nie musisz dodawać go do dodatkowego zestawu.

Jak wspomniano w komentarzach, IDA* is basically just IDDFS with heuristics: