In der Informatik ist A* (ausgesprochen "Ein Stern") ein Computeralgorithmus, der in pathfinding und Graph-Traversal, dem Prozess weit verwendet wird, einen effizient überquerbaren Pfad zwischen Punkten, genannt Knoten zu planen. Bemerkt für seine Leistung und Genauigkeit genießt es weit verbreiteten Gebrauch. Peter Hart, Nils Nilsson und Bertram Raphael haben zuerst den Algorithmus 1968 beschrieben. Es ist eine Erweiterung des 1959-Algorithmus von Edsger Dijkstra. A* erreicht bessere Leistung (in Bezug auf die Zeit) durch das Verwenden der Heuristik.

Beschreibung

A* verwendet eine beste erste Suche und findet einen am wenigsten gekosteten Pfad von einem gegebenen anfänglichen Knoten bis einen Absicht-Knoten (aus einem oder möglicheren Absichten).

Es verwendet eine Entfernung plus die Kosten heuristische Funktion (gewöhnlich angezeigt), um die Ordnung zu bestimmen, in der die Suche Knoten im Baum besucht. Die heuristische Entfernung plus die Kosten ist eine Summe von zwei Funktionen:

• die Funktion der Pfad-gekosteten, die die Kosten vom Startknoten bis den aktuellen Knoten (gewöhnlich angezeigt) ist
• und eine zulässige "heuristische Schätzung" der Entfernung zur Absicht (gewöhnlich angezeigt).

Der Teil der Funktion muss ein zulässiger heuristischer sein; d. h. es muss die Entfernung zur Absicht nicht überschätzen. So, für eine Anwendung wie Routenplanung, könnte die lineare Entfernung zur Absicht vertreten, da das physisch die kleinstmögliche Entfernung zwischen irgendwelchen zwei Punkten oder Knoten ist.

Wenn der heuristische h die zusätzliche Bedingung für jeden Rand x, y vom Graphen befriedigt (wo d die Länge dieses Randes anzeigt), dann wird h Eintönigkeit, oder konsequent genannt. In solch einem Fall kann A* effizienter — grob das Sprechen durchgeführt werden, kein Knoten muss mehr bearbeitet werden als einmal (sieh geschlossenen Satz unten) — und A* ist zum Laufen des Algorithmus von Dijkstra mit den reduzierten Kosten gleichwertig.

Bemerken Sie, dass A* in einen bidirektionalen heuristischen Suchalgorithmus verallgemeinert worden ist; sieh bidirektionale Suche.

Geschichte

1964 hat Nils Nilsson eine heuristische basierte Annäherung erfunden, um die Geschwindigkeit des Algorithmus von Dijkstra zu vergrößern. Dieser Algorithmus wurde A1 genannt. 1967 hat Bertram Raphael dramatische Verbesserungen auf diesen Algorithmus gebildet, aber hat gescheitert, optimality zu zeigen. Er hat diesen Algorithmus A2 genannt. Dann 1968 hat Peter E. Hart ein Argument eingeführt, das bewiesen hat, dass A2 optimal war, als er einen konsequenten heuristischen mit nur geringen Änderungen verwendet hat. Sein Beweis des Algorithmus hat auch eine Abteilung eingeschlossen, die gezeigt hat, dass der neue A2 Algorithmus der beste Algorithmus möglich gegeben die Bedingungen war. Er hat so den neuen Algorithmus in der Sternsyntax von Kleene genannt, um der Algorithmus zu sein, der mit A anfängt und alle möglichen Versionsnummern oder A* einschließt.

Konzepte

Da A* den Graphen überquert, folgt er einem Pfad der niedrigsten bekannten Kosten, eine sortierte Vorzugswarteschlange von abwechselnden Pfad-Segmenten entlang dem Weg behaltend. Wenn, an einem Punkt, ein Segment des Pfads, der wird überquert, höhere Kosten hat als ein anderes gestoßenes Pfad-Segment, gibt es das höher gekostete Pfad-Segment auf und überquert das tiefer gekostete Pfad-Segment stattdessen. Dieser Prozess geht weiter, bis die Absicht erreicht wird.

Prozess

Wie alle informierten Suchalgorithmen sucht es zuerst die Wege, die scheinen, höchstwahrscheinlich zur Absicht zu führen. Was untergeht, ist A* abgesondert von einer gierigen besten ersten Suche, dass sie auch die Entfernung nimmt, bereits ist in die Rechnung gereist; der Teil des heuristischen ist die Kosten vom Startpunkt, nicht einfach die lokalen Kosten vom vorher ausgebreiteten Knoten.

