Kapitel 3 - Problemlösung durch Suchen Flashcards
Definition Suche
Ermitteln einer Folge von Aktionen, die das Ziel erreicht
Definition Lösung
Aktionsfolge
Definition Problem
Ausgangszustand
Mögliche Aktionen
Überführungsmodell: Was bewirkt jede Aktion
Zieltest: Ist ein Zustand ein Zielzustand?
Pfadkostenfunktion: Kosten
Definition Suchbaum
Mögliche Aktionssequenzen, die beim Ausgangszustand beginnen
Definition Grenzknoten
Menge aller zur Erweiterung an einem bestimmten Punkt verfügbare Blattknoten
(Alle nachfolgenden Knoten sind noch unbesucht)
Definition redundanter Pfad
Längerer Weg, um zum selben Ziel zu gelangen, Spezialfall: Schleifenpfade: Enthält wiederholte Zustände. Redundante Pfade können vermieden werden, wenn besuchte Pfade gespeichert werden
Datenstruktur für Knoten n?
- n.STATE: Zustand, dem der Knoten entspricht
- n.PARENT: Knoten im Suchbaum, der diesen Knoten generiert hat
- n.ACTION: Aktion, die auf den Elternknoten angewandt wurde, um den Knoten zu generieren
- n.PATH-COST: Kosten des Pfades vom Ausgangszustand zum Knoten
Größen zur Leistungsbewertung?
- b: Verzweigungsfaktor: Maximale Anzahl der Kinder jedes Knotens
- d: Tiefe des flachsten Knotens
- m: Maximale Länge eines beliebigen Pfades im Zustandsraum
- Suchkosten: Kosten, um eine Lösung zu finden
- Gesamtkosten: Suchkosten und Länge des gefundenen Pfades
Definition Verzweigungsfaktor
Maximale Anzahl der Kinder jedes Knotens
Definition Vollständigkeit
Findet der Algorithmus garantiert eine Lösung, wenn eine existiert?
Definition Optimalität
Findet der Algorithmus die optimale Lösung?
Definition Zeitkomplexität
Wie lange dauert es, bis eine Lösung gefunden wurde?
Definition Speicherkomplexität
Wie viel Speicher wird für die Suche benötigt
Welche Datenstruktur wird für die Breitensuche benötigt?
FIFO-Warteschlange
Welche Datenstruktur wird für die Suche Einheitliche Kosten benötigt?
Prioritätswarteschlange, sortiert nach Pfadkosten
Welche Datenstruktur wird für die Tiefensuche benötigt?
LIFO-Warteschlange bzw. Stack
Wie funktioniert die beschränkte Tiefensuche?
Wie Tiefensuche, jedoch wird die Tiefe beschränkt
Wie funktioniert die Iterative Vertiefung?
Wie eine Breitensuche, bei der in jeder Iteration die Suchtiefe erhöht wird
Wie funktioniert die bidirektionale Suche?
Suche, bei der bei Start und Ziel gleichzeitig gestartet wird
Was ist eine uniformierte Suchstrategie?
Eine Suchstrategie, die außer der Problemstellung keine weiteren Informationen hat
Was ist eine informierte (heuristische) Suchstrategie?
Eine Suchstrategie, die problemspezifisches Wissen nutzt
Wie funktioniert die Bestensuche (Best-First)?
Wählt Knoten auf Basis einer Evaluierungsfunktion f als Kostenabschätzung aus. Der Knoten mit der geringsten Bewertung wird zuerst erweitert.
Wie funktioniert die Greedy Best-First Suche?
Wählt den Knoten aus, der dem Ziel am nächsten liegt
Welche Evaluierungsfunktion nimmt der A*-Algorithmus?
f(n) = g(n) + h(n) mit
- g: Pfadkosten vom Ausgangsknoten
- h: geschätzte Kosten des billigsten Pfades zum Ziel
Definition Zulässigkeit einer Heuristik
Kosten, um das Ziel zu erreichen wird niemals überschätzt
Definition Konsistenz einer Heuristik
Dreiecksungleichung:
h(n) <= c(n, a, n’) + h(n’)
Kosten von n aus sind geringer, als die Kosten von n’ plus Kosten, um von n nach n’ zu gelangen
Welche speicherbegrenzte heuristische Suchen gibt es u.A.?
- Iterative-Deepening-A* (IDA*)
- Recursive Best-First Search (RBFS)
- (S)MA* ((Simplified) Memory-Bounded A*)
Wie funktioniert Iterative-Deepening-A* (IDA*)?
Ähnlich wie iterative Vertiefung; Kürzungswert ist der kleinste f-Kostenwert jedes Knotens, der die Kürzung der vorherigen Iteration überschritten hat
Wie funktioniert Recursive Best-First Search (RBFS)?
- Ähnlich rekursiver Tiefensuche, Variable f_limit gibt an, wie tief der Algorithmus gehen darf
- f_limit ist gleich dem besten Alternativpfad (also dem zweitbesten)
- Wenn der Algorithmus zurückgeht, ersetzt er den f-Wert jedes Knotens auf dem Pfad durch die backed-up value, den besten f-Wert seiner untergeordneten Knoten
Welche Speicherkomplexität hat Recursive Best-First Search (RBFS)?
Linear
In welchem Fall ist RBFS optimal?
Wenn die Heuristik zulässig ist
Wie funktioniert (S)MA* ((Simplified) Memory-Bounded A*)?
- Arbeitet wie A*, das beste Blatt wird expandiert
- Wenn Speicher voll, wird ältestes schlechteste Blatt gelöscht und Wert des vergessenen Knotens wird im übergeordneten Knoten gespeichert
Definition einer dominierenden Heuristik
Heuristik h2 dominiert h1, wenn gilt: h2>=h1.
h2 ist dann die bessere Heuristik
Wie können Heuristiken generiert werden?
Indem das Problem gelockert wird (d. h. mit weniger Beschränkungen)
Was bedeutet, dass ein Problem gelockert wird?
Die Beschränkungen werden verringert
Wie hängen Lösung eines Problems und eines gelockerten Problems zusammen?
Eine optimale Lösung für das Problem ist auch eine Lösung für das gelockerte Problem.
Welche Eigenschaften hat die Heuristik
h(n):=max{h1(n), …, hm(n)}?
- Zulässig
- Konsistent
- Dominiert alle Komponenten-Heuristiken
Welchen Zweck haben Musterdatenbanken?
Musterdatenbanken speichern Lösungskosten für alle Unterprobleme
