Ein * (Ein Stern) Algorithmus erklärt

Question

Ich wurde gebeten, Verbesserungen zu Dijkstra-Algorithmus zu untersuchen. Ich habe den A-Star-Algorithmus erforscht, aber ich finde viele Erklärungen verwenden unbekannte Wörter und mathematische Notationen.

Ich verstehe, ein Stern berücksichtigt nur Kanten in Richtung des Zielknotens. Wenn beispielsweise der A-Star-Algorithmus auf das Straßennetz des Vereinigten Königreichs angewendet würde und das Ziel Dundee und ich in London anfingen, würden nur nach Norden führende Kanten untersucht.

Ist das zumindest richtig?

Answer 1

A * verwendet eine Heuristik, um die minimalen Kosten eines Knotens für das Ziel zu erraten. Bei der Auswahl eines Knotens analysieren Sie also nicht nur die Kosten von Anfang an bis zu diesem Knoten, sondern auch die voraussichtlichen Kosten vom Knoten zum Ziel. Dies erlaubt, Pfade zu ignorieren, die wahrscheinlich in die falsche Richtung führen.

Wenn die Heuristik in Ihrem Beispiel die geographische Entfernung der Knoten verwendet, dann nach Norden führenden Straßen werden zuerst untersucht werden (weil sie ein klein geschätzt Gesamtkosten haben). Es ist jedoch möglich, dass diese Straßen während der Ausführung des Algorithmus eine sehr große tatsächliche Entfernung vom Start aggregieren (vielleicht, weil es viele Kurven gibt). Dann können auch nach Süden führende Straßen untersucht werden. Es ist also möglich, ein Stück nach Süden zu fahren und geradeaus nach Norden zu fahren, wenn dies kürzer ist als alle kurvigen Straßen, die nach Norden führen (ohne die tatsächliche Straßenkarte von GB zu berücksichtigen).

Die Art der Heuristik definiert die Qualität des Algorithmus. Wenn die Heuristik eine untere Grenze für die Entfernung angibt (d. H. Es ist nicht möglich, mit einem niedrigeren Preis zum Ziel zu gelangen, als die Heuristik sagt), dann ist der Pfad tatsächlich der kürzeste Weg. Wenn die Heuristik nicht ein untere Grenze, andere Wege könnten auch (was möglicherweise ein Kompromiss zwischen Algorithmus Laufzeit und Streckenqualität) erlaubt. Je besser die Heuristik die minimalen Kosten schätzt, desto weniger falsche Richtungen werden Sie untersuchen. I.e. Wenn die Heuristik konstant ist, erhalten Sie einen einfachen Dijkstra-Algorithmus. Wenn die Heuristik die tatsächlichen Kosten für das Ziel berechnet, folgen Sie nur dem kürzesten Pfad, und es werden keine anderen Knoten untersucht.