Ein* Suchalgorithmus

Klasse Suchalgorithmus
Datenstruktur Graph
Schlimmsten Fall Leistung
Schlimmsten Fall Raumkomplexität

EIN* (ausgesprochen "a-star") ist a Graph Traversal und Pfadsuche Algorithmus, der häufig in vielen Bereichen der Informatik aufgrund seiner Vollständigkeit, Optimalität und optimalen Effizienz verwendet wird.[1] Ein wichtiger praktischer Nachteil ist sein Raumkomplexität, da sie alle erzeugten Knoten im Speicher speichert. So in praktisch ReisungssystemeEs wird im Allgemeinen von Algorithmen übertroffen, die das Diagramm vorbereiten können, um eine bessere Leistung zu erzielen.[2] sowie erinnerungsreste Ansätze; A* ist jedoch in vielen Fällen immer noch die beste Lösung.[3]

Peter Hart, Nils Nilsson und Bertram Raphael des Stanford Research Institute (jetzt SRI International) veröffentlichte 1968 den Algorithmus.[4] Es kann als Erweiterung von gesehen werden Dijkstra -Algorithmus. A* erzielt eine bessere Leistung durch Verwendung Heuristik seine Suche leiten.

Im Vergleich zum Algorithmus von Dijkstra findet der A* -Algorithmus nur den kürzesten Weg von einer bestimmten Quelle zu einem bestimmten Ziel und nicht den kürzesten Pfadbaum von einer bestimmten Quelle zu allen möglichen Zielen. Dies ist ein notwendiger Kompromiss für die Verwendung einer spezifischen Heizung. Für den Algorithmus von Dijkstra ist jeder Knoten ein Ziel, da der gesamte Baumpfundbaum erzeugt wird, und es kann keine Heuristik mit spezifischem Tor geben.

Geschichte

A* wurde von Forschern erfunden, die an Shakey The Roboter's Pfadplanung arbeiteten.

A* wurde als Teil von erstellt Das Shakey -Projekt, was das Ziel hatte, einen mobilen Roboter aufzubauen, der seine eigenen Handlungen planen konnte. Nils Nilsson hat ursprünglich mit dem Graph Traverser -Algorithmus vorgeschlagen[5] Für Shakey's Pfadplanung.[6] Graph Traverser wird von einer heuristischen Funktion geleitet h(n), der geschätzte Abstand vom Knoten n zum Zielknoten: es ignoriert völlig ignoriert g(n), der Abstand vom Startknoten nach n. Bertram Raphael schlug die Summe vor, g(n) + h(n).[6] Peter Hart erfand die Konzepte, die wir jetzt nennen, Zulässigkeit und Konsistenz von heuristischen Funktionen. A* wurde ursprünglich für die Suche nach den am wenigsten günstigen Pfaden entwickelt, wenn die Kosten eines Pfades die Summe seiner Kosten sind. Es wurde jedoch gezeigt, dass A* verwendet werden kann, um optimale Pfade für jedes Problem zu finden, das die Bedingungen einer Kostenalgebra erfüllt.[7]

Das ursprüngliche Papier von 1968 A*[4] enthielt einen Theorem, der angibt, dass kein A*-ähnlicher Algorithmus[a] Könnte weniger Knoten als eine* erweitern, wenn die heuristische Funktion konsistent ist und eine Bindungsregel von A* angemessen ausgewählt wird. Eine "Korrektur" wurde einige Jahre später veröffentlicht[8] Es wurde behauptet, dass keine Konsistenz erforderlich sei, aber dies wurde in DeChter und Pearls endgültiges Studium der Optimalität von A* als falsch erwiesen (jetzt als optimaler Effizienz bezeichnet), was ein Beispiel für A* mit einer Heuristik ergab willkürlich mehr Knoten als ein alternativer A*-ähnlicher Algorithmus.[9]

Beschreibung

Ein* Pfadfindungsalgorithmus, der durch ein zufällig erzeugtes Labyrinth navigiert
Illustration einer* Suche nach einem Pfad zwischen zwei Punkten in einem Diagramm.

A* ist ein Informierter Suchalgorithmus, oder ein Best-First-Suche, was bedeutet, dass es in Bezug auf formuliert ist gewichtete Grafiken: Ausgehend von einem bestimmten Start Knoten Von einer Grafik soll ein Weg zum angegebenen Zielknoten mit den geringsten Kosten (am wenigsten zurückgelegte, kürzeste Zeit usw.) finden. Dies geschieht, indem es a beibehält Baum von Pfaden, die am Startknoten stammen und diese Pfade jeweils um eine Kante erweitern, bis das Beendigungkriterium erfüllt ist.