Mit dem anfänglichen Knoten anfangend, unterstützt es eine Vorzugswarteschlange von zu überquerenden Knoten, als der offene Satz bekannt. Je tiefer für einen gegebenen Knoten, desto höher sein Vorrang. An jedem Schritt des Algorithmus wird der Knoten mit dem niedrigsten Wert von der Warteschlange, entfernt, und Werte seiner Nachbarn werden entsprechend aktualisiert, und diese Nachbarn werden zur Warteschlange hinzugefügt. Der Algorithmus geht weiter, bis ein Absicht-Knoten einen niedrigeren Wert hat als jeder Knoten in der Warteschlange (oder bis die Warteschlange leer ist). (Absicht-Knoten können mehrmals übertragen werden, wenn dort andere Knoten mit niedrigeren Werten bleiben, weil sie zu einem kürzeren Pfad zu einer Absicht führen können.) Der Wert der Absicht ist dann die Länge des kürzesten Pfads, da an der Absicht Null in einem zulässigen heuristischen ist. Wenn der wirkliche kürzeste Pfad gewünscht wird, kann der Algorithmus auch jeden Nachbar mit seinem unmittelbaren Vorgänger im besten Pfad gefunden bis jetzt aktualisieren; diese Information kann dann verwendet werden, um den Pfad durch das Arbeiten umgekehrt vom Absicht-Knoten wieder aufzubauen. Zusätzlich, wenn das heuristische monotonisch (oder konsequent ist, sieh unten), ein geschlossener Satz von bereits überquerten Knoten kann verwendet werden, um die Suche effizienter zu machen.

Pseudocode

Der folgende Pseudocode beschreibt den Algorithmus:

fungieren Sie * (Anfang, Absicht)

closedset: = der leere Satz//Der Satz von Knoten bereits bewertet.

openset: = {Anfang}//Der Satz von versuchsweisen Knoten, die zu bewerten sind, am Anfang den Anfang-Knoten enthaltend

came_from: = die leere Karte//Die Karte von befahrenen Knoten.

g_score [Anfang]: = 0//Kosten vom Anfang entlang dem am besten bekannten Pfad.

h_score [Anfang]: = heuristic_cost_estimate (Anfang, Absicht)

f_score [Anfang]: = g_score [Anfang] + h_score [Anfang]//Geschätzte Gesamtkosten vom Anfang bis Absicht durch y.

während openset nicht leerer ist

Strom: = der Knoten in openset den niedrigsten f_score [] zu haben, schätzen

wenn Strom = Absicht

geben Sie reconstruct_path (came_from, Absicht) zurück

entfernen Sie Strom von openset

fügen Sie Strom zu closedset hinzu

für jeden Nachbar in neighbor_nodes (Strom)

wenn Nachbar in closedset

setzen Sie fort

tentative_g_score: = g_score [Strom] + dist_between (Strom, Nachbar)

wenn Nachbar nicht in openset

fügen Sie Nachbar zu openset hinzu

h_score [Nachbar]: = heuristic_cost_estimate (Nachbar, Absicht)

tentative_is_better: = wahrer

sonst, wenn tentative_g_score

Bemerkung: Der obengenannte Pseudocode nimmt an, dass die heuristische Funktion monotonisch (oder konsequent ist, sieh unten), der ein häufiger Fall in vielen praktischen Problemen wie der Kürzeste Entfernungspfad in Straßennetzen ist. Jedoch, wenn die Annahme nicht wahr ist, können Knoten im geschlossenen Satz wieder entdeckt werden, und ihre Kosten verbessert.

Mit anderen Worten kann der geschlossene Satz weggelassen werden (das Nachgeben eines Baumsuchalgorithmus), wenn, wie man versichert, eine Lösung besteht, oder wenn der Algorithmus angepasst wird, so dass neue Knoten zum offenen Satz nur hinzugefügt werden, wenn sie einen niedrigeren Wert haben als bei einer vorheriger Wiederholung.

Beispiel

Ein Beispiel Ein Stern (*) Algorithmus in der Handlung, wo Knoten Städte sind, die mit Straßen und h (x) verbunden sind, ist die lineare Entfernung, um Punkt ins Visier zu nehmen:

Schlüssel: grün: Fangen Sie an; blau: Absicht; orange: besuchter

Zeichen: Dieses Beispiel verwendet ein Komma als die Trennung von Dezimalstellen.

Eigenschaften

Wie Breitensuche ist A* abgeschlossen und wird immer eine Lösung finden, wenn man besteht.

