64
Problemlösen durch Suchen

Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Embed Size (px)

Citation preview

Page 1: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Problemlösen durch Suchen

Page 2: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Überblick

• Problemlösende Agenten

• Motivation: Problemlösen durch Suche

• Problemtypen

• Probleme formulieren

• Beispielprobleme

• Einfache Suchalgorithmen

Page 3: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Problemlösende Agenten

Offline-Problemlösen, da Wissen vollständig!

Page 4: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Begriffe: Online / Offline

• Offline:1. Berechne erst vollständige Lösung

2. Dann Ausführung in der Realwelt

• Online: „Interleaving“, d.h. Verzahnung – Berechnung– Aktion– Berechnung– Aktion …

Page 5: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Problemlösen durch Suchen

• Erinnerung: Modellbasierte Agenten „denken“ über Wirkung ihrer Aktionen nach

• Besonders wichtig, wenn eine Aktion nicht ausreicht, um zum Ziel zu kommen, …

• … sondern mehrere Aktionen in der richtigen Reihenfolge nötig sind!

• Ansatz: Mehrere Aktionsfolgen durchspielen

Page 6: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Rumänien

• Standort: Arad• Ziel: Bukarest• Zielformulierung:

– In Bukarest sein

• Problemformulierung:– Zustände: Verschiedene Städte– Aktionen: Von einer Stadt zur anderen fahren

• Lösung finden:– Folge von Städten finden, z.B. Arad, Sibiu, Fagaras,

Bukarest

––

–•

Page 7: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Rumänien

Page 8: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Einordnung der Umgebung „Landkarte“

• Statisch: Städte fest• Beobachtbar: Agent kennt Standort• Diskret: Fahrt nur durch „diskrete“ Städte, nicht

querfeldein• Deterministisch: Aktion „Fahre nach X“ endet in X

Page 9: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Weitere Begriffe: Problemtypen• Deterministisch, vollständig beobachtbar Ein-Zustands-Problem (single state problem)

– Agent weiß genau, in welchem Zustand er gelangen wird; Lösung ist eine Zustandsfolge

(Ein-Zustands-Problem heißt nicht, dass es nur einen Zustand gibt!)• Nicht-beobachtbar Sensorloses Problem (“Angepasstes

(conformant) Problem”)– Z.B. Staubsauger kennt seinen Ort nicht ; Lösung ist eine Zustandsfolge

• Nicht-deterministisch und/oder teilweise beobachtbar Kontingenzproblem– Wahrnehmungen liefern neue Information über aktuellen Zustand– Meist Interleaving erforderlich– Wenn die neue Information durch anderen Agenten verursacht wird:

Adversariales Problem• Unbekannter Zustandsraum Explorationsproblem

––

Page 10: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Staubsaugerwelt

• Einzustands-Problem, Start #5 Lösung?

Page 11: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Staubsaugerwelt

• Einzustands-Problem, Start #5

Lösung? [Rechts, Saugen]

Page 12: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Staubsaugerwelt

• Sensorlos, Start in {1,2,3,4,5,6,7,8} z.B. Rechts geht über in {2,4,6,8},

d.h. Menge von Zuständen

statt nur eines Zustands.Lösung?

Page 13: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Staubsaugerwelt

• Sensorlos, Start in {1,2,3,4,5,6,7,8} z.B. Rechts geht über in {2,4,6,8} },

d.h. Menge von Zuständen

statt nur eines Zustands. Lösung? [Rechts,Saugen,Links,Saugen]

Page 14: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Staubsaugerwelt

• Kontingenz-Problem – Nicht-deterministisch:

Z.B. Saugen kann Teppich

verschmutzen!– Teilweise beobachtbar:

Ort, Schmutz am aktuellen Ort.– Wahrnehmung:

[L, Sauber], d.h. Start in #5 oder #7

Lösung?

Page 15: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Staubsaugerwelt

