Einführung in die Informatik I Prof. Dr. Bernd Schmidt Lehrstuhl für Operations Research und Systemtheorie, Universität Passau Planung

Einführung in die Informatik I

Prof. Dr. Bernd SchmidtLehrstuhl für Operations Research und Systemtheorie, Universität Passau

Planung

Planung

Planung

Planung

Planung

Planung

Lehrstuhl für Operations Research und Systemtheorie Planung Folie 2

Gliederung

1. Einführung: Probleme

2. Definitionen: Zustand

Plan

3. Suchstrategien: Breitensuche

Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche

4. Planung: Bedingungsabhängige Aktionen

Verbotene Zustände

5. Anwendung: Beispiel Ziege, Kohlkopf und Wolf


Gliederung



Plan


Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche


Verbotene Zustände



Einführung Labyrinth

Aufgabe: finde einen Weg von einem gegebenen Startpunkt zu einem Ausgang


Einführung Aktionsrepertoire und Strategie: Labyrinth

Die Knoten sind Punkte, an denen sich der Agent zu bestimmten Zeitpunkten befindet.

An jedem Knoten stehen dem Agenten unterschiedliche Handlungsoptionen zur Verfügung.

Mögliche Aktionen:

gehe

Strategie:

versuche

1: links

2: vorwärts

3: zurück

4: rechts

vorwärts

rechtslinks

zurück



1. Versuch:



2. Versuch:



3. Versuch:


Einführung Ziege, Kohlkopf und Wolf

Aufgabe:

- Fährmann muss Ziege, Kohlkopf und Wolf von einem Ufer zum anderen transportieren

Regeln:- Fähre: Fährmann + ein Passagier

- bleiben Ziege und Kohlkopf an einem Ufer zurück, so wird der Kohlkopf gefressen

- bleiben Wolf und Ziege an einem Ufer zurück, so wird die Ziege gefressen

Notation:

- Fährmann fährt alleine nach oben:

- Wolf und Fährmann fahren nach unten:

F▲

WF▼

Wolf:

Ziege:

Kohlkopf:

Z

K

W

Bewegung der Fähre: ▲, ▼

Beispiele:

Fährmann: F



1. Versuch:

ZF▼Notation:

ZF▼1:

Aktionsfolge:



1. Versuch:

Notation: F▲

1:

2:F▲

ZF▼

Aktionsfolge:



1. Versuch:

Notation: KF▼

1:

2:F▲

ZF▼

3:KF▼

Aktionsfolge:



1. Versuch:

Notation: F▲

1:

2:F▲

ZF▼

3:KF▼

4:F▲

Aktionsfolge:



2. Versuch:

ZF▼Notation:

ZF▼1:

Aktionsfolge:



2. Versuch:

Notation: F▲

1:

2:F▲

ZF▼

Aktionsfolge:



2. Versuch:

Notation: KF▼

1:

2:F▲

ZF▼

3:KF▼

Aktionsfolge:



2. Versuch:

Notation: ZF▲

1:

2:F▲

ZF▼

3:KF▼

4:ZF▲

Aktionsfolge:



2. Versuch:

Notation: WF▼

1:

2:F▲

ZF▼

3:KF▼

4:ZF▲

5:WF▼

Aktionsfolge:



2. Versuch:

Notation: F▲

1:

2:F▲

ZF▼

3:KF▼

4:ZF▲

5:WF▼

6:F▲

Aktionsfolge:



2. Versuch:

Notation: ZF▼

1:

2:F▲

ZF▼

3:KF▼

4:ZF▲

5:WF▼

6:F▲

7:ZF▼

Aktionsfolge:



A Z1

Z5

Z4

Z3

Z2

Z6 E

ZF▼ F▲ KF▼

ZF▲

WF▼ F▲ ZF▼

Plan


Gliederung



Plan


Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche


Verbotene Zustände



Ein Plan ist eine Abfolge von Aktionen, die einen Anfangszustand A durch Ausführung von Aktionen über Zwischenzustände Z in einen Endzustand E überführt.

A E

Definitionen Plan

Ein Zustand ist eine Menge von Zustandsvariablen.

Z A

Ex1=e1

x2=e2 .

..xn=en

Im Endzustand besitzen alle Zustandsvariablen den richtigen Wert.

x1= a1

x2= z1

...

xn= an

x1= z1

xn= zn

x2= a1

...

Anfangszustand

Zwischenzustand

Endzustand