Wenn die heuristische Funktion zulässig ist, bedeutend, dass sie nie die wirklichen minimalen Kosten überschätzt, die Absicht zu erreichen, dann ist A* selbst zulässig (oder optimal), wenn wir keinen geschlossenen Satz verwenden. Wenn ein geschlossener Satz verwendet wird, auch dann monotonisch (oder konsequent sein muss) für A*, um optimal zu sein. Das bedeutet, dass für jedes Paar von angrenzenden Knoten und, wo die Länge des Randes zwischen ihnen anzeigt, wir haben müssen:

:

Das stellt dass für jeden Pfad vom anfänglichen Knoten sicher bis:

:

wo die Länge eines Pfads anzeigt, und der Pfad ist, der erweitert ist, um einzuschließen. Mit anderen Worten ist es unmöglich (Gesamtentfernung bis jetzt + geschätzte restliche Entfernung) durch das Verlängern eines Pfads abzunehmen, um einen benachbarten Knoten einzuschließen. (Das ist der Beschränkung zu nichtnegativen Rand-Gewichten im Algorithmus von Dijkstra analog.) bezieht Monomuskeltonus Annehmbarkeit ein, wenn die heuristische Schätzung auf jeden Absicht-Knoten selbst Null, seitdem (das Lassen ist, ein kürzester Pfad von jedem Knoten bis die nächste Absicht sein):

:

A* ist auch für irgendwelchen heuristisch optimal effizient, bedeutend, dass kein Algorithmus, der heuristisches dasselbe verwendet, weniger Knoten ausbreiten wird als *, außer, wenn es vielfache teilweise Lösungen gibt, wo genau die Kosten des optimalen Pfads voraussagt. Sogar in diesem Fall, für jeden Graphen dort besteht eine Ordnung, Bande im Vorrang zu brechen, steht solch Schlange, dass A* die geringstmöglichen Knoten untersucht.

Spezielle Fälle

Der Algorithmus von Dijkstra, als ein anderes Beispiel eines Suchalgorithmus des Uniform-gekosteten, kann als ein spezieller Fall von A* wo für alle angesehen werden. Allgemeine Tiefensuche kann mit A* durch das Denken durchgeführt werden, dass es einen globalen Schalter C initialisiert mit einem sehr großen Wert gibt. Jedes Mal, wenn wir einen Knoten bearbeiten, teilen wir C allen seinen kürzlich entdeckten Nachbarn zu. Nach jeder einzelnen Anweisung vermindern wir den Schalter C durch einen. So, je früher ein Knoten, desto höher sein Wert entdeckt wird. Es sollte jedoch bemerkt werden, dass sowohl der Algorithmus als auch Tiefensuche von Dijkstra effizienter ohne das Umfassen eines Werts an jedem Knoten durchgeführt werden können.

Durchführungsdetails

Es gibt mehrere einfache Optimierungen oder Durchführungsdetails, die die Leistung einer A* Durchführung bedeutsam betreffen können. Das erste Detail, um zu bemerken, ist, dass der Weg die Vorzugswarteschlange-Griff-Bande eine bedeutende Wirkung auf die Leistung in einigen Situationen haben kann. Wenn Bande so gebrochen werden, benimmt sich die Warteschlange auf eine LIFO Weise, A* wird sich wie Tiefensuche unter gleichen Kostenpfaden benehmen.

Wenn ein Pfad am Ende der Suche erforderlich ist, ist es üblich, mit jedem Knoten eine Verweisung auf den Elternteil dieses Knotens zu behalten. Am Ende der Suche können diese Verweisungen verwendet werden, um den optimalen Pfad wieder zu erlangen. Wenn diese Verweisungen dann behalten werden, kann es wichtig sein, dass derselbe Knoten in der Vorzugswarteschlange mehr nicht erscheint als einmal (jeder Zugang entsprechend einem verschiedenen Pfad zum Knoten und jedem mit verschiedenen Kosten). Eine Standardannäherung hier soll überprüfen, ob ein Knoten über, bereits hinzugefügt zu werden, in der Vorzugswarteschlange erscheint. Wenn es tut, dann werden der Vorrang und die Elternteilzeigestöcke geändert, um tiefer Kostenpfad zu entsprechen. Wenn sie einen Knoten in einer Warteschlange finden, diese Kontrolle durchzuführen, verlangen viele Standarddurchführungen eines Minute-Haufens Zeit. Das Vergrößern des Haufens mit einer Hash-Tabelle kann das auf die unveränderliche Zeit reduzieren.

Annehmbarkeit und optimality

