Dijkstra’s Algorithmus und Best-First-Search#
Dijkstra’s Algorithmus arbeitet, indem er Scheitelpunkte im Graphen besucht, beginnend mit dem Startpunkt des Objekts. Er untersucht dann wiederholt den nächstgelegenen, noch nicht untersuchten Knotenpunkt und fügt dessen Eckpunkte der Menge der zu untersuchenden Eckpunkte hinzu. Der Algorithmus expandiert vom Startpunkt aus, bis er das Ziel erreicht. Dijkstra’s Algorithmus findet garantiert einen kürzesten Weg vom Startpunkt zum Ziel, solange keine der Kanten negative Kosten hat. (Ich schreibe „ein kürzester Weg“, weil es oft mehrere gleich kurze Wege gibt.) Im folgenden Diagramm ist das rosafarbene Quadrat der Ausgangspunkt, das blaue Quadrat ist das Ziel, und die blaugrünen Flächen zeigen, welche Bereiche Dijkstras Algorithmus durchsucht hat. Die hellsten blaugrünen Flächen sind diejenigen, die am weitesten vom Ausgangspunkt entfernt sind und somit die „Grenze“ der Erkundung bilden:
Der Greedy Best-First-Search-Algorithmus funktioniert auf ähnliche Weise, nur dass er über eine Schätzung (Heuristik genannt) verfügt, wie weit ein beliebiger Knoten vom Ziel entfernt ist. Anstatt den Punkt auszuwählen, der dem Startpunkt am nächsten liegt, wird der Punkt ausgewählt, der dem Ziel am nächsten liegt. Bei der Greedy Best-First-Search ist nicht garantiert, dass sie einen kürzesten Weg findet. Er läuft jedoch viel schneller als der Dijkstra-Algorithmus, da er die heuristische Funktion verwendet, um sehr schnell zum Ziel zu gelangen. Wenn das Ziel beispielsweise südlich der Startposition liegt, wird sich Greedy Best-First-Search auf Wege konzentrieren, die in Richtung Süden führen. Im folgenden Diagramm stellt Gelb die Knoten mit einem hohen heuristischen Wert (hohe Kosten, um zum Ziel zu gelangen) und Schwarz die Knoten mit einem niedrigen heuristischen Wert (niedrige Kosten, um zum Ziel zu gelangen) dar. Es zeigt, dass Greedy Best-First-Search im Vergleich zu Dijkstras Algorithmus sehr schnell Wege finden kann:
Beide Beispiele illustrieren jedoch den einfachsten Fall – wenn die Karte keine Hindernisse hat und der kürzeste Weg wirklich eine gerade Linie ist. Betrachten wir nun das konkave Hindernis, wie es im vorigen Abschnitt beschrieben wurde. Dijkstra’s Algorithmus arbeitet härter, findet aber garantiert einen kürzesten Weg:
Greedy Best-First-Search dagegen macht weniger Arbeit, aber sein Weg ist eindeutig nicht so gut:
Das Problem ist, dass Greedy Best-First-Search „gierig“ ist und versucht, zum Ziel zu gelangen, auch wenn es nicht der richtige Weg ist. Da sie nur die Kosten berücksichtigt, um zum Ziel zu gelangen, und die Kosten des bisherigen Weges ignoriert, geht sie weiter, auch wenn der Weg, auf dem sie sich befindet, sehr lang geworden ist.
Wäre es nicht schön, das Beste von beiden zu kombinieren? A* wurde 1968 entwickelt, um heuristische Ansätze wie Greedy Best-First-Search und formale Ansätze wie Dijsktra’s Algorithmus zu kombinieren. Das ist insofern etwas ungewöhnlich, als heuristische Ansätze in der Regel einen ungefähren Weg zur Lösung von Problemen bieten, ohne zu garantieren, dass man die beste Antwort erhält. A* baut jedoch auf der Heuristik auf, und obwohl die Heuristik selbst keine Garantie bietet, kann A* einen kürzesten Weg garantieren.