Zustand der Umwelt vor Beginn der Abarbeitung des Plans

Zustand der nach Erreichen des Ziels eingenommen werden soll

ZF▼ F▲

KF▼

ZF▲ WF▼ F▲ ZF▼


Gliederung



Plan


Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche


Verbotene Zustände



Bewertungskriterien

- Vollständigkeit

Wird eine Lösung garantiert gefunden, wenn es eine gibt?

- Zeitkomplexität

Innerhalb welcher Schranken bewegt sich die Dauer zur Ermittlung eines Ergebnisses?

- Speicherkomplexität

Innerhalb welcher Schranken bewegt sich der Verbrauch an Speicherplatz?

- Optimalität (bzgl. der Pfadkosten)

Wird eine beste Lösung gefunden, wenn eine existiert?

Suchstrategien Bewertungskriterien


Suchstrategien Klassifikation

Klassifikation von Suchstrategien

- blinde Suche:

- Breitensuche

- Tiefensuche

- Uniform Cost Suche

- Tiefenbeschränkte Suche

- Informierte Suche:

- Greedy Suche

- A*- Suche

kein Wissen über die Richtung zum Ziel vorhanden

Zielrichtung ist bekannt, Verarbeitung in heuristischer Funktion


Suchstrategien Datenstrukturen

Datenstrukturen für Suchbäume

Knoten {

Zustand // Zustand, der dem Knoten entspricht

Mutterknoten // Verweis auf den erzeugenden Konten

Operator // erzeugender Operator

Tiefe

Pfadkosten // aufsummiert, beginnend am Anfangszustand

}

Kanten = Übergänge zwischen den Knoten

= Zustände

= Aktionen


Suchstrategien Netz aus Knoten und Kanten

Arad

Zerind

Oradea

Sibiu

Riminicu V.Timisoara

Lugoj

Mehadia

Fagaras

Pitesti

Dobreta

Craiova

UrziceniBucharest

Giurgiu

Hirsova

Vasuli

Iasi

Neamt

Eforie

KantenKnoten


Suchstrategien Wegsuche in Rumänien

Zerind

Sibiu

Timisoara

Arad

Oradea

Riminicu V.

Fagaras

Arad

ZerindSibiuTimisoara

Expandieren des Anfangszustandes:

Wie gelangt man zum Strassennetz?

Expandieren!

Alle möglichen Aktionen

ausführen, die von einem

Zustand aus ausführbar sind.

Beispiel:


Suchstrategien Blinde Suche: Wegsuche in Rumänien

Zerind

Sibiu

Timisoara

Arad

Oradea

Riminicu V.

Fagaras

Arad



Bewertung + Auswahl: Welcher Knoten soll als nächster expandiert werden?

Blinde Suche: alle drei Knoten sind gleichberechtigt


Suchstrategien Informierte Suche: Wegsuche in Rumänien

Zerind

Sibiu

Timisoara

Arad

Oradea

Riminicu V.

Fagaras

Arad



Bewertung + Auswahl: Welcher Knoten soll als nächster expandiert werden?

Informierte Suche: Zusatzinformation wird verarbeitet:

z.B. Sibiu liegt in Richtung Bucharest, daher Sibiu zuerst expandieren

N

S

OW


Suchstrategien Queue

Organisation der Daten

Eine Queue ist eine Warteschlange für zu expandierende Knoten.

Suchstrategien unterscheiden sich durch…

- …den Mechanismus, der die Reihenfolge zu expandierender Knoten festlegt

- …den Mechanismus, der entscheidet, an welcher Stelle die noch zu

expandierenden Knoten in die Queue eingereiht werden.

Queue

expandieren


Suchstrategien Queue

Organisation der Queue

- Wird ein Knoten expandiert, so werden die Tochterknoten am Ende der

Queue angehängt.

- Der expandierte Knoten wird aus der Queue entfernt.

- Die Queue wächst am hinteren Ende.

Queue

expandieren

d d d d+1 d+1

Tiefe d

Tiefe d+1


Suchstrategien Beispiel Breitensuche

Breitensuche: in einer Ebene werden die Knoten von links nach rechts aufgefüllt

1 2 3

4 5 6


Suchstrategien Breitensuche: Wegsuche in Rumänien

Arad

Zerind

Oradea

Sibiu

Riminicu V.Timisoara

Lugoj

Mehadia

Fagaras

Pitesti

Dobreta

Craiova

