Algorytm Best-First-Search

Każdemu przeszukiwanemu stanowi (węzłowi) v nadawana jestheurystyczna ocena liczbowa f (v) , szacująca, na ile daleko dany stanjest od docelowego.

Algorytm przeszukuje w pierwszej kolejności stany o najniższej wartości funkcji heurystycznej.

Uwagi o Best First Search

Best First Search przeszukuje w głąb (a nie wszerz) coraz bardziej oddalając sią od stanu początkowego.

Przy natknięciu się na stan niepoprawny (w szczególności, gdy wszyscy potomkowie są niepoprawni), algorytm wycofuje się do stanów o gorszej wartości heurystyki.

Liczba takich wycofań zależy od: jakości podanej heurystyki i od sposobu budowania stanów potomnych (pewna wiedzę o problemie można zawrzeć już tu, aby nie dopuszczać do stanów bezpośrednio niepoprawnych).

Struktury danych i złożoność obliczeniowa dla Open i Closed

Zbiór Openimplementowany jest przez kolejkę priorytetową (ang. PriorityQueue) porządkująca˛ stany wg heurystyki. Wstawienie nowego elementu do kolejki z zachowaniem porządku ma złożoność O(log n). Wyciągnięcie elementu z kolejki ma złożoność O(1)

Zbiór Closedimplementowany jest przez hashmape˛. Sprawdzenie, czy pewien stan już był rozpatrzony i jest w zbiorze Closed, ma złożoność O(1).

Heurystyka monotoniczna

Heurystyka jest na pewno dopuszczalna, jeżeli jest monotoniczna, tzn.:

v,w h(v) 6 d(v,w) + h(w). (1)

Innymi słowy, dodanie do jakiejkolwiek ścieżki dodatkowego węzła powoduje, że nowa ścieżka jest nie krótsza od poprzedniej. A równość może mieć miejsce tylko, gdy dodamy węzeł poruszając się po prostej do celu.

algorytm A*

Funkcja decydująca o porządku wyciągania stanów ze zbioru Open jest suma˛ dwóch funkcji:

f (v) = g(v) + h(v),

gdzie g(v) wyraża faktyczny koszt (odległość) przebyty od stanu początkowego do v, natomiast h(v) jest heurystyką szacującą koszt (odległość) od stanu v do stanu docelowego.

Funkcja h musi być´ tzw. dopuszczalna˛ heurystyka˛, tzn. nie wolno jej przeszacowywać kosztu (odległości) do stanu docelowego (o tym dokładniej jeszcze później. . . ).

W zastosowaniach path-findingczy routing (gdzie mamy fizyczny/geograficzny graf) częstym i poprawnym wyborem dla h, jest zwykła odległość w linii prostej od v do stanu docelowego (na pewno nie przeszacowujemy).

W odróżnieniu od Best First Search, A. bierze pod uwagę˛ także g(v), a nie tylko heurystykę˛ zorientowana˛ na cel. A zatem w budowanej ścieżce z jednej strony preferowane są stany bliskie początkowemu, a z drugiej jednocześnie bliskie końcowemu (w sensie minimalizacji tej sumy).

W algorytmie, każdy stan v musi mieć´ możliwość zapamiętania swoich trzech wartości: g(v), h(v), f (v).

Przechodząc od pewnego stanu v do pewnego stanu w, wartość funkcji g wyznaczamy jako: g(w) = g(v) + d(v,w), gdzie d(v,w) oznacza koszt przejścia z v do w.