Bei jeder Iteration seiner Hauptschleife muss A* bestimmen, welcher seiner Wege sich verlängern soll. Dies basiert auf den Kosten des Pfades und einer Schätzung der Kosten, die erforderlich sind, um den Pfad bis zum Ziel zu erweitern. Insbesondere wählt a* den Pfad aus, der minimiert

wo n ist der nächste Knoten auf dem Pfad, g(n) sind die Kosten des Pfades vom Startknoten nach n, und h(n) ist ein Heuristik Funktion, die die Kosten des billigsten Weges von schätzt n zum Ziel. Ein* endet, wenn der Weg, den er verlängert, ein Weg von Anfang zu Ziel ist oder ob keine Wege zur Verlängerung berechtigt sind. Die heuristische Funktion ist problemspezifisch. Wenn die heuristische Funktion ist zulässig -Dies bedeutet, dass es die tatsächlichen Kosten für das Ziel nie überschätzt. Es wird garantiert, dass A* vom Anfang bis zum Ziel den am wenigsten günstigen Pfad zurückgibt.

Typische Implementierungen von a* verwenden a Prioritätswarteschlange Um die wiederholte Auswahl der minimalen (geschätzten) Kostenknoten zur Erweiterung durchzuführen. Diese vorrangige Warteschlange ist als die bekannt als die Open Set oder Randbereich. Bei jedem Schritt des Algorithmus den Knoten mit dem niedrigsten f(x) Der Wert wird aus der Warteschlange entfernt, die f und g Die Werte seiner Nachbarn werden entsprechend aktualisiert, und diese Nachbarn werden der Warteschlange hinzugefügt. Der Algorithmus wird bis zum entfernten Knoten fortgesetzt (somit der Knoten mit dem niedrigsten f Wert aus allen Randknoten) ist ein Zielknoten.[b] Das f Der Wert dieses Ziels ist dann auch die Kosten des kürzesten Weges seitdem h Am Ziel ist Null in einer zulässigen Heuristik.

Der bisher beschriebene Algorithmus gibt uns nur die Länge des kürzesten Weges. Um die tatsächliche Abfolge von Schritten zu finden, kann der Algorithmus leicht überarbeitet werden, so dass jeder Knoten auf dem Pfad seinen Vorgänger im Auge behält. Nachdem dieser Algorithmus ausgeführt wurde, verweist der Endknoten auf seinen Vorgänger und so weiter, bis der Vorgänger eines Knotens der Startknoten ist.

Beispielsweise bei der Suche nach der kürzesten Route auf einer Karte, h(x) könnte die darstellen Gerade Entfernung zum Ziel, da dies physisch der kleinstmögliche Abstand zwischen zwei Punkten ist. Für eine Rasterkarte aus einem Videospiel mit dem Manhattan -Entfernung oder die oktile Entfernung wird je nach den verfügbaren Bewegungen (4-Wege oder 8-Wege) besser.

Wenn die Heuristik h erfüllt den zusätzlichen Zustand h(x) ≤ d(x, y) + h(y) Für jede Kante (x, y) der Grafik (wo d bezeichnet die Länge dieser Kante), dann h wird genannt monoton oder konsequent. Mit einer konsistenten Heuristik findet A* garantiert einen optimalen Pfad, ohne einen Knoten mehr als einmal zu verarbeiten, und A* entspricht dem Laufen Dijkstra -Algorithmus mit dem reduzierte Kosten d'(x, y) = d(x, y) + h(y) - h(x).

Pseudocode

Folgende Pseudocode beschreibt den Algorithmus:

