KI-Übung

Teil I: Uninformierte Suche

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung

Problem: „Fahre von Lübeck nach Berlin“

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Problem: „Fahre von Lübeck nach Berlin“

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung 1. Schritt: das richtige Abstraktionsniveau wählen

Ziel formulieren: Nach Berlin zu kommen

Für die Planung der Reise wichtig: Kostenebene: Die zurückgelegte Wegstrecke Zustandsebene: In welchem Ort bin ich? Aktionsebene: Von einem benachbarten Ort zum nächsten fahren

Weniger wichtig: Kostenebene: Radioempfang entlang des Weges Zustandsebene: Wetterverhältnisse, Mitfahrer, Radio ein / aus Aktionsebene: Bei Kilometer 10 das Lenkrad um 3° nach links

einschlagen, bei Wittstock das Radio einschalten Warum?

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung 1. Schritt: das richtige Abstraktionsniveau wählen

Jedes unnötige Detail erhöht die Dimension des Suchraumes (exponentiell)

Bei einer geeigneten Abstraktion lässt sich die abstrakte Lösung in eine detaillierte Lösung erweitern (das Wetter kann sich ändern, wir schalten das Radio ein/aus, …)

Die Wahl des Abstraktionsniveaus ist für viele KI-Fragestellungen von großer Bedeutung – und basiert teilweise auf Intuition

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Abstraktionsniveau : Aufspaltung eines abstrakten Zustands

Hamburg

Lübeck

Wittstock

Berlin

Hamburg

Lübeck

Wittstock

Berlin

Hamburg

Lübeck

Wittstock

Berlin

Hamburg

Lübeck

Wittstock

Berlin

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung 2. Schritt: Problem formulieren

Zustände: „in Stadt X“ Nachfolgerfunktion: alle gültigen Zustände, die sich als nächstes

erreichen lassen (alle Städte die sich direkt anfahren lassen) Startzustand festlegen Zielzustand festlegen Kosten für den Zustandsübergang (Entfernung, Zeit)

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung 3. Schritt: Nach einer Lösung suchen

Startzustand und Nachfolgerfunktion definieren einen Suchgraphen Dieser Suchgraph wird durchlaufen und jeder betrachtete Zustand wird

daraufhin untersucht, ob es sich um den Endzustand handelt Im einfachsten Fall wird bei erreichen eines Endzustandes mit

positivem Ergebnis abgebrochen Beispiel

Suche startet mit „in Stadt Lübeck“ Nachfolgezustände sind „in Stadt Hamburg“ und „in Stadt Rostock“

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung 3. Schritt: nach einer Lösung suchen

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

1

1

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung 3. Schritt: nach einer Lösung suchen

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

1

12

2

2

22

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Beispiel für Suchproblem: 8-er Puzzle (Schiebe Puzzle)

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Beispiel für Suchproblem: 8-er Puzzle

Zustand: eine Konfiguration / Reihenfolge der 8 Plättchen

Zustandsübergangsfunktion: Generiert zu einem Zustand die Menge der Zustände, die durch

Verschieben von Plättchen auf die leere Stelle erreicht werden können (ein Zug!)

Maximal 4 mögliche Folgezustände Kostenfunktion:

Jeder Zug kostet „1“

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Beispiel für Suchproblem: 8-Damen Problem

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Beispiel für Suchproblem: 8-Damen Problem

Zustand: eine Konfiguration von 0<n<=8 Damen auf dem Spielbrett

Zustandsübergangsfunktion: Generiert zu einem Zustand alle Zustande die durch Hinzufügen einer

Dame entstehen, so dass keine Dame eine andere bedroht Kostenfunktion:

keine

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Datenstruktur: Suchbaum

Enthält Knoten / Kanten Repräsentiert eine Zustandsfolge, d.h. Knoten des Suchbaumes sind

keine Zustände (sondern enthalten einen Zustand – zwei Knoten können den selben Zustand enthalten)

Knoten-Fachsprache: Elternknoten Zustandsübergang Kosten des Pfades bis zum Knoten Tiefe des Knotens im Suchbaum

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Exkursion „(gerichteter Wurzel-)Baum“