UrziceniBucharest

Giurgiu

Hirsova

Vasuli

Iasi

Neamt

Eforie

Aufgabe: finde einen Weg von Arad nach Bucharest


Suchstrategien Breitensuche: Wegsuche in Rumänien

Arad


QueueArad

1. Anfangsknoten mit Anfangszustand Arad

2. Nach der Expansion von Arad

Arad

QueueSibiu ZerindTimisoara

3. Nach der Expansion von Timisoara


AradQueue

Lugoj

Sibiu Zerind Lugoj


Suchstrategien Beispiel Tiefensuche

1 2 3 4 5

Tiefensuche: alle Knoten eines Pfades werden bis zur maximalen Tiefe expandiert

6 7 8


Suchstrategien Tiefensuche: Wegsuche in Rumänien

Arad

Timisoara

QueueArad

1. Anfangsknoten mit Anfangszustand Arad

2. Nach der Expansion von Arad

Arad

QueueTimisoara

3. Nach der Expansion von Timisoara

Timisoara

AradQueue

Lugoj

Lugoj


Suchstrategien Uniform Cost Suche

Uniform Cost Suche (Blinde Suche)

- Modifizierte Breitensuche

- Einführung von Pfadkosten direkter Verbindungen durch Pfadkostenmatrix

- Knoten mit den geringsten Pfadkosten werden zuerst expandiert

Arad Zerind Sibiu Timisoara ...

Arad 0 75 140 118 ...

Zerind 75 0 - - ...

Sibiu 140 - 0 - ...

Timisoara 118 - - 0 ...

... ... ... ... ... 0

Zusatzinformation: Pfadkostenmatrix




- Neu generierte Knoten werden derart eingefügt, dass die Knoten bezüglich

ihrer Pfadkosten aufsteigend sortiert sind.

expandieren

75 118 140

2

118 140 75

146

Queue

Zerind Sibiu Timisoara

Oradea

146

Timisoara Sibiu OradeaZerind


Suchstrategien Uniform Cost Suche: Wegsuche in Rumänien

Uniform Cost Suche

Arad QueueArad

QueueSibiuZerind Timisoara

Arad

Zerind 75Sibiu 140Timisoara 118

QueueSibiuTimisoara

Arad


Oradea 146

Oradea



Uniform Cost Suche

Arad


QueueSibiu Lugoj

Oradea 146

Oradea

Lugoj 229

Arad


QueueRiminicu V. Lugoj

Oradea 146

Oradea

Lugoj 229 Riminicu V. 220 Fagaras 239

Fagaras


Suchstrategien Greedy Suche

Greedy Suche

- Informierte Suche

- Bewertungsfunktion: Heuristik h: Knoten Int

ermittelt die (geschätzte) Entfernung eines Knotens (= Zustand)

zum Ziel

Expandieren von Knoten

- Expandiert wird der Knoten, dem die geringste geschätzte Entfernung zum Ziel

zugeschrieben wird.

Eigenschaften

- Nicht vollständig

- Nicht optimal


Suchstrategien Greedy Suche

Greedy Suche

Arad 366 QueueArad


QueueZerindTimisoara

Arad


Oradea

Arad


Oradea 380 Arad 366Fagaras 178Riminicu V. 193

Fagaras Riminicu V. Arad


Suchstrategien A*- Suche

A*- Suche

- Kombination von Uniform Cost Suche und Greedy Suche

- Bewertung der Knoten: Heuristik h(n) = f(n) + g(n)

- Dabei: f(n) = Summe der Strassenkilometer (Arad Ortn) (Uniform Cost Suche)g(n) = Luftliniendistanz (Ortn Bucharest) (Greedy- Suche)

Eigenschaften

- Vollständig.

- Optimal.


- Neu generierte Knoten werden derart eingefügt, dass die Knoten bezüglich

ihrer Pfadkosten aufsteigend sortiert sind- Analog zur Uniform Cost Suche, Greedy- Suche


Suchstrategien A*- Suche

A*- Suche 0 Arad 366

366

QueueArad


Arad

75 Zerind 374

449

140 Sibiu 253

393

118 Timisoara 329

447

QueueZerindTimisoara Oradea

146 Oradea 380

526

239 Fagaras 178

417

220 Riminicu V. 193

413

FagarasRiminicu V. Arad

280 Arad 366

646

Arad

75 Zerind 374

449

140 Sibiu 253

393

118 Timisoara 329