Funktion reconstruct_path(kam aus, aktuell)  Total_Path : = {aktuell}  während aktuell in kam aus.Schlüssel:  aktuell : = kam aus[aktuell]  Total_Path.vorbereiten(aktuell)  Rückkehr Total_Path // a* findet einen Weg von Anfang zum Ziel. // H ist die heuristische Funktion. H (n) schätzt die Kosten, um das Ziel vom Knoten n zu erreichen. Funktion Ein Stern(Anfang, Tor, h)  // Der Satz entdeckter Knoten, die möglicherweise (wieder) erweitert werden müssen.  // Zunächst ist nur der Startknoten bekannt.  // Dies wird in der Regel eher als Hash-Set als Miner-Heap- oder Prioritätswarteschlange implementiert.  OpenSet : = {Anfang}  // Für den Knoten N ist von Anfang an der Knoten unmittelbar vor ihm auf dem billigsten Weg von Anfang  // zu n derzeit bekannt.  kam aus : = ein leer Karte  // für Knoten N ist GSCORE [N] die Kosten des billigsten Pfades von Anfang bis N, der derzeit bekannt ist.  GSCORE : = Karte mit Ursprünglich Wert von Unendlichkeit  GSCORE[Anfang] : = 0  // für Knoten N, FSCORE [N]: = GSCORE [N] + H (N). fScore [n] repräsentiert unsere aktuelle beste Vermutung in Bezug auf  // Wie billig kann ein Weg von Anfang bis Ende sein, wenn er durch n geht.  fscore : = Karte mit Ursprünglich Wert von Unendlichkeit  fscore[Anfang] : = h(Anfang)  während OpenSet ist nicht leer  // Dieser Vorgang kann in O (log (n)) auftreten, wenn OpenSet ein Min-HEAP oder eine Prioritätswarteschlange ist  aktuell : = das Knoten in OpenSet haben das niedrigste fscore[] Wert  wenn aktuell = Tor  Rückkehr reconstruct_path(kam aus, aktuell)  OpenSet.Entfernen(aktuell)  zum jeder Nachbar von aktuell  // D (Strom, Nachbar) ist das Gewicht der Kante von Strom zum Nachbarn  // Tentative_gscore ist die Entfernung vom Start zum Nachbarn über Strom  Tentative_gscore : = GSCORE[aktuell] + d(aktuell, Nachbar)  wenn Tentative_gscore < GSCORE[Nachbar]  // Dieser Weg zum Nachbarn ist besser als jeder vorherige. Nimm es auf!  kam aus[Nachbar] : = aktuell  GSCORE[Nachbar] : = Tentative_gscore  fscore[Nachbar] : = Tentative_gscore + h(Nachbar)  wenn Nachbar nicht in OpenSet  OpenSet.hinzufügen(Nachbar)  // Open Set ist leer, aber das Ziel wurde nie erreicht  Rückkehr Versagen 

Anmerkung: In diesem Pseudocode wird ein Knoten, wenn ein Knoten von einem Pfad erreicht, aus OpenSet entfernt und anschließend von einem billigeren Pfad erreicht wird, erneut zu OpenSet hinzugefügt. Dies ist wichtig zu garantieren, dass der zurückgegebene Weg optimal ist, wenn die heuristische Funktion ist zulässig aber nicht konsistent. Wenn die Heuristik konsistent ist und ein Knoten aus OpenSet entfernt wird, ist der Weg dazu garantiert optimal, sodass der Test „Tentative_gscore <gScore [Nachbar]“ immer fehlschlägt, wenn der Knoten erneut erreicht wird.

Illustration einer* Suche nach dem Finden von Pfad von einem Startknoten zu einem Zielknoten in a Roboter Bewegungsplanung Problem. Die leeren Kreise repräsentieren die Knoten in der Open Set, d.h. Die Farbe an jedem geschlossenen Knoten zeigt den Abstand vom Ziel an: Je grüner, je näher. Man kann zuerst sehen, dass sich das A* in einer geraden Linie in Richtung des Ziels bewegt. Wenn Sie das Hindernis treffen, werden alternative Routen durch die Knoten aus dem offenen Satz untersucht.


Beispiel

Ein Beispiel für einen A* -Algorithmus in Aktion, bei dem Knoten mit Straßen und H (x) Städte sind, ist die geradlinige Entfernung zum Zielpunkt:

An example of A* algorithm in action (nodes are cities connected with roads, h(x) is the straight-line distance to target point) Green: Start, Blue: Target, Orange: Visited

Taste: Grün: Start; Blau: Ziel; Orange: Besucht

Der A* -Algorithmus hat auch reale Anwendungen. In diesem Beispiel sind Kanten Eisenbahnen und H (x) ist das Großkreisentfernung (Die kürzeste Entfernung auf einer Kugel) zum Ziel. Der Algorithmus sucht nach einem Weg zwischen Washington, DC und Los Angeles.

The A* algorithm finding a path of railroads between Washington, D.C. and Los Angeles.

Implementierungsdetails

