Der \(A^*\)-Algorithmus1 (im folgenden \(A^*\) genannt) wird verwendet um in einem Baum oder allgemein in einem Graphen den kürzesten Pfad zwischen zwei Knoten zu finden. Im Rahmen dieses Unterrichtsblocks wird der Einfachheit halber von einem Baum ausgegangen, allgemeinere Graphen werden nicht betrachtet. Um den \(A^*\) anwenden zu können, müssen die Kanten des Baumes mit Kosten versehen sein. Gesucht ist nun der kürzeste (bzw. billigste) Pfad zwischen der Wurzel des Baumes und einem bestimmten Zielknoten.
Bei der Breiten- bzw. Tiefensuche wird keine «intelligente» Auswahl der Knoten in der Liste OPEN getroffen, die Knoten werden in willkürlicher Reihenfolge verarbeitet. Der \(A^*\) ist eine Verfeinerung dieser Verfahren, wobei folgendermassen immer der vielversprechendste Knoten weiterverarbeitet wird. Es wird abgeschätzt, wie «gut» ein Knoten ist, indem eine Bewertungsfunktion berechnet wird. Die Kosten eines Knotens \(N\) beinhalten zwei Beiträge: einerseits die Kosten vom Startknoten bis zu \(N\) und andererseits die geschätzten Kosten von \(N\) bis zum Zielknoten. Diese Bewertungsfunktion \(f(N)\) für einen Knoten \(N\) wird also folgendermassen definiert:
\(f(N) = g(N) + h(N)\), wobei
\(g(N)\) die Kosten des Pfades vom Startknoten zu \(N\) darstellt und
\(h(N)\) die Kosten des optimalen Pfades von \(N\) zu einem Zielknoten darstellt.
Dabei ist \(h\) normalerweise unbekannt und kann nur abgeschätzt werden. Für dieses \(h\) muss gelten: \(h(N)\geq h^*(N)\), wobei \(h^*(N)\) die wirklichen Kosten des optimalen Pfades von \(N\) zu einem Zielknoten sind. Das heisst \(h\) darf die Kosten eines Knotens nie überschätzen. Oft wird z.B. die euklidische Distanz zum Ziel verwendet.
Die Funktion \(h\) ist eine sog. Heuristik, also eine Abschätzung des wahren Werts. So kann die Suche nach dem optimalen Pfad oft wesentlich beschleunigt werden, was beim \(A^*\) ausgenutzt wird. Man kann zeigen, dass der \(A^*\) immer den kürzesten Weg findet, wenn es einen gibt.
Wir suchen den schnellsten Weg von Würzburg nach Saarbrücken. Durch Abstraktion der Karte haben wir den folgenden gewichteten Graphen erhalten. Zusätzlich kennen wir für jeden Knoten eine Heuristik, nämlich die Distanz der Luftlinie nach Würzburg:
Karte | Aktion |
---|---|
![]() |
|
Schritt 1 | |
![]() |
|
Schritt 2 | |
![]() |
|
Schritt 3 | |
![]() |
|
Schritt 4 | |
![]() |
|
Schritt 5 | |
![]() |
|
Schritt 6 | |
![]() |
Beim Spiel «8-Puzzle» geht es darum, von einer beliebig durcheinander gebrachten Position der Zahlen durch Verschieben einzelner Zahlen in das jeweils leere Feld die folgende Zielposition zu erreichen:
Der \(A^*\)-Algorithmus kann verwendet werden, um diese Aufgabe für beliebige Ausgangsstellungen zu lösen. Im Folgenden geht es darum, diesen algorithmischen Lösungsweg nachzuvollziehen und mit Suchverfahren ohne Heuristik zu vergleichen.
\(A^*\)-Algorithmus in Pseudocode
program a-star
OPEN.add(startNode)
repeat
bestNode := OPEN.remove(Node with minimal f-Value)
if (bestNode == targetNode) then return bestNode
calcF(bestNode.successors())
OPEN.add(bestNode.successors())
CLOSED.add(bestNode)
until (OPEN.isEmpty)
return no path found
end
Teile übernommen von Ryter, M.: Einführung in die künstliche Intelligenz. http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/ (26.12.2009) ↩