SMA*

SMA* lub Simplified Memory Bounded A* to algorytm najkrótszej ścieżki oparty na algorytmie A* . Główną zaletą SMA* jest to, że używa ograniczonej pamięci, podczas gdy algorytm A* może wymagać pamięci wykładniczej. Wszystkie inne cechy SMA* są dziedziczone z A*.

Nieruchomości

SMA* ma następujące właściwości

• Działa z heurystyką , podobnie jak A*
• Jest kompletna, jeśli dozwolona pamięć jest wystarczająco duża, aby przechowywać najpłytsze rozwiązanie
• Jest optymalny, jeśli dozwolona pamięć jest wystarczająco wysoka, aby przechowywać najpłytsze optymalne rozwiązanie, w przeciwnym razie zwróci najlepsze rozwiązanie, które mieści się w dozwolonej pamięci
• Unika powtarzających się stanów, o ile pozwala na to ograniczenie pamięci
• Wykorzysta całą dostępną pamięć
• Zwiększenie ograniczenia pamięci algorytmu tylko przyspieszy obliczenia
• Gdy dostępna jest wystarczająca ilość pamięci, aby pomieścić całe drzewo wyszukiwania, obliczenia mają optymalną szybkość

Realizacja

Implementacja prostego A* ograniczonego pamięcią jest bardzo podobna do implementacji A*; jedyna różnica polega na tym, że węzły o najwyższym koszcie f są usuwane z kolejki, gdy nie ma już miejsca. Ponieważ te węzły są usuwane, prosty A* ograniczony pamięcią musi pamiętać koszt f najlepiej zapomnianego dziecka węzła nadrzędnego. Kiedy wydaje się, że wszystkie zbadane ścieżki są gorsze od takiej zapomnianej ścieżki, ścieżka jest regenerowana.

Pseudo kod: funkcja prosta ograniczona pamięcią A*-gwiazda(problem): ścieżka

kolejka: zbiór węzłów uporządkowanych według f-cost;

zaczynać

 kolejka.insert(problem.węzeł główny); 

 while True rozpocznij, jeśli kolejka.empty() następnie zwróć błąd; //nie ma rozwiązania pasującego do podanego węzła pamięci := kolejka.begin();  // min-f-cost-node if problem.is-goal(node) następnie zwróć sukces;  s := następny-następca (węzeł) if !problem.is-goal(s) && głębokość(s) == maksymalna_głębokość następnie f(s) := inf;  // nie ma już pamięci do przejścia przez s, więc cała ścieżka jest bezużyteczna else f(s) := max(f(node), g(s) + h(s));  // wartość f następnika to maksimum // wartość f rodzica i // heurystyka następnika + długość ścieżki do końca następnika, jeśli nie ma więcej następców, zaktualizuj koszt f węzła i tych jego przodkowie w razie potrzeby if node.successors ⊆ kolejka, a następnie kolejka.remove(węzeł);  // wszystkie dzieci zostały już dodane do kolejki krótszą drogą jeśli pamięć jest pełna to zacznij źle Node := najpłytszy węzeł z najwyższym kosztem f;  dla rodzica w złym węźle.rodzice rozpoczynają parent.successors.remove(bad Node);  w razie potrzeby kolejka.wstaw(rodzic);  koniec za koniec, jeśli  

 kolejka.wstaw(y); koniec póki  

koniec</syntax highlight>