Es gibt eine Reihe einfacher Optimierungen oder Implementierungsdetails, die die Leistung einer A* Implementierung erheblich beeinflussen können. Das erste Detail ist, dass die Art und Weise, wie die Prioritätswarteschlange miteinander umgeht, in einigen Situationen einen signifikanten Einfluss auf die Leistung haben kann. Wenn Krawatten gebrochen sind, so verhält sich die Warteschlange in a LIFO Art, ein* wird sich verhalten wie Tiefe-First-Suche Unter den gleichen Kostenpfaden (Vermeidung von mehr als einer gleichermaßen optimalen Lösung).

Wenn am Ende der Suche ein Pfad erforderlich ist, ist es üblich, mit jedem Knoten eine Referenz auf das übergeordnete Knoten zu halten. Am Ende der Suche können diese Referenzen verwendet werden, um den optimalen Pfad wiederherzustellen. Wenn diese Referenzen aufbewahrt werden, kann es wichtig sein, dass derselbe Knoten in der Prioritätswarteschlange nicht mehr als einmal erscheint (jeder Eintrag entspricht einem anderen Pfad als dem Knoten und jeweils mit anderen Kosten). Ein Standardansatz besteht darin, zu überprüfen, ob ein Knoten bereits in der Prioritätswarteschlange angezeigt wird. Wenn dies der Fall ist, werden die Prioritäts- und Elternzeiger geändert, um dem niedrigeren Kostenpfad zu entsprechen. Ein Standard Binärhaufen Die basierte Prioritätswarteschlange unterstützt den Betrieb der Suche nach einem seiner Elemente nicht direkt, kann aber mit a verstärkt werden Hash-tabelle Das ordnet Elemente ihrer Position im Haufen zu und ermöglicht es, dass dieser Abnahme-Prioritätsbetrieb in logarithmischer Zeit durchgeführt wird. Alternativ a Fibonacci Heap kann konstant die gleichen Abnahmeprioritätsoperationen durchführen abgeschriebene Zeit.

Spezialfälle

Dijkstra -Algorithmus, als ein weiteres Beispiel für einen einheitlichen Kosten-Suchalgorithmus kann als Sonderfall eines* wo angesehen werden für alle x.[10][11] Allgemein Tiefe-First-Suche kann mit a* implementiert werden, indem er bedenkt, dass es einen globalen Zähler gibt C mit einem sehr großen Wert initialisiert. Jedes Mal, wenn wir einen Knoten verarbeiten, weisen wir zu C an all seine neu entdeckten Nachbarn. Nach jeder einzelnen Zuordnung verringern wir den Zähler C einzeln. Je früher ein Knoten entdeckt wird, desto höher ist es Wert. Sowohl der Algorithmus von Dijkstra als auch die Tiefe-First-Suche können effizienter implementiert werden, ohne ein einzuführen Wert bei jedem Knoten.

Eigenschaften

Kündigung und Vollständigkeit

Bei endlichen Graphen mit nicht negativen Kantengewichten wird a* garantiert enden und ist Komplett, d. H. Es wird immer eine Lösung finden (von Anfang bis Ziel), wenn es existiert. Bei unendlichen Graphen mit einem endlichen Verzweigungsfaktor und den Kantenkosten, die von Null entfernt sind ( für einige fest ), A* wird garantiert nur dann enden, wenn es eine Lösung gibt.[1]

Zulässigkeit

Ein Suchalgorithmus soll sein zulässig Wenn garantiert eine optimale Lösung zurückgibt. Wenn die von A* verwendete heuristische Funktion zulässigdann ist a* zulässig. Ein intuitives "Proof" davon ist wie folgt:

Wenn eine* Suche eine Suche beendet, hat es von Anfang an einen Pfad gefunden Wert). Wenn die Heuristik zulässig ist, sind diese Schätzungen optimistisch (nicht ganz - siehe den nächsten Absatz), sodass A* diese Knoten sicher ignorieren kann, weil sie unmöglich zu einer billigeren Lösung führen können als die, die sie bereits hat. Mit anderen Worten, ein* wird niemals die Möglichkeit eines niedrigeren Pfadweges von Anfang bis Ziel übersehen und so weiter suchen, bis keine solchen Möglichkeiten bestehen.

Der tatsächliche Beweis ist ein bisschen besser umgegangen, weil die Werte offener Knoten sind nicht garantiert optimistisch, selbst wenn die Heuristik zulässig ist. Das liegt daran, dass die Die Werte offener Knoten sind nicht garantiert optimal, also die Summe ist nicht garantiert optimistisch.