A* ist zulässig und denkt weniger Knoten als jeder andere zulässige Suchalgorithmus mit heuristischem demselben. Das ist, weil A* eine "optimistische" Schätzung der Kosten eines Pfads durch jeden Knoten verwendet, dass es — optimistisch darin in Betracht zieht, werden die wahren Kosten eines Pfads durch diesen Knoten zur Absicht mindestens so groß sein wie die Schätzung. Aber, kritisch, so weit A* "weiß", dass optimistische Schätzung erreichbar sein könnte.

Hier ist die Hauptidee vom Beweis:

Wenn A* seine Suche begrenzt, hat es einen Pfad gefunden, dessen Ist-Kosten niedriger sind als die geschätzten Kosten jedes Pfads durch jeden offenen Knoten. Aber da jene Schätzungen optimistisch sind, kann A* jene Knoten sicher ignorieren. Mit anderen Worten wird A* die Möglichkeit eines tiefer gekosteten Pfads nie überblicken und ist zulässig auch.

Denken Sie, jetzt wo ein anderer Suchalgorithmus B seine Suche mit einem Pfad begrenzt, dessen Ist-Kosten nicht weniger sind als die geschätzten Kosten eines Pfads durch einen offenen Knoten. Gestützt auf der heuristischen Information hat es, Algorithmus B kann die Möglichkeit nicht ausschließen, dass ein Pfad durch diesen Knoten niedrigere Kosten hat. So, während B weniger Knoten denken könnte als *, kann es nicht zulässig sein. Entsprechend denkt A* wenigste Knoten jedes zulässigen Suchalgorithmus.

Das ist nur wenn beide wahr:

• A* verwendet einen zulässigen heuristischen. Sonst, wie man versichert, breitet A* weniger Knoten nicht aus als ein anderer Suchalgorithmus mit heuristischem demselben. Sieh (Verallgemeinert am besten die ersten Suchstrategien und der optimality *, Rina Dechter und Judea Pearl, 1985)
• A* behebt nur ein Suchproblem aber nicht eine Reihe von ähnlichen Suchproblemen. Sonst, wie man versichert, breitet A* weniger Knoten nicht aus als zusätzliche heuristische Suchalgorithmen. Sieh (Zusätzliche heuristische Suche in künstlicher Intelligenz, Sven Koenig, Maxim Likhachev, Yaxin Liu und David Furcy, 2004)

Belasteter A*

Belasteter A* ist eine Variante des A* Algorithmus, der eine Beschleunigung eine Suche auf Kosten von optimality lässt. Die Grundidee ist, einen zulässigen heuristischen "aufzublasen", um die Suche zu beschleunigen, und noch einen gebundenen der sub-optimality zu haben. Wenn eine zulässige heuristische Funktion ist, in der belasteten Version von der A* Suche verwendet man als die heuristische Funktion, und führen Sie die A* Suche wie gewöhnlich durch (der schließlich schneller geschieht als das Verwenden, da weniger Knoten ausgebreitet werden). Der durch den Suchalgorithmus folglich gefundene Pfad kann Kosten an die meisten Male diesem des kleinsten Kostenpfads im Graphen haben.

Kompliziertheit

Die Zeitkompliziertheit von A* hängt vom heuristischen ab. Im Grenzfall ist die Zahl von ausgebreiteten Knoten in der Länge der Lösung Exponential-(der kürzeste Pfad), aber es ist Polynom, wenn der Suchraum ein Baum ist, gibt es einen einzelnen Absicht-Staat, und die heuristische Funktion h entspricht die folgende Bedingung:

:

wo das optimale heuristische, die genauen Kosten ist, um von zur Absicht zu kommen. Mit anderen Worten wird der Fehler von h schneller nicht wachsen als der Logarithmus "vollkommen heuristisch", der die wahre Entfernung von x bis die Absicht zurückgibt (sieh Pearl 1984 und auch Russell und Norvig 2003, p. 101)

Varianten von A*

• D *
• D* Lite
• Feld D *
• IDA *
• Franse
• Fringe Saving A* (FSA *)
• Verallgemeinerter anpassungsfähiger A* (GAA *)
• Lebenslänglicher Planning A* (LPA *)
• SMA *
• Theta *

Links

• A* Pathfinding für Anfänger
• A* mit dem Sprung-Punkt sucht
• Klare SehA* Erklärung, mit dem Rat und den Gedanken auf der Pfad-Entdeckung
• Schwankung auf A* genannt Hierarchischer Path-Finding A* (HPA *)
• A* Algorithm Tutorenkurs