Algorytm SMA*

Algorytm SMA* – algorytm przeszukiwania grafu prostego, odnajdujący najkrótszą ścieżkę pomiędzy wierzchołkiem początkowym a dowolnym z wierzchołków docelowych. Pierwszym i rozwiązaniem heurystycznym tego problemu był algorytm A*, który opisano w 1968 roku. Wadą tego algorytmu jest niepraktycznie duże zapotrzebowanie na pamięć. Jedną z prób rozwiązania tego problemu jest opisany w 1989 roku, który gwarantuje znalezienie akceptowalnych rozwiązań w określonych granicach pamięci (powyżej wymaganego minimum). SMA*, przedstawiony w 1992. przez Stuarta Russella, jest uproszczoną wersją tego algorytmu, która zarazem sprawniej wykorzystuje dostępną pamięć. Zdaniem autora największą zaletą algorytmu SMA* w porównaniu z MA* jest wykorzystanie zmiennej pathmax, która jest ustalana w ten sposób, że z jednej strony jej wartość jest co najmniej równa wartości dla optymalnego rozwiązania, a z drugiej strony pozwala na efektywną selekcję rozwiązań, których funkcja kosztu jest zbyt duża i kasowanie związanych z nimi rezultatów pośrednich. Ponadto jego zdaniem algorytm SMA* jest łatwiejszy do zrozumienia i implementacji, w algorytmie wprowadzono bardziej efektywne struktury danych do przechowywania rezultatów pośrednich oraz usprawniono obsługę odrzucania rezultatów charakteryzujących się najgorszymi wartościami w przypadku wykorzystania całej pamięci przydzielonej do realizacji zadania.