Optimalität und Konsistenz

Algorithmus A ist in Bezug auf eine Reihe alternativer Algorithmen optimal effizient Alten Bei einer Reihe von Problemen P Wenn für jedes Problem P in P und jeder Algorithmus a 'in AltenDie durch A bei der Lösung p erweiterte Knotenmenge ist eine Untergruppe (möglicherweise gleich) des Satzes von Knoten, die durch A 'bei der Lösung von P erweitert werden. Die endgültige Untersuchung der optimalen Effizienz von A* ist auf Rina DeChter und Judea Pearl zurückzuführen.[9] Sie betrachteten eine Vielzahl von Definitionen von Alten und P in Kombination mit einem heuristischen Wesen von nur zulässig oder beides sein konsistent und zulässig. Das interessanteste positive Ergebnis, das sie bewiesen haben, ist, dass A*mit einer konsistenten Heuristik in Bezug auf alle zulässigen A*-ähnlichen Suchalgorithmen auf allen "nicht pathologischen" Suchproblemen optimal effizient ist. Grob gesagt, ihre Vorstellung von nicht pathologischem Problem ist das, was wir jetzt mit "bis zum Binden" meinen. Dieses Ergebnis gilt nicht, wenn eine Heuristik von A*zulässig ist, aber nicht konsistent. In diesem Fall zeigten DeChter und Pearl, dass es zulässige A*-ähnliche Algorithmen gibt, die bei einigen nicht pathologischen Problemen willkürlich weniger Knoten als ein* erweitern können.

Bei optimaler Effizienz geht es um die einstellen von Knoten erweitert, nicht die Nummer von Knotenausdehnungen (die Anzahl der Iterationen von A*'s Hauptschleife). Wenn das verwendete Heuristik zulässig, aber nicht konsistent ist, ist es möglich, dass ein Knoten im schlimmsten Fall eine Exponentialzahl um ein* um ein* um ein* erweitert wird.[12] Unter solchen Umständen könnte Dijkstras Algorithmus einen großen Rand übertreffen. Neuere Untersuchungen ergaben jedoch, dass dieser pathologische Fall nur in bestimmten erfundenen Situationen auftritt, in denen das Kantengewicht des Suchdiagramms in der Größe des Diagramms exponentiell ist und dass bestimmte inkonsistente (aber zulässige) Heuristiken zu einer reduzierten Anzahl von Knoten führen können Erweiterungen in einem* Suchanfragen.[13][14]

Begrenzte Entspannung

Eine* Suche, die eine Heuristik verwendet, die 5,0 (= ε) mal a ist konsequent heuristischund erhält einen suboptimalen Weg.

Während das Zulässigkeitskriterium einen optimalen Lösungsweg garantiert, bedeutet dies auch, dass A* alle gleichwertigen Pfade untersuchen muss, um den optimalen Pfad zu finden. Um ungefähre kürzeste Wege zu berechnen, ist es möglich, die Suche auf Kosten der Optimalität zu beschleunigen, indem das Zulässigkeitskriterium gelockert wird. Oft wollen wir diese Entspannung gebunden, damit wir garantieren können, dass der Lösungsweg nicht schlechter ist als (1 + ε) mal den optimalen Lösungsweg. Diese neue Garantie wird als bezeichnet als ε-zulässig.

Es gibt eine Reihe von ε-Abulbare Algorithmen:

  • Gewichtete A*/statische Gewichtung.[15] Wenn ha(n) ist eine zulässige heuristische Funktion in der gewichteten Version der A* -Suche, die man verwendet hw(n) = ε ha(n), ε > 1 als heuristische Funktion und die a* suche wie gewohn ha Da sind weniger Knoten erweitert). Der vom Suchalgorithmus gefundene Weg kann höchstens Kosten von höchsten ε mal das des am wenigsten Kostenpfads in der Grafik.[16]
  • Dynamische Gewichtung[17] Verwendet die Kostenfunktion , wo , und wo ist die Tiefe der Suche und N ist die erwartete Länge des Lösungswegs.
  • Abgetastete dynamische Gewichtung[18] Verwendet die Stichprobe von Knoten, um den heuristischen Fehler besser abzuschätzen und zu debiieren.
  • .[19] Verwendet zwei heuristische Funktionen. Die erste ist die Fokusliste, mit der Kandidatenknoten ausgewählt werden können, und die zweite hF wird verwendet, um den vielversprechendsten Knoten aus der Fokusliste auszuwählen.
  • Aε[20] Wählt Knoten mit der Funktion aus , wo A und B sind Konstanten. Wenn keine Knoten ausgewählt werden können, wird der Algorithmus mit der Funktion zurückverfolgen , wo C und D sind Konstanten.
  • Alpha*[21] Versuche zur Förderung der Tiefe-First-Ausbeutung, indem sie kürzlich erweiterte Knoten bevorzugen. Alpha* verwendet die Kostenfunktion , wo , wo λ und Λ sind Konstanten mit , π(n) ist der Elternteil von n, und ñ ist der zuletzt erweiterte Knoten.

