A-Stern

Der \(A^*\)-Algorithmus¹ (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:

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.

1. Finde mittels einer Tiefensuche (maximale Tiefe: 6) den Lösungsweg zur beschriebenen Zielposition aus der dargestellten Ausgangsstellung.
   Vervollständige dazu den Suchbaum auf dem Zusatzblatt von links nach rechts bis der Zielknoten erreicht ist. Schreibe neben jeden Knoten die Reihenfolge, in welcher diese besucht werden (z.B. mit roter Farbe)
2. Denke dir eine Heuristik aus (d.h. definiere die Funktion \(h(N)\)), um dieses Problem mit dem \(A^*\) zu lösen. Diese Heuristik soll ein Mass dafür sein, wie nahe am Ziel der jeweilige Knoten ist.
3. Zeichne in den Suchbaum aus Aufgabe 1 ein, wie der \(A^*\) mit deiner Funktion \(h(N)\) von Aufgabe 2 den Baum absuchen würde. Beginne beim Startknoten und berechne für alle Nachfolgeknoten
   \(f(n) = g(n) + h(n)\). Dabei ist \(g(n)\) die Anzahl bereits zurückgelegten Kanten. Verfolge immer denjenigen Nachfolgeknoten weiter, der den kleinsten Wert von \(f(n)\) hat. Schreibe neben jeden betrachteten Knoten den Wert der Funktion \(f(N)\) (z.B. so: (1) mit grün) und die Reihenfolge in welcher die Knoten besucht werden (z.B. <4> mit blau).
   Ist der \(A^*\) schneller als die Tiefensuche ohne Heuristik? Wie viele Knoten müssen besucht werden? Vergleiche diese Zahl mit denjenigen der Breiten- bzw. Tiefensuche.

\(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