Algorytm Dijkstry i Best-First-Search#
Algorytm Dijkstry działa poprzez odwiedzanie wierzchołków w grafie, zaczynając od punktu początkowego obiektu. Następnie wielokrotnie bada najbliższy, jeszcze nie zbadany wierzchołek, dodając jego wierzchołki do zbioru wierzchołków, które mają być zbadane. Od punktu startowego rozszerza się na zewnątrz, aż do osiągnięcia celu. Algorytm Dijkstry ma gwarancję znalezienia najkrótszej ścieżki z punktu startowego do celu, o ile żadna z krawędzi nie ma ujemnego kosztu. (Piszę „najkrótszą ścieżkę”, ponieważ często istnieje wiele równoważnie krótkich ścieżek). Na poniższym rysunku różowy kwadrat to punkt startowy, niebieski kwadrat to cel, a tealowe obszary pokazują, jakie obszary zostały przeskanowane przez algorytm Dijkstry. Najjaśniejsze tealowe obszary są najdalej od punktu startowego, a zatem tworzą „granicę” eksploracji:
Greedy Best-First-Search algorytm działa w podobny sposób, z wyjątkiem tego, że ma pewne oszacowanie (zwane heurystyką), jak daleko od celu jest każdy wierzchołek. Zamiast wybierać wierzchołek najbliższy punktowi początkowemu, wybiera wierzchołek najbliższy celowi. Greedy Best-First-Search nie gwarantuje znalezienia najkrótszej ścieżki. Jednak działa znacznie szybciej niż algorytm Dijkstry, ponieważ używa funkcji heurystycznej, aby poprowadzić drogę do celu bardzo szybko. Na przykład, jeśli cel jest na południe od pozycji startowej, Greedy Best-First-Search będzie miał tendencję do skupiania się na ścieżkach, które prowadzą na południe. Na poniższym diagramie kolor żółty reprezentuje węzły o wysokiej wartości heurystycznej (wysoki koszt dotarcia do celu), a czarny – węzły o niskiej wartości heurystycznej (niski koszt dotarcia do celu). Pokazuje to, że Greedy Best-First-Search może znaleźć ścieżki bardzo szybko w porównaniu do algorytmu Dijkstry:
Jednakże oba te przykłady ilustrują najprostszy przypadek – gdy mapa nie ma żadnych przeszkód, a najkrótsza ścieżka naprawdę jest linią prostą. Rozważmy wklęsłą przeszkodę opisaną w poprzedniej sekcji. Algorytm Dijkstry pracuje ciężej, ale ma gwarancję, że znajdzie najkrótszą ścieżkę:
Greedy Best-First-Search z drugiej strony wykonuje mniej pracy, ale jego ścieżka wyraźnie nie jest tak dobra:
Problem polega na tym, że Greedy Best-First-Search jest „chciwy” i próbuje iść w kierunku celu, nawet jeśli nie jest to właściwa ścieżka. Ponieważ bierze pod uwagę tylko koszt dotarcia do celu i ignoruje koszt dotychczasowej ścieżki, kontynuuje nawet jeśli ścieżka, na której się znajduje stała się naprawdę długa.
Czy nie byłoby miło połączyć to, co najlepsze z obu rozwiązań? A* został opracowany w 1968 roku w celu połączenia heurystycznego podejścia jak Greedy Best-First-Search z formalnym podejściem jak Algorytm Dijsktra. Jest to trochę nietypowe rozwiązanie, ponieważ heurystyczne metody zwykle dają przybliżony sposób rozwiązywania problemów, nie gwarantując uzyskania najlepszej odpowiedzi. Jednak A* jest zbudowany na heurystyce i chociaż sama heurystyka nie daje gwarancji, A* może zagwarantować najkrótszą ścieżkę.