Komplexität

Das Zeitkomplexität von a* hängt von der Heuristik ab. Im schlimmsten Fall eines unbegrenzten Suchraums ist die Anzahl der erweiterten Knoten exponentiell in der Tiefe der Lösung (der kürzeste Weg) d: O(bd), wo b ist der Verzweigungsfaktor (Die durchschnittliche Anzahl der Nachfolger pro Staat).[22] Dies setzt voraus, dass überhaupt ein Zielstaat existiert und ist erreichbar vom Startzustand; Wenn dies nicht der Fall ist und der Zustandsraum unendlich ist, endet der Algorithmus nicht.

Die heuristische Funktion hat einen großen Einfluss auf die praktische Leistung einer* Suche bd Knoten, die eine nicht informierte Suche erweitern würden. Seine Qualität kann in Bezug auf die ausgedrückt werden Wirksam Verzweigungsfaktor b*, die für eine Probleminstanz empirisch bestimmt werden kann, indem die Anzahl der durch Expansion generierten Knoten gemessen wird, Nund die Tiefe der Lösung, dann lösen[23]

Gute Heuristiken sind diejenigen mit niedrigem effektivem Verzweigungsfaktor (das optimale Wesen b* = 1).

Die Zeitkomplexität ist Polynom Wenn der Suchraum ein Baum ist, gibt es einen einzelnen Zielzustand und die heuristische Funktion h erfüllt die folgende Bedingung:

wo h* ist die optimale Heuristik, die genauen Kosten, von denen man bekommen muss x zum Ziel. Mit anderen Worten, der Fehler von h wird nicht schneller wachsen als die Logarithmus der "perfekten Heuristik" h* Das gibt die wahre Entfernung von zurück x zum Ziel.[16][22]

Das Raumkomplexität von a* ist ungefähr das gleiche wie das aller anderen Diagramm -Suchalgorithmen, da es alle erzeugten Knoten im Speicher hält.[1] In der Praxis stellt sich heraus Iterative Vertiefung a*, Gedächtnis begrenzt a*und SMA*.

Anwendungen

A* wird oft für das Gemeinsame verwendet Wegfindung Problem in Anwendungen wie Videospielen, wurde jedoch ursprünglich als allgemeiner Graph -Traversal -Algorithmus entwickelt.[4] Es findet Anwendungen in verschiedenen Problemen, einschließlich des Problems von Parsing Verwendung Stochastische Grammatiken in NLP.[24] Andere Fälle umfassen eine Informationssuche mit Online -Lernen.[25]

Beziehungen zu anderen Algorithmen

Was unterscheidet ein* von a gierig Der Best-First-Suchalgorithmus ist, dass die bereits befahrenen Kosten/Entfernungen erforderlich sind. g(n), berücksichtigt.

Einige gemeinsame Varianten von Dijkstra -Algorithmus kann als Sonderfall von a* angesehen werden, wo die Heuristik für alle Knoten;[10][11] wiederum sind sowohl Dijkstra als auch a* besondere Fälle von Dynamische Programmierung.[26] A* selbst ist ein Sonderfall einer Verallgemeinerung von Zweig und gebunden.[27]

Varianten

A* kann auch an a angepasst werden Bidirektionale Suche Algorithmus. Für das Stoppkriterium muss besondere Sorgfalt berücksichtigt werden.[31]

Siehe auch

Anmerkungen

  1. ^ "A* -Like" bezeichnet die Algorithmus-Suche, indem sie Wege, die an der Startknoten nacheinander stammen, nur wie ein* ausdehnen. Dies schließt beispielsweise Algorithmen aus, die gleichzeitig vom Ziel oder in beide Richtungen nach hinten suchen. Darüber hinaus müssen die von diesem Satz abgedeckten Algorithmen zulässig und „nicht informierter“ sein als ein*.
  2. ^ Zielknoten können mehrfach übertroffen werden, wenn andere Knoten mit niedrigeren bestehen bleiben f Werte, wie sie zu einem kürzeren Weg zu einem Ziel führen können.

