Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03528.jsonl.gz/977

Anzeige
A-Stern
Der
Bei der Breitensuche wird keine «intelligente» Auswahl der Knoten in der Open-List getroffen, die Knoten werden in willkürlicher Reihenfolge verarbeitet. Der
Definition
wobei
Bei der Schätzung muss gelten:
wobei
Dabei ist
Die Funktion
Beispiel
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|
Aufgabe: Schiebepuzzle 1
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
- 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)
Lösung
Aufgabe: Schiebepuzzle
- Denke dir eine Heuristik aus (d.h. definiere die Funktion
), um dieses Problem mit dem zu lösen. Diese Heuristik soll ein Mass dafür sein, wie nahe am Ziel der jeweilige Knoten ist.
Lösung
h(N) := Anzahl falsch platzierte Zahlen
Diese Heuristik erfüllt die Bedingungen: Jede falsch platzierte Zahl muss in mindestens einem Zug verschoben werden, um an den korrekten Ort zu kommen.
Aufgabe: Schiebepuzzle
- Zeichne in den Suchbaum aus Aufgabe 1 ein, wie der
mit deiner Funktion von Aufgabe 2 den Baum absuchen würde. Beginne beim Startknoten und berechne für alle Nachfolgeknoten . Dabei ist die Anzahl bereits zurückgelegten Kanten. Verfolge immer denjenigen Nachfolgeknoten weiter, der den kleinsten Wert von hat. Schreibe neben jeden betrachteten Knoten den Wert der Funktion (z.B. so: (1) mit grün) und die Reihenfolge in welcher die Knoten besucht werden (z.B. <4> mit blau).
Ist der
schneller als die Tiefensuche ohne Heuristik? Wie viele Knoten müssen besucht werden? Vergleiche diese Zahl mit denjenigen der Breiten- bzw. Tiefensuche.
Lösung
Der Algorithmus ist bedeutend schneller als ohne Heuristik. Es müssen nur 7 Knoten expandiert werden, bei der Breitensuche waren es 34, bei der Tiefensuche 31 (diese Zahl ist aber abhängig davon, wie man den Baum zeichnet).
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
Vergleich
Abschliessend wollen wir die 3 Algorithmen miteinander vergleichen:
|Breitensuche||Dijkstra||A-Stern|
|Ansatz||«Brute Force»||«Algorithmisch»||«Heuristisch»|
|Voraussetzung||normaler Graph||gewichteter Graph||gewichteter Graph inkl. Heuristik|
Aufgabe
Auf der verlinkten Seite kannst du Breitensuche, Dijkstra und A-Stern miteinander vergleichen. Teste die Seite aus und beantworte folgende Fragen:
- Was ist «Breadth First»?
- Was ist «Depth First»?
- Wofür stehen die Farben wenn man bei Terrain den Eintrag Simplex Terrain wählt. Welchen Einfluss haben diese auf den A-Stern-Algorithmus?
Zusatzaufgabe
Der A-Stern-Algorithmus kommt auch in Computer-Spielen zu Einsatz:
Lies dich durch den folgenden Beitrag durch und teste die tollen (und teilweise interaktiven) Visualisierungen:
Teile übernommen von Ryter, M.: Einführung in die künstliche Intelligenz. http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/ (26.12.2009) ↩︎