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 zupełnym i optymalnym rozwiązaniem heurystycznym tego problemu był algorytm A*, który opisano w 1968 roku[1]. Wadą tego algorytmu jest niepraktycznie duże zapotrzebowanie na pamięć[2]. Jedną z prób rozwiązania tego problemu jest algorytm MA* opisany w 1989 roku, który gwarantuje znalezienie akceptowalnych rozwiązań w określonych granicach pamięci (powyżej wymaganego minimum)[3]. 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 funkcji kosztu w przypadku wykorzystania całej pamięci przydzielonej do realizacji zadania[2].

Przypisy

  1. ↑ Peter E.P.E. Hart Peter E.P.E., Nils J.N.J. Nilsson Nils J.N.J., BertramB. Raphael BertramB., A Formal Basis for the Heuristic Determination of Minimum Cost Paths, „IEEE Transactions on Systems Science and Cybernetics”, 4 (2), IEEE Xplore, 1968, s. 100–107, DOI: 10.1109/TSSC.1968.300136 .
  2. ↑ a b publikacja w otwartym dostępie – możesz ją przeczytaćStuartS. Russell StuartS., Efficient memory-bounded search methods, [w:] BerndB. Neumann (red.), ECAI 92: 10th European Conference on Artificial Intelligence, August 3-7, 1992, Vienna, Austria : proceedings, John Wiley & Sons, Nowy Jork, 1992, s. 1–5, ISBN 978-0-471-93608-4 .
  3. ↑ P.P.P.P. Chakrabarti P.P.P.P. i inni, Heuristic search in restricted memory, „Artificial Intelligence”, 41 (2), Elsevier B.V., 1989, s. 197–221, DOI: 10.1016/0004-3702(89)90010-6 .