Verweise

  1. ^ a b c Russell, Stuart J. (2018). Künstliche Intelligenz Ein moderner Ansatz. Norvig, Peter (4. Aufl.). Boston: Pearson. ISBN 978-0134610993. OCLC 1021874142.
  2. ^ Delling, D.; Sanders, P.; Schulte, D.; Wagner, D. (2009). "Algorithmen für technische Routenplanung". Algorithmik großer und komplexer Netzwerke: Design, Analyse und Simulation. Vorlesungsnotizen in Informatik. Vol. 5515. Springer. S. 11 个 $ 7–139. Citeseerx 10.1.1.164.8916. doi:10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
  3. ^ Zeng, W.; Church, R. L. (2009). "Kürzeste Wege in echten Straßennetzwerken finden: Der Fall für a*". Internationales Journal of Geographical Information Science. 23 (4): 531–543. doi:10.1080/13658810801949850. S2CID 14833639.
  4. ^ a b c Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "Eine formale Grundlage für die heuristische Bestimmung der Mindestkostenwege". IEEE -Transaktionen zu Systemwissenschaft und Kybernetik. 4 (2): 100–107. doi:10.1109/tssc.1968.300136.
  5. ^ Doran, J. E.; Michie, D. (1966-09-20). "Experimente mit dem Graph Traverser -Programm". Proc. R. Soc. Lond. EIN. 294 (1437): 235–259. Bibcode:1966RSPSA.294..235d. doi:10.1098/rspa.1966.0205. ISSN 0080-4630. S2CID 21698093.
  6. ^ a b Nilsson, Nils J. (2009-10-30). Die Suche nach künstlicher Intelligenz (PDF). Cambridge: Cambridge University Press. ISBN 9780521122931.
  7. ^ Edelkamp, ​​Stefan; Jabbar, Shahid; Lluch-Lafuente, Alberto (2005). "Cost-algebraische heuristische Suche" (PDF). Proceedings der zwanzigsten nationalen Konferenz über künstliche Intelligenz (AAAI): 1362–1367.
  8. ^ Hart, Peter E.; Nilsson, Nils J.; Raphael, Bertram (1972-12-01). "Korrektur auf eine formale Grundlage für die heuristische Bestimmung der Mindestkostenwege"" (PDF). ACM Sigart Bulletin (37): 28–29. doi:10.1145/1056777.1056779. ISSN 0163-5719. S2CID 6386648.
  9. ^ a b Decher, Rina; Juda Pearl (1985). "Generalisierte Best-First-Suchstrategien und die Optimalität eines*". Journal of the ACM. 32 (3): 505–536. doi:10.1145/3828.3830. S2CID 2092415.
  10. ^ a b De Smith, Michael John; Goodchild, Michael F.; Longley, Paul (2007), Geospatial Analysis: Ein umfassender Leitfaden zu Prinzipien, Techniken und Softwaretools, Troubadour Publishing Ltd, p. 344, ISBN 9781905886609.
  11. ^ a b Hetland, Magnus Lie (2010), Python -Algorithmen: Mastering grundlegende Algorithmen in der Python -Sprache, Apress, p. 214, ISBN 9781430232377.
  12. ^ Martelli, Alberto (1977). "Über die Komplexität zulässiger Suchalgorithmen". Künstliche Intelligenz. 8 (1): 1–13. doi:10.1016/0004-3702 (77) 90002-9.
  13. ^ Felner, Ariel; Uzi Zahavi (2011). "Inkonsistente Heuristiken in Theorie und Praxis". Künstliche Intelligenz. 175 (9–10): 1570–1603. doi:10.1016/j.artint.2011.02.001.
  14. ^ Zhang, Zhifu; N. R. Sturtevant (2009). Verwendung inkonsistenter Heuristiken bei einer* Suche. Einundzwanzigste internationale gemeinsame Konferenz über künstliche Intelligenz.
  15. ^ Pohl, Ira (1970). "Erste Ergebnisse zum Effekt des Fehlers bei der heuristischen Suche". Maschineninformation. 5: 219–236.
  16. ^ a b Pearl, Judäa (1984). Heuristik: Intelligente Suchstrategien zur Lösung von Computerproblemen. Addison-Wesley. ISBN 978-0-201-05594-8.
  17. ^ Pohl, IRA (August 1973). "Die Vermeidung von (relativer) Katastrophe, heuristische Kompetenz, echte dynamische Gewichtung und Rechenprobleme bei heuristischer Problemlösung" (PDF). Proceedings der dritten internationalen gemeinsamen Konferenz über künstliche Intelligenz (IJCAI-73). Vol. 3. Kalifornien, USA. S. 11–17.
  18. ^ Köll, Andreas; Hermann Kaindl (August 1992). "Ein neuer Ansatz zur dynamischen Gewichtung". Verfahren der zehnten Europäischen Konferenz über künstliche Intelligenz (ECAI-92). Wien, Österreich. S. 16–17.
  19. ^ Perle, Judäa; Jin H. Kim (1982). "Studien an semi-ordnungsvoller Heuristik". IEEE -Transaktionen zur Musteranalyse und Maschinenintelligenz. 4 (4): 392–399. doi:10.1109/tpami.1982.4767270. PMID 21869053. S2CID 3176931.
  20. ^ Ghallab, Malik; Dennis Allard (August 1983). "Aε - Ein effizienter nahezu zulässiger heuristischer Suchalgorithmus " (PDF). Proceedings der achten internationalen gemeinsamen Konferenz über künstliche Intelligenz (IJCAI-83). Vol. 2. Karlsruhe, Deutschland. S. 789–791. Archiviert von das Original (PDF) Am 2014-08-06.
  21. ^ Reese, Bjørn (1999). Alpha*: ein ε-Alliger heuristischer Suchalgorithmus (Bericht). Archiviert von das Original Am 2016-01-31. Abgerufen 2014-11-05.
  22. ^ a b Russell, Stuart; Norvig, Peter (2003) [1995]. Künstliche Intelligenz: ein moderner Ansatz (2. Aufl.). Prentice Hall. S. 97–104. ISBN 978-0137903955.
  23. ^ Russell, Stuart; Norvig, Peter (2009) [1995]. Künstliche Intelligenz: ein moderner Ansatz (3. Aufl.). Prentice Hall. p. 103. ISBN 978-0-13-604259-4.
  24. ^ Klein, Dan; Manning, Christopher D. (2003). A* Parsing: Schnell genau Viterbi Parse Selection. Proc. NAACl-HLT.
  25. ^ Kagan E.; Ben-Gal I. (2014). "Ein Gruppentest-Algorithmus mit Online-Informationslernen" (PDF). Iie Transaktionen. 46 (2): 164–184. doi:10.1080/0740817X.2013.803639. S2CID 18588494.
  26. ^ Ferguson, Dave; Likhachev, Maxim; Stentz, Anthony (2005). Ein Leitfaden zur heuristischen Pfadplanung (PDF). Proc. ICAPS -Workshop für Planung unter Unsicherheit für autonome Systeme.
  27. ^ Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). "Allgemeiner Zweig und gebunden und seine Beziehung zu einem ∗ und ao ∗" (PDF). Künstliche Intelligenz. 23 (1): 29–58. doi:10.1016/0004-3702 (84) 90004-3.
  28. ^ Hansen, Eric A. und Rong Zhou. "Jederzeit heuristische Suche. Archiviert 2016-11-05 bei der Wayback -Maschine"J. Artif. Intell. Res. (Jair) 28 (2007): 267-297.
  29. ^ Fareeh, Raouf; Baziyad, Mohammed; Rahman, Mohammad H.; Rabie, Tamer; Bettayeb, Maamar (2019-05-14). "Untersuchung der Strategie zur reduzierten Pfadplanung für differentielle mobile Roboter" Differential Rad "". Roboter. 38 (2): 235–255. doi:10.1017/s0263574719000572. ISSN 0263-5747. S2CID 181849209.
  30. ^ Pijls, Wim; Post, Henk "Ein weiterer bidirektionaler Algorithmus für kürzeste Wege" Im Econometric Institute Report EI 2009-10/Econometric Institute, Erasmus University Rotterdam. Erasmus School of Economics.
  31. ^ Goldberg, Andrew V.; Harrelson, Chris; Kaplan, Haim; Werneck, Renato F. "Effiziente Point-to-Point-kürzeste Pfadalgorithmen" (PDF). Princeton Universität. Archiviert (PDF) vom Original am 18. Mai 2022.

Weitere Lektüre

Externe Links