• Kontingenz-Problem – Nicht-deterministisch:

Z.B. Saugen kann Teppich

verschmutzen!– Teilweise beobachtbar:

Ort, Schmutz am aktuellen Ort.– Wahrnehmung:

[L, Sauber], d.h. Start in #5 oder #7

Lösung?

[Rechts, wenn Schmutz dann Saugen]

Page 16: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Formulierung des Single-State Problems

Nach Festlegen der Zustände ist ein Problem definiert durch vierPunkte:

1. Anfangszustand, z.B. „in Arad"2. Aktionen, die in einem Zustand möglich sind, sind gegeben durch

die Nachfolgerfunktion S(x) = Menge der Aktion–Zustand Paare – Z.B. S(Arad) = {<Arad Zerind, Zerind>, … }

3. Pfadkosten (additiv)– Z.B. Summe der Distanzen, # Aktionen etc.– c(x,a,y) ≥ 0 sind die Schrittkosten

4. Zieltest:– Explizit, z.B. x = „in Bukarest"– Implizit, z.B. Schachmatt(x)

Eine Lösung ist eine Sequenz von Aktionen die vom Anfangszustandzum Zielzustand führen.

––

Page 17: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Wahl des Zustandsraums• Realwelt ist hochkomplex

Zustandsraum muss abstrahieren • Wahl der Zustände schwierigster Teil der Problemformulierung!• Hier:

– Zustand = Stadt– Kosten = Entfernung der Mittelpunkte

• Was wurde ignoriert / idealisiert?– Kosten = Strecke (nicht Fahrzeit, Spritkosten)– Ausdehnung der Stadt, Stau, Straßenzustand– Detailabläufe: Gas geben, lenken, …

• (Abstrakter) Zustand = Menge realer Zustände• (Abstrakte) Aktion = komplexe Kombination realer Aktionen

– Z.B. "Arad Zerind" repräsentiert eine komplexe Menge möglicher Routen, Umwege, Gasgeben, Lenken, etc.

• Um Realisierbarkeit zu garantieren muss jeder reale Zustand "in Arad“ zu einem realen Zustand "in Zerind“ führen

• (Abstrakte) Lösung = – Menge der Pfade die Lösungen in der Realwelt sind

• Jede abstrakte Aktion sollte "einfacher" sein als das reale Problem

•••

Page 18: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Pfadkostenfunktion• Hier: Pfadkosten = Summe der Schrittkosten• Schritt = Aktion, die von einem Zustand zum

nächsten führt• Sinnvoll z.B. bei Städte-Problem

– A nach B 20 km– B nach C 10 km– A über B nach C 30 km

• Gegenbeispiel:– Auto beschleunigt auf Weg von A nach B: 3 sec– Auto beschleunigt auf Weg von B nach C: 3 sec– Auto beschleunigt von A nach B (3 sec), ist also auf

Weg von B nach C schon schneller (1 sec) !

Page 19: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Staubsaugerwelt als Zustandsraum

• Zustände?• Aktionen?• Zieltest?• Pfadkosten?

Page 20: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Staubsaugerwelt als Zustandsraum

• Zustände? Diskreter Schmutz und diskreter Ort• Aktionen? Links, Rechts, Saugen• Zieltest? Kein Schmutz an allen Orten• Pfadkosten? 1 pro Aktion

Page 21: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Schiebefax

• Zustände?• Aktionen? • Zieltest?• Pfadkosten?

Page 22: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Beispiel: Schiebefax

• Zustände? Anordnungen • Aktionen? Verschiebe Lücke links, rechts, rauf, runter • Zieltest? Bestimmte Anordnung• Pfadkosten? 1 pro Verschieben

[Bemerkung: optimale Lösung der n-Puzzle Familie ist NP-hart]

••

Page 23: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

8-Damen Problem