Kreisfreier, zusammenhängender Graph Bei n Knoten genau (n-1) Kanten (und zusammenhängend) Tiefe (depth) d eines Knotens:

Anzahl der Kanten eines Pfades zur Wurzel Grad g eines Knotens:

Anzahl der vom Konten ausgehenden Kanten Verzweigungsgrad (branching factor) b des Baumes:

maximale Anzahl der Nachfolgerknoten über alle Knoten Im gerichteten Wurzelbaum ist ein Knoten (Startknoten) als Wurzel

ausgewiesen, dadurch ist die Richtung der Eltern – Kindbeziehung im Baum vorgegeben

Knoten ohne Kinder heißen Blätter Pfad: Folge von Kanten zwischen zwei Knoten, die Länge entspricht

der (gewichteten) Anzahl der Kanten

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Beispiel: Baum

G E A

F D C BK

I H

17

3

6 4 2 3

8 4

Knoten Kante

Kanten-gewicht

Pfad von F nach H(Länge 12)

Blatt

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Beispiel: Wurzelbaum

G

E

A

F

D C

B

K

I H

17 3

6 4

2

3

8 4

Wurzel

Elternknoten

Tiefe (2)

Kindknoten

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Datenstruktur: Suchbaum

Ein Knoten mit dem Startzustand bildet die Wurzel Noch nicht „expandierte“ Knoten sind Blätter im aktuellen Suchbaum,

die Menge aller dieser Knoten wird auch als ‚fringe‘ (Rand) bezeichnet

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck Lübeck

„fringe“

Wittstock

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Suchalgorithmus

Falls ein Knoten (im Suchbaum! – nicht im Zustandsgraphen) existiert, dessen Nachfolger noch nicht betrachtet wurden (d.h. ein Blatt-Knoten aus der „fringe“), dann

Wenn der Knoten einen Zielzustand enthält, terminiere mit Lösung Sonst, bestimme die Nachfolgerknoten und füge sie zum Suchbaum hinzu

Falls nicht, terminiere ohne Ergebnis Mögliche Datenstrukturen zur Verwaltung der „fringe“:

FIFO / SCHLANGE (implementiert Breitensuche …) LIFO / STACK (implementiert Tiefensuche …) Komplexere Funktion (ggf. mit Kosten)

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Breitensuche (BFS, breadth first search)

Die Blätter des Suchbaumes werden in einer FIFO (first-in-first-out) -Datenstruktur gespeichert

Beginnend mit dem Wurzelknoten werden jeweils alle Nachfolger eines Knoten bestimmt und gespeichert

Wegen FIFO kommen die Kinder immer nach der Elterngeneration dran, d.h.

Es werden erst alle Knoten mit Tiefe n betrachtet, danach alle Knoten mit Tiefe n+1, usw.

Es findet eine Suche „in die Breite“ statt

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Breitensuche (BFS, breadth first search)

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck LübeckWittstock

Ha

mb

urg

Be

rlin

Ro

sto

ck

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Ha

mb

urg

Mü

nst

er

Ha

mb

urg

Ka

sse

l

Ma

gd

eb

urg

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Be

rlin

Ro

sto

ck

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Kostenbasierte Suche (uniform cost search)

Ähnlich wie Breitensuche, aber statt der Tiefe wird anhand einer Kostenfunktion bestimmt, welche Nachfolger gewählt werden sollen

Für Kosten von 1 für alle Zustandsübergänge ergibt sich der gleiche Ablauf wie für Breitensuche

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Kostenbasierte Suche (uniform cost search)

Hamburg

Lübeck

Hamburg

Rostock

Kiel

Wittstock

BremenHannover

Lübeck

Lübeck

70

100

70

90100 120

100

12070

100

110

90100

100120 220

70 100

170 120

Wittstock

170

120

110

Ha

mb

urg

Be

rlin

Ro

sto

ck

Ro

sto

ck

Ha

mb

urg

Ha

mb

urg

Mü

nst

er

Ha

mb

urg

Ka

sse

l

Ma

gd

eb

urg

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Be

rlin

Ro

sto

ck

350 330

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Tiefensuche (DFS, depth first search)

