Algorytm A*: Różnice pomiędzy wersjami

[wersja nieprzejrzana][wersja przejrzana]
Usunięta treść Dodana treść
Nie podano opisu zmian
Znacznik: Z urządzenia mobilnego
Tufor (dyskusja | edycje)
m Wycofano edycje użytkownika Filip2014 (dyskusja). Autor przywróconej wersji to Doctore.
Linia 83:
Kiedy A* kończy przeszukiwanie, ma (z definicji) znalezioną ścieżkę, której koszt jest mniejszy niż szacowany koszt jakiejkolwiek innej ścieżki (innej, czyli przechodzącej co najmniej przez jeden węzeł niewchodzący w skład znalezionej ścieżki). Ponieważ oszacowania są optymistyczne, algorytm A* może bezpiecznie zignorować te inne ścieżki. Innymi słowy, A* nigdy nie "przeoczy" ścieżki o niższym koszcie i dlatego jest dopuszczalny.
 
Przypuśćmy teraz, że jakiś inny algorytm B kończy swoje przeszukiwanie ze ścieżką, której koszt jest nie mniejszy niż szacowany koszt ścieżki przez jakiś węzeł X niewchodzący w skład znalezionej ścieżki. Algorytm B, bazując na informacjach wynikających z posiadanej heurystyki, nie może wykluczyć możliwości, że ścieżka przez węzeł X może mieć niższy koszt niż znaleziona ścieżka. Z tego wynika, że jeśli B bierze pod uwagę mniejszą liczbę węzłów niż A*, to B nie jest dopuszczalny. W związku z tym można stwierdzić, że A* bierze pod uwagę najmniejszą liczbę węzłów ze wszystkich dopuszczalnych algorytmów przeszukiwań, oczywiście pod warunkiem, że algorytmy te nie używają heurystyk dających bardziej dokładne oszacowania.a1
 
== Złożoność czasowa ==