Die A-Suche ist das bekannteste heuristische Suchverfahren: Sie bewertet jeden Knoten mit der Summe aus bisherigen Kosten und geschätzten Restkosten* und expandiert stets den günstigsten. Mit einer zulässigen Heuristik findet sie garantiert die beste Lösung.
Jeder Knoten erhält den Wert f(n) = g(n) + h(n). Dabei ist g(n) der bisher zurückgelegte Weg — bekannt und exakt — und h(n) die geschätzte Restentfernung, geliefert von einer Heuristik. Die Summe schätzt die Gesamtkosten des besten Pfades durch diesen Knoten. Expandiert wird immer der Knoten mit dem kleinsten f-Wert.
Die Formel verbindet zwei bekannte Verfahren. Setzt man h auf null, bleibt allein g übrig: Das Verfahren wird zur uniformen Kostensuche und läuft blind in alle Richtungen. Beachtet man nur h und ignoriert g, entsteht die gierige Bestensuche — sie stürmt auf das Ziel zu, nimmt dabei aber Umwege in Kauf, weil sie den zurückgelegten Weg vergisst. A* hält beides zusammen: Es bevorzugt Knoten in Zielrichtung, ohne zu vergessen, was der Weg dorthin bisher gekostet hat.
Ist die Heuristik zulässig, überschätzt sie die Restkosten nie. Dann kann A einen Pfad erst dann endgültig verwerfen, wenn feststeht, dass er teurer ist als eine bereits gefundene Alternative — die günstigste Lösung geht nicht verloren. Unter allen Verfahren, die dieselbe Heuristik nutzen, expandiert A zudem nachweislich die wenigsten Knoten.
Die Schwierigkeit liegt beim Speicher: A hält alle erzeugten Knoten vor, und deren Zahl kann exponentiell wachsen. In großen Räumen geht der Arbeitsspeicher aus, lange bevor die Rechenzeit zum Problem wird. Speicherschonende Varianten (IDA, RBFS, SMA) und die gewichtete A-Suche, die schnellere, aber nicht mehr garantiert optimale Lösungen liefert, umgehen das.
Peter Hart, Nils Nilsson und Bertram Raphael veröffentlichten das Verfahren 1968 am Stanford Research Institute; es entstand im Zusammenhang mit dem Roboter Shakey. A* gehört zu den meistgelehrten Algorithmen der KI und steckt bis heute in Navigationssoftware, in der Wegfindung von Computerspielen und in der Routenplanung von Robotern.
Hallo! Ich bin dein KI-Tutor.
Melde dich an, um mit mir zu chatten — ich erinnere mich dann auch an eure letzten Gespräche.