447


Gliederung



Plan


Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche


Verbotene Zustände



Planung Zusammenschau

• Anfangszustand A, Endzustand E• Zustandsmenge Z• Aktionsmenge O

• Einschränkungen– Bedingungsabhängige Aktionen– Verbotene Zustände

…a1 an

A E

Ein Plan ist eine Abfolge von Aktionen, die einen Anfangszustand durch Ausführung von Aktionen in einen Endzustand überführt.


Planung Einschränkungen

Einschränkungen

Verbotene Zustände- Dürfen durch Ausführung von Aktionen zu keiner Zeit eingenommen werden

A Z1 Z4Z3Z2ZF▼ F▲ KF▼ F▲

Verbotener Zustand:

Fährmann lässt Ziege und

Kohlkopf am selben Ufer zurück


Planung Einschränkungen

Bedingungsabhängige Aktionen

- Dürfen nur ausgeführt werden, wenn alle Vorbedingungen erfüllt sind, die

an die Aktion gebunden sind.

Einschränkungen

Notation

Boot obenBedingung(en):

(Fähre runter)

Bedingungen werden an Aktion gebunden

F▼

Boot oben

F▼Aktion: (Fähre runter)


Planung Breitensuche: Beispiel

Beispiel: arithmetische Umformung

A = 1

B = 2

C = 3

…

Aktionsmenge O:

A = 10

B = 5

C = 6

Startzustand Zielzustand

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 6

B = 6

C = 4

A = 9

B = 7

C = 5

Verbotene Zustände:


Planung Breitensuche: Beispiel

Beispiel: arithmetische UmformungA = 1

B = 2

C = 3

Aktionsauswahl:A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5


Planung Breitensuche: Bedingungsabhängige Aktionen


B = 2

C = 3


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 4

B = 3

C = 4

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 6

B = 6

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5


A = 6

B = 6

C = 4

Planung Breitensuche: Verbotene Zustände


B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

Verbotener Zustand

C > 3

A=A+2

B=B+3

C=C

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5


A = 6

B = 6

C = 4



B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

Verbotener Zustand

C > 3

A=A+2

B=B+3

C=C

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

A = 5

B = 0

C = 5


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 5

B = 4

C = 4

A = 5

B = 0

C = 5


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 5

B = 4

C = 4

A = 5

B = 0

C = 5

A = 9

B = 7

C = 5

C >3

A=A+2

B=B+3

C=C


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 5

B = 4

C = 4

A = 5

B = 0

C = 5

A = 9

B = 7

C = 5

C >3

A=A+2

B=B+3

C=C Verbotener Zustand


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 5

B = 4

C = 4

A = 5

B = 0

C = 5

A = 9

B = 7

C = 5

C >3

A=A+2

B=B+3

C=C Verbotener Zustand


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 5

B = 4

C = 4

A = 5

B = 0

C = 5

A = 10

B = 5

C = 6

A > 0

A=A+3

B=B+1

C=C+1


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5




B = 2

C = 3

A = 4

B = 3

C = 4

A = 3

B = 1

C = 4

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1


A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B- 1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A > 0

A=A+3

B=B+1

C=C+1

A = 6

B = 2

C = 5

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

B < 3

A=A+2

B=B-1

C=C+1

C > 3

A=A+2

B=B+3

C=C

A = 5

B = 4

C = 4

A = 5

B = 0

C = 5

A = 10

B = 5

C = 6

A > 0

A=A+3

B=B+1

C=C+1

Zielzustand erreicht


A = 6

B = 6

C = 4

A = 9

B = 7

C = 5


Gliederung



Plan


Tiefensuche

Uniform Cost Suche

Greedy- Suche

A*- Suche


Verbotene Zustände



Anwendung Ziege, Kohlkopf und Wolf

Notation:

Wolf:

Ziege:

Kohlkopf:

Z

K

W

Bewegung der Fähre: ▲, ▼

Startzustand:Z = oK = oW = oF = o

Erinnerung: Weder Ziege und Kohlkopf, noch Ziege und Wolf dürfen vom Fährmann am selben Ufer zurückgelassen werden!

Fährmann: F



Modellierung der Zustände

Z K W FZ K W FZ K F WZ K W FZ W F KZ W K FZ F K WZ K W F

K W F ZK W Z FK F Z WK Z W F

W F Z KW Z K F

F Z K WZ K W F

Ôben o Unten u

Zustände:

