Informierte Suche Flashcards
Was ist eine Heuristik bzw. was macht diese?
Eine Heuristik ist eine Funktion mit der man die Restkosten zum Ziel approximieren möchte.
Was ist der unterschied zwischen einer informierten Suche und einer uninformierten Suche?
Eine maximal uninformierte Suche ist eine Suche die keine Heuristik verwerden. Mann könnte auch sagen h(n) = 0 für alle Zustände n. Hingegen benutzen informierte Suchen Heuristiken um die aktuellen Zustand zu bewerten um bessere Wahlen für die nächsten zu erkundenen Zustände zu treffen.
Was ist die Bewertrungsfunktion bei einer Informierten Suche?
Die Bewertungsfunktion f(n) bewertet den aktuellen Zustand auf grund von der Heuristik h(n) und den bereits angefallenend Pfadkosten g(n).
Bewertungsfunktion f(n) = g(n) + h(n)
Sie ist also auch eine Approximation der entgültigen Pfadkosten.
Welche Anforderungen muss eine heuristische Funktion erfüllen
- h(x) >= 0 für alle Zustände. h(x) = 0 ist maximal uninformiert.
- h(x) = 0 für jeden Zielzustand
Pseudocode vom A* Algorithmus
Wann ist eine Heuristik zulässig?
Wenn ihre Werte im Intervall [0, g*] liegen, wobei g* die tatsächlichen Pfadkosten vom aktuellen Zustand zum sind. Heißt die Heuristik darf niemals die Pfadkosten als zu hoch einstufen als sie sind.
Warum darf eine Heuristik die Kosten niemals höher einschätzen als die tatsächlichen Kosten?
Weil sonst die Gefahr besteht, das man nicht in der optimalen Lösung terminiert.
Wann ist eine Heuristik Monoton?
Wenn für alle Knotenpaare (x,y) für die es eine Kante gibt gilt:
f(x) <= f(y) = g(y) + h(y) = g(x) + c + h(y) oder auch
h(x) <= c + h(y)
wobei c die Aktionskosten von x nach y sind.
Warum will man das eine Heuristik monton ist?
Es stellt sicher, dass jeder expaniderte Knoten auf dem kürzesten möglichen Weg erreicht wird. Daruch muss man suboptimale Pfade nicht mehr extra behandeln.
Was sind suboptimale Pfade bei einer informierten Suche?
Wenn durch die Heuristik zuerst der Pfad ABZ erkunndet wird aber eigentlich der Pfad AC kürzer wäre.
Die roten Zahlen sind die h(x) Werte
Was für Auswirkungen hat die Wahl der Heuristik in hinsicht auf A*
- unzulässige Heuristik schätzt Pfade zu pessimistisch ein: gefährded Optimalität von A*
- unzulässige Heuristik hat negative h-Werte: gefährded Vollständkigkeit von A*
- zulässige Heuristik: A* ist vollständig und optimal, Speicher- und Laufzeitklasse = Branch & Bound. In der Realität aber besser.
- zulässige monotone Heuristik: A* hat quadratische Worst-Case-Laufzeit
Was bedeutet es, das A* optimal effizient ist?
Jeder andere vollständige und optimale Algorithmus besucht mindestens genau so viele Konten wenn er die gleiche Heuristik verwendet.
Was macht der SMA* Algorithmus?
Der Algorithmus ist eine Modifizierung des A* Algorithmuses um ihn Speichereffizienter zu machen. Wenn der speicher errreicht ist wird der “schlechteste” Knoten entfernt und sein f-Wert wird im Elternknoten zwischengespeichert um ihn später wieder Konstruieren zu können. Der Knoten wird also “vergessen”. Danach kann der nächste Knoten generiert werden. SMA* findet eine Lösung genau dann wenn mindestens ein Lösungsfad in den Speicher passt.