• Zustände: 0-8 Damen in bel. Anordnung• Ausgangszustand: Brett leer• Nachfolgerfunktion: 1 Dame auf freies Feld setzen• Pfadkosten: Egal• Zieltest: Alle 8 Damen da, keine wird bedroht

Page 24: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Verwandte Problem der Routensuche

• Routensuche (Zustand = Stadt)

• Touring Problem: – Jede Stadt 1x besuchen, Anfangs- = Endstadt– Zustand = Aktuelle Stadt + alle schon

besuchten

• Traveling Salesman Problem: Kürzesten Weg für Touring finden

Page 25: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Realweltproblem: Manipulation durch Roboter

• Zustände?: Reellwertige Gelenkwinkel des Arms, reellwertige Objektkoordinaten

• Aktionen?: Kontinuierliche Gelenkwinkel, Gelenkwinkelgeschwindigkeiten, -beschleunigungen

• Zieltest?: Z.B. vollständige Montage• Pfadkosten?: Ausführungszeit

•••

Page 26: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Suchbäume

• Idee:– Offline, simulierte Exploration des Suchraums, indem

Nachfolger bereits untersuchter Zustände generiert werden (“Expandierung” von Zuständen)

Page 27: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Suchbaum: Beispiel

Page 28: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Suchbaum: Beispiel

Page 29: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Suchbaum: Beispiel

Page 30: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Implementierung: Allgemeiner Suchbaum

Page 31: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Implementierung: Zustände / Knoten• Ein Zustand ist eine Repräsentation einer physischen Konfiguration

• Ein Knoten ist eine Datenstruktur, die Bestandteil des Suchbaums ist. Umfasst Zustand, Elternknoten, Aktion, Pfadkosten g(x), Tiefe

• Ein Zustand kann durch mehrere Knoten repräsentiert sein! (Z.B. Arad – Sibiu – Arad bei ungünstiger Strategie)

• Die Expand Funktion erzeugt neue Knoten und belegt die Felder der Datenstrukturen mit Werten. Insb. wird die Nachfolgefunktion SuccessorFn des Problems angewendet, um die entsprechenden Zustände zu erhalten.

Page 32: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Suchstrategien• Eine Suchstrategie ist definiert durch die Reihenfolge, in

der die Knoten expandiert werden.

• Strategien werden anhand folgender Kriterien bewertet: – Vollständigkeit: Wird garantiert eine Lösung gefunden, falls eine

existiert?– Zeitkomplexität: Zahl der erzeugten Knoten – Speicherkomplexität: Maximalzahl der Knoten im Speicher – Optimalität: Wird die Lösung mit den geringsten Kosten sicher

gefunden?– Optimalität heißt nicht: Die (optimale oder suboptimale) Lösung

wird mit geringstem Suchaufwand gefunden!

• Zeit- und Speicherkomplexität werden in folgenden Größen ausgedrückt:– b: Maximaler Verzweigungs (branching-)faktor des Suchbaums– d: Minimale Tiefe (depth) der optimalen Lösung– m: Maximale Tiefe des Suchbaums (u.U. ∞)

––

Page 33: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Uninformierte Suchstrategien

• Uninformierte Suchstrategien verwenden nur die Information, die durch die Problemdefinition gegeben ist

• Wichtigste Strategien:– Breitensuche (Breadth-first search)

– Suche mit einheitliche Kosten (Uniform-cost search)

– Tiefensuche (Depth-first search )

– Tiefenbeschränkte Suche (Depth-limited search)

– Iterative Tiefensuche (Iterative deepening search)

Page 34: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

Page 35: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

Page 36: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

Page 37: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

Page 38: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Eigenschaften der Breitensuche

• Vollständig? Ja (falls b endlich)• Zeit? 1+b+b2+b3+… +bd + bd+1-b = O(bd+1) (Wenn Lsg. auf Tiefe d müssen noch bd+1-b Knoten (unnötig) erzeugt werden.)• Speicher? O(bd+1) (jeder Knoten wird

gespeichert)• Optimal? Ja (falls Kosten = 1 pro Schritt)