Start-Zustand

End-Zustand

Z = oK = oW = oF = o

Z = uK = uW = uF = u

Z = oK = uW = uF = o



Notation: F▲

1:

2:F▲

ZF▼

Aktionsfolge:

Zustand:Z = uK = oW = oF = u



Einschränkungen


Z = oK = oW = oF = u

Z = oK = uW = oF = u

Z = oK = oW = uF = u

Z = uK = uW = oF = o

Z = uK = oW = uF = o

Alle an einem Ufer, ohne Fährmann

Ziege und Wolf oben, Fährmann unten

Ziege und Wolf unten, Fährmann oben

Ziege und Kohlkopf oben, Fährmann unten

Ziege und Kohlkopf unten, Fährmann oben



Einschränkungen

Bedingungsabhängige Aktionen:

F▲

Fu

F ▼

Fo

W F▼

FoWo

Soll sich der Fährmann nach oben bewegen, so muss sich die Fähre zuerst unten befinden…

...ebenso in die umgekehrte Richtung...

... soll er dabei einen Passagier transportieren, so muss sich dieser am selben Ufer wie die Fähre befinden...



Zustandsübergang

Z = uK = oW = oF = o

Z = uK = uW = oF = u

KF▼

FoKo

- Fährmann transportiert den Kohlkopf von oben nach unten

unter Einhaltung aller Bedingungen:


Anwendung Breitensuche: Ziege, Kohlkopf und Wolf

Suchbaum Z = oK = oW = oF = o


Z = uK = oW = oF = u



F▼

ZF▼ KF▼

WF▼


Anwendung Breitensuche






F▼

ZF▼ KF▼

WF▼

Verbotene Zustände








F▼

ZF▼ KF▼

WF▼

Verbotene Zustände





ZF▼

ZF▲ F▲







ZF▼

ZF▲ F▲



Dieser Zustand ist identisch mit dem Anfangszustand.

Ein Zustand, der bereits einmal expandiert wurde, muss nicht nochmals expandiert werden.





ZF▼

ZF▲ F▲



Dieser Zustand ist identisch mit dem Anfangszustand.



Suchbaum



Z = uK = oW = uF = u

KF▼

F▼

WF▼Z = uK = oW = oF = u



ZF▼

F▲



Suchbaum




KF▼

F▼


Dieser Zustand wurde bereits expandiert



ZF▼

F▲



Suchbaum Z = uK = oW = oF = o



KF▼

F▼


Dieser Zustand wurde bereits expandiert






KF▼ WF▼



Z = oK = uW = oF = o

F▲

ZF▲

KF▲

Bereits expandierter Zustand

Verbotener Zustand






KF▼ WF▼






Z = oK = oW = uF = o

F▲

ZF▲

KF▲ F▲

ZF▲

WF▲


Verbotener Zustand


Verbotener Zustand






KF▼ WF▼







F▲

ZF▲

KF▲ F▲

ZF▲

WF▲


Verbotener Zustand

Verbotener Zustand




Lösung Z = oK = oW = oF = o


ZF▼

F▲






Z = oK = uW = uF = u





F▲

WF▼ZF▼

KF▼

ZF▲

ZF▼

F▲

ZF▼

ZF▲

WF▼



Die entstehenden Pläne



ZF▼ F▲



ZF▲WF▼




F▲KF▼ ZF▼




ZF▼ F▲



ZF▲ZF▼




F▲WF▼ ZF▼



Zusammenfassung

Z0 Z1 Z6 EFZ▼ F▲ FZ▼

…

Definitionen:

Zustände, Aktionen, Pläne

Zerind

Sibiu

Timisoara

Arad

Oradea

Riminicu V.

Fagaras

N

S

OW

Suchstrategien:

Breitensuche, Tiefensuche, Uniform Cost, Greedy- Suche, A*- Suche

A = 6

B = 6

C = 4

A = 4

B = 3

C = 4

Verbotener Zustand

C > 3

A=A+2

B=B+3

C=C

A = 7

B = 4

C = 5

A > 0

A=A+3

B=B+1

C=C+1

Planung:

Bedingungsabhängige Aktionen, verbotene Zustände

Anwendung:

Das Ziege- Kohlkopf- Wolf- Problem mit Breitensuche

Documents

Einführung in die Informatik I Prof. Dr. Bernd Schmidt Lehrstuhl für Operations Research und Systemtheorie, Universität Passau Planung