Die Blätter des Suchbaumes werden in einer LIFO (last-in-first-out) -Datenstruktur gespeichert

Beginnend mit dem Wurzelknoten wird sukzessive zu einem Knoten ein Nachfolger (Kind) ausgewählt

Wegen LIFO wird zuerst ein Pfad bis zum Blatt verfolgt, d.h. Es wird immer der Knoten mit der größten Tiefe weiter expandiert Erst wenn bei einem Knoten der Tiefe n keine unbetrachteten Nachfolger

mehr existieren wird der nächste „Geschwisterknoten“ der selben Tiefe betrachtet bzw. ein Knoten mit geringerer Tiefe betrachtet

Es findet eine Suche „in die Tiefe“ statt Alternativ zur Verwaltung aller Kinder im Stack: Backtracking vom Kind

zum Elternknoten, wo der nächste Kindknoten gewählt wird

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Tiefensuche (DFS, depth first search)

Lübeck

Hamburg Rostock

Wittstock

BerlinHamburg

Wittstock

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Tiefensuche mit Tiefenlimit

Ähnlich wie Tiefensuche, aber es werden nur Knoten bis zu einer fest definierten Tiefe n betrachtet

Lübeck

Hamburg Rostock

Wittstock

BerlinHamburg

Wittstock

Tiefenbegrenzung d max=4

Kiel Bremen HannoverLübeck

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Iterativ fortschreitende Tiefensuche (iterative deepening dfs)

Tiefensuche mit Tiefenlimit dmax

Falls eine Lösung gefunden wurde, terminiere mit Lösung Sonst:

Falls der Suchbaum nicht vollständig durchlaufen wurde, setze inkrementiere dmax um 1 und starte einen neuen Suchlauf

Sonst terminiere mit dem Ergebnis, dass keine Lösung existiert Die Suche wird also unter Umständen sehr oft wiederholt?!

Ja, aber die meisten Knoten haben immer die Tiefe des Lösungsknoten Es werden nur Knoten mit maximal der Tiefe des Lösungsknoten erzeugt –

vergleiche Breitensuche, dort werden für einen Teil der Knoten mit Tiefe n die Kindknoten erzeugt und in der FIFO-Schlange gespeichert

Daher ist iterative Tiefensuche schneller als Breitensuche!

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Iterativ fortschreitende Tiefensuche (iterative deepening dfs)

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck LübeckWittstock

Ha

mb

urg

Ro

sto

ck

Be

rlin

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Ha

mb

urg

Mü

nst

er

Ha

mb

urg

Ka

sse

l

Ma

gd

eb

urg

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Be

rlin

Ro

sto

ck

dmax =0

dmax =1

dmax =2

dmax =3

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Iterativ fortschreitende Tiefensuche vs. Breitensuche

Im Beispiel Iterative Tiefensuche (IDS):

3 * 2 Knoten der Tiefe 12 * 7 Knoten der Tiefe 21 * 6 Knoten der Tiefe 3

Breitensuche (BFS):1 * 2 Knoten der Tiefe 11 * 7 Knoten der Tiefe 21 * 16 Knoten der Tiefe 31 * 19 Knoten der Tiefe 4

Im Ergebnis hat IDS einige Knoten mehrfach erzeugt aber insgesamt nur 26 Knoten im Vergleich zu 44 Knoten bei Breitensuche erzeugt!

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Bidirektionale Suche (bidirectional search)

Suche sowohl vom Startzustand Richtung Zielzustand als auch vom Zielzustand Richtung Startzustand

Reduziert die Suchtiefe und damit die Zeit Aber

Oft existieren mehrere Zielzustände (Schach-Matt-Positionen) Die Vorgängerzustände lassen sich oft nicht einfach berechnen

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Bidirektionale Suche (bidirectional search)

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck LübeckWittstock

Berlin

Wittstock Magdeburg Leipzig Dresden

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Kriterien zur Bewertung von Lösungsstrategien

Vollständigkeit (completeness): wenn es eine Lösung gibt, sollte der Algorithmus sie auch finden.

Optimalität (otimality): die vom Algorithmus gefunden Lösung ist hinsichtlich eine Bewertungsfunktion (Kosten) optimal