• Speicher ist das Hauptproblem (noch mehr als Zeit)

••

Page 39: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Suche mit einheitliche Kosten

• Expandiere Knoten mit (bisher) geringsten Pfadkosten zuerst

• Implementierung:– Rand = Schlange geordnet nach Pfadkosten

• Equivalent zu breadth-first falls Schrittkosten alle gleich• Vollständig? Ja, falls Schrittkosten ≥ ε• Zeit? # Knoten mit g ≤ Kosten der optimalen Lösung,

O(bceiling(C*/ ε)), wobei C* = Kosten der optimalen Lösung• Speicher? # Knoten mit g ≤ Kosten der opitmalen

Lösung, O(bceiling(C*/ ε))• Optimal? Ja – Knoten werden in ansteigender Ordnung

von g(n) expandiert

••••

Page 40: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 41: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search

• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 42: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 43: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 44: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 45: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 46: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 47: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 48: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 49: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 50: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 51: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

Page 52: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Eigenschaften der depth-first search

• Vollständig? Nein: Versagt in unendlich tiefen Suchräumen und Suchräumen mit Schleifen – Modifikation: Verbot der Zustandswiederholung

entlang eines Pfades Vollständig in endlichen Suchräumen

• Zeit? O(bm): Katastrophal falls m wesentlich größer als d– Aber: Falls Lösungen “dicht” sind, kann depth-first

wesentlich schneller sein als breadth-first

• Speicher? O(bm), d.h., linear im Speicher!• Optimal? Nein

••

–•

Page 53: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Tiefenbeschränkte Suche

= depth-first Suche mit Tiefenlimit l,

d.h. Knoten mit Tiefe l haben keine Nachfolger

• Rekursive Implementierung:

Page 54: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Iterative Tiefensuche

Page 55: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Iterative Tiefensuche l =0

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Page 56: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Iterative Tiefensuche l =1

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Page 57: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Iterative Tiefensuche l =2

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Page 58: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Iterative Tiefensuche l =3

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Page 59: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Iterative Tiefensuche

• Zahl der Knoten, die depth-limited Suche bis Tiefe d mit Verzweigungsfaktor b generiert:

NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd

• Zahl der Knoten, die Iterative Tiefensuche bis Tiefe d mit Verzweigungsfaktor b generiert: NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd

• Für b = 10, d = 5,– NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111– NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

• Overhead = (123,456 - 111,111)/111,111 = 11%

–•

Page 60: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Eigenschaften der Iterativen Tiefensuche

• Vollständig? Ja

• Zeit? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)

• Speicher? O(bd)

• Optimal? Ja, wenn Schrittkosten = 1

Page 61: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Übersicht

Page 62: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Wiederholte Zustände• Wenn wiederholte Zustände nicht erkannt werden, kann

ein lineares Problem exponentiell werden!

Zustandsraum Suchbaum

Page 63: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Graphensuche• Modifikation von Tree-Search: Liste bereits besuchter Zustände• Bei wiederholtem Zustand wird der neue Pfad verworfen• Findet daher i.a. nicht das Optimum, außer im Fall

– konstanter Kosten oder

– Breadth-first-seach

• Speicherprobleme bei sehr vielen Zuständen

Page 64: Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche Problemtypen Probleme formulieren Beispielprobleme Einfache

Zusammenfassung

• Problemformulierung erfordert gewöhnlich Abstraktion. Irrelevante Details der Realwelt werden weggelassen um einen Zustandsraum zu erhalten, in dem das Problem durch Suche gelöst werden kann.

• Sehr unterschiedliche “blinde” / “uninformierte” Suchstrategien

• Iterative Tiefensuche benötigt nur linearen Speicher und nicht wesentlich mehr Zeit als andere uninformierte Algorithmen

• Graphensuche vermeidet wiederholte Zustände

••