Kapitel 3 - Problemlösung durch Suchen

Question 1

Definition Suche

Answer 1

Ermitteln einer Folge von Aktionen, die das Ziel erreicht

Question 2

Definition Lösung

Answer 2

Aktionsfolge

Question 3

Definition Problem

Answer 3

Ausgangszustand
Mögliche Aktionen
Überführungsmodell: Was bewirkt jede Aktion
Zieltest: Ist ein Zustand ein Zielzustand?
Pfadkostenfunktion: Kosten

Question 4

Definition Suchbaum

Answer 4

Mögliche Aktionssequenzen, die beim Ausgangszustand beginnen

Question 5

Definition Grenzknoten

Answer 5

Menge aller zur Erweiterung an einem bestimmten Punkt verfügbare Blattknoten
(Alle nachfolgenden Knoten sind noch unbesucht)

Question 6

Definition redundanter Pfad

Answer 6

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

Question 7

Datenstruktur für Knoten n?

Answer 7

• 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

Question 8

Größen zur Leistungsbewertung?

Answer 8

• 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

Question 9

Definition Verzweigungsfaktor

Answer 9

Maximale Anzahl der Kinder jedes Knotens

Question 10

Definition Vollständigkeit

Answer 10

Findet der Algorithmus garantiert eine Lösung, wenn eine existiert?

Question 11

Definition Optimalität

Answer 11

Findet der Algorithmus die optimale Lösung?

Question 12

Definition Zeitkomplexität

Answer 12

Wie lange dauert es, bis eine Lösung gefunden wurde?

Question 13

Definition Speicherkomplexität

Answer 13

Wie viel Speicher wird für die Suche benötigt

Question 14

Welche Datenstruktur wird für die Breitensuche benötigt?

Answer 14

FIFO-Warteschlange

Question 15

Welche Datenstruktur wird für die Suche Einheitliche Kosten benötigt?

Answer 15

Prioritätswarteschlange, sortiert nach Pfadkosten

Question 16

Welche Datenstruktur wird für die Tiefensuche benötigt?

Answer 16

LIFO-Warteschlange bzw. Stack

Question 17

Wie funktioniert die beschränkte Tiefensuche?

Answer 17

Wie Tiefensuche, jedoch wird die Tiefe beschränkt

Question 18

Wie funktioniert die Iterative Vertiefung?

Answer 18

Wie eine Breitensuche, bei der in jeder Iteration die Suchtiefe erhöht wird

Question 19

Wie funktioniert die bidirektionale Suche?

Answer 19

Suche, bei der bei Start und Ziel gleichzeitig gestartet wird

Question 20

Was ist eine uniformierte Suchstrategie?

Answer 20

Eine Suchstrategie, die außer der Problemstellung keine weiteren Informationen hat

Question 21

Was ist eine informierte (heuristische) Suchstrategie?

Answer 21

Eine Suchstrategie, die problemspezifisches Wissen nutzt

Question 22

Wie funktioniert die Bestensuche (Best-First)?

Answer 22

Wählt Knoten auf Basis einer Evaluierungsfunktion f als Kostenabschätzung aus. Der Knoten mit der geringsten Bewertung wird zuerst erweitert.

Question 23

Wie funktioniert die Greedy Best-First Suche?

Answer 23

Wählt den Knoten aus, der dem Ziel am nächsten liegt

Question 24

Welche Evaluierungsfunktion nimmt der A*-Algorithmus?

Answer 24

f(n) = g(n) + h(n) mit

• g: Pfadkosten vom Ausgangsknoten
• h: geschätzte Kosten des billigsten Pfades zum Ziel

Question 25

Definition Zulässigkeit einer Heuristik

Answer 25

Kosten, um das Ziel zu erreichen wird niemals überschätzt

Question 26

Definition Konsistenz einer Heuristik

Answer 26

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

Question 27

Welche speicherbegrenzte heuristische Suchen gibt es u.A.?

Answer 27

• Iterative-Deepening-A* (IDA*)
• Recursive Best-First Search (RBFS)
• (S)MA* ((Simplified) Memory-Bounded A*)

Question 28

Wie funktioniert Iterative-Deepening-A* (IDA*)?

Answer 28

Ähnlich wie iterative Vertiefung; Kürzungswert ist der kleinste f-Kostenwert jedes Knotens, der die Kürzung der vorherigen Iteration überschritten hat

Question 29

Wie funktioniert Recursive Best-First Search (RBFS)?

Answer 29

• Ä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

Question 30

Welche Speicherkomplexität hat Recursive Best-First Search (RBFS)?

Answer 30

Linear

Question 31

In welchem Fall ist RBFS optimal?

Answer 31

Wenn die Heuristik zulässig ist

Question 32

Wie funktioniert (S)MA* ((Simplified) Memory-Bounded A*)?

Answer 32

• 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

Question 33

Definition einer dominierenden Heuristik

Answer 33

Heuristik h2 dominiert h1, wenn gilt: h2>=h1.

h2 ist dann die bessere Heuristik

Question 34

Wie können Heuristiken generiert werden?

Answer 34

Indem das Problem gelockert wird (d. h. mit weniger Beschränkungen)

Question 35

Was bedeutet, dass ein Problem gelockert wird?

Answer 35

Die Beschränkungen werden verringert

Question 36

Wie hängen Lösung eines Problems und eines gelockerten Problems zusammen?

Answer 36

Eine optimale Lösung für das Problem ist auch eine Lösung für das gelockerte Problem.

Question 37

Welche Eigenschaften hat die Heuristik

h(n):=max{h1(n), …, hm(n)}?

Answer 37

• Zulässig
• Konsistent
• Dominiert alle Komponenten-Heuristiken

Question 38

Welchen Zweck haben Musterdatenbanken?

Answer 38

Musterdatenbanken speichern Lösungskosten für alle Unterprobleme