Algorytm SMA*
Algorytm SMA* to metoda przeszukiwania grafu prostego, która umożliwia znalezienie najkrótszej ścieżki pomiędzy wierzchołkiem startowym a dowolnym wierzchołkiem docelowym.
Historia i rozwój algorytmu
Pierwszym kompletnym i optymalnym rozwiązaniem heurystycznym dla tego problemu był algorytm A*, wprowadzony w 1968 roku. Jego główną wadą jest nadmierne zapotrzebowanie na pamięć. W odpowiedzi na ten problem stworzono algorytm MA*, opisany w 1989 roku, który zapewnia akceptowalne rozwiązania w określonych granicach pamięci (przekraczających wymagane minimum). W 1992 roku Stuart Russell przedstawił algorytm SMA*, który jest uproszczoną wersją MA* i lepiej wykorzystuje dostępną pamięć.
Autor wskazuje, że kluczową zaletą SMA* w porównaniu do MA* jest zastosowanie zmiennej pathmax. Jej wartość jest ustalona tak, aby z jednej strony była co najmniej równa wartości dla optymalnego rozwiązania, a z drugiej strony umożliwiała efektywne wybieranie rozwiązań o zbyt wysokiej funkcji kosztu i usuwanie związanych z nimi rezultatów pośrednich. Dodatkowo, SMA* jest według autora łatwiejszy do zrozumienia i implementacji, w algorytmie zastosowano również bardziej efektywne struktury danych do przechowywania wyników pośrednich oraz udoskonalono proces odrzucania rezultatów o najgorszych wartościach funkcji kosztu, gdy pamięć przydzielona do zadania jest w pełni wykorzystana.