Zeitkomplexität (time complexity): die benötigte Rechenzeit, als Anzahl der insgesamt betrachteten Knoten

Speicherkomplexität (space complexity): der zur Abarbeitung benötigte Platz (die Anzahl der gleichzeitig im Speicher befindlichen Knoten)

Nachfolgend gilt: b ist der maximale Verzweigungsgrad im Baum d ist die Tiefe des (ersten) Zielknotens m ist die maximale Tiefe im Baum (= Höhe des Baumes) C sind Kosten der optimalen Lösung e sind die minimalen Kosten für einen Zustandsübergang

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Breitensuche

Vollständigkeit: ja, falls es zu jedem Knoten endlich viele Nachfolger gibt

Optimalität: ja, falls die Kosten für Zustandübergänge immer gleich sind

Zeitkomplexität: O(b(d+1)) Im worst case ist die Lösung der letzte Knoten der Tiefe d, d.h. es gibt

b Knoten der Tiefe 1, b2 Knoten der Tiefe 2 … bd

Knoten der Tiefe d es werden außerdem (bd-1)*b = bd+1-b Knoten der Tiefe d+1 erzeugt und in

die FIFO-Schlange geschrieben Speicherkomplexität: O(b(d+1))

In der Schlange befinden sich im worst case die (bd-1)*b Knoten die bei der Betrachtung der Knoten mit Tiefe d erzeugt werden

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Kostenbasierte Suche

Vollständigkeit: ja, falls es zu jedem Knoten endlich viele Nachfolger gibt und die Kosten

immer > ε > 0 sind Optimalität:

Ja, falls alle Kosten ≥ 0 Zeitkomplexität: O(b(C/e))

Anzahl der Knoten nicht abhängig von der Tiefe des Zielknotens im Baum, im worst case wird ein Baum der Tiefe C/e vor der optimalen Lösung betrachtet

Speicherkomplexität: O(b(C/e)) Im worst case müssen die Knoten mit der Tiefe C/e gespeichert werden

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Kostenbasierte Suche

>> ed'

d = 2C = Kosten auf dem Pfad

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Tiefensuche

Vollständigkeit: nein, unendliche Pfade möglich

Optimalität: nein, erste gefundene Lösung muss nicht optimal sein

Zeitkomplexität: O(bm) Im worst case werden alle Knoten durchlaufen, insbesondere auch der am

tiefsten im Baum liegende Knoten mit der Tiefe m m kann unendlich sein, siehe oben!

Speicherkomplexität: O(bm) Wenn alle Geschwisterknoten auf dem Weg zum tiefsten Knoten erzeugt

und gespeichert werden, werden auf m Ebenen je maximal b Knoten erzeugt

Falls die Knoten mit Backtracking – es wird nur jeweils ein Nachfolger-knoten je Knoten generiert, nur falls die Suche unterhalb des Nachfolgers erfolglos ist, wird der nächste generiert - durchlaufen werden : O(m)

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Tiefenbeschränkte Tiefensuche

Vollständigkeit: nein, Lösung ggf. durch Tiefenschranke abgeschnitten

Optimalität: nein, erste gefundene Lösung muss nicht optimal sein

Zeitkomplexität: O(bl) Siehe Tiefensuche, wobei l die maximale Tiefe gemäß Tiefenschranke

darstellt Speicherkomplexität: O(bl)

Siehe Tiefensuche, wobei l die maximale Tiefe gemäß Tiefenschranke darstellt

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Iterative Tiefensuche

Vollständigkeit: ja, falls es zu jedem Knoten endlich viele Nachfolger gibt

Optimalität: ja, falls die Kosten für Zustandsübergänge immer gleich sind

Zeitkomplexität: O(bd) Es werden keine Knoten der Tiefe d+1 betrachtet (wegen Schranke)! Knoten der Tiefe d werden 1 x betrachtet, Knoten der Tiefe (d-1) 2 x, usw.,

aber 2*b(d-1) , d.h. O(bd) (wegen b>=2, 2*bd/b …)

Ist günstiger als Breitensuche (!) und ohne weitere a priori – Informationen die bevorzugte uninformierte Suchstrategie

Speicherkomplexität: O(bd) Siehe Tiefensuche / tiefenbeschränke Tiefensuche

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Bidirektionale Suche

Vollständigkeit: hängt von der Suchstrategie ab, ja falls Breitensuche

Optimalität: hängt von der Suchstrategie ab, ja falls Breitensuche

Zeitkomplexität: O(b(d/2)) Bei Breitensuche

Speicherkomplexität: O(b(d/2)) Bei Breitensuche

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vergleich der betrachteten Suchstrategien Fazit: die geeignete Suchstrategie hängt von der Problemstellung

ab, u.a.: Ist die maximale Tiefe des Zielknotens bekannt? Ist der Suchbaum endlich? Sind Zustandübergänge mit Kosten verbunden? Gibt es wenige / viele Zielknoten? Lassen sich die Vorgängerknoten (Elternknoten) effizient bestimmen?

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (DFS, depth first search)

Lübeck

Hamburg Rostock

Wittstock

BerlinHamburg

Wittstock

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (DFS, depth first search)

Lübeck

Hamburg Rostock

Wittstock

BerlinHamburg

= ?

= ?

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (DFS, depth first search)

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck LübeckWittstock

Ha

mb

urg

Be

rlin

Ro

sto

ck

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Ha

mb

urg

Mü

nst

er

Ha

mb

urg

Ka

sse

l

Ma

gd

eb

urg

Ha

mb

urg

Ro

sto

ck

Ha

mb

urg

Be

rlin

Ro

sto

ck

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (DFS, depth first search)

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck LübeckWittstock

Ha

mb

urg

Be

rlin

Ro

sto

ck

Ha

mb

urg

Ha

mb

urg

Mü

nst

er

Ha

mb

urg

Ka

sse

l

Ma

gd

eb

urg

Ha

mb

urg

Be

rlin

Ro

sto

ck

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (DFS, depth first search)

Lübeck

Hamburg Rostock

Kiel WittstockBremen HannoverLübeck LübeckWittstock

Ha

mb

urg

Be

rlin

Ro

sto

ck

Ha

mb

urg

Ha

mb

urg

Mü

nst

er

Ha

mb

urg

Ka

sse

l

Ma

gd

eb

urg

Ha

mb

urg

Be

rlin

Ro

sto

ck

? ?

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (GRAPH SEARCH)

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

Open List (SUCHGRAPH) Closed List (HISTORY)

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (GRAPH SEARCH)

Open List (SUCHGRAPH) Closed List (HISTORY)

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen (GRAPH SEARCH)

Open List (SUCHGRAPH) Closed List (HISTORY)

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

Hannover

Rostock

Hamburg

Lübeck

Bremen

Kiel

Magdeburg

Leipzig

Münster

Kassel

Dresden

Wittstock

Berlin

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Vermeidung von Wiederholungen

Zyklen im Zustandsgraphen führen zu wiederholten Abfolgen von Knoten im Suchbaum und zu endlosen Pfaden

Idee: bereits betrachtete Zustände merken und nicht erneut betrachten Beispiel 1: Tiefensuche speichert alle Knoten auf dem Pfad

Bei jedem neuen Knoten wird getestet, ob Knoten mit dem gleichen Zustand bereits betrachtet

Ggf. wird der Knoten nicht weiter betrachtet Beispiel 2: alle bereits betrachteten Zustände werden in einer

entsprechenden Datenstruktur (Hashset) gespeichert Reduziert Suchbaum ggf. erheblich Bei allen Suchstrategien von Vorteil Erfordert ggf. sehr viel Speicher

KI Übung SoSe 2006

Suche nach einer „intelligenten“ Lösung Weitere Beispiele

Touren-Probleme: Zustände enthalten nicht nur eine bestimmte Stadt als Ziel, sondern die Menge der besuchten Städte – Ziel ist eine Tour über alle Städte

Spezialfall: Traveling Salesman Problem (TSP): jede Stadt darf nur ein Mal besucht werden

Roboter-Navigation: Bewegungen des Roboters im Raum, so dass ein beliebiger Zielzustand erreicht wird

Automatische Montageplanung (assembly planning): Suche nach einer Abfolge von Montageschritten, die das fertige Produkt erzeugen

Suche im Internet