Anwendungen der Planung

Planung

Planung

Planung

PlanungPlanung

Planung

Planung

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

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 2

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

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 3

Anwendung Ziege, Kohlkopf und Wolf

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

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 4

Anwendung Ziege, Kohlkopf und Wolf

Notation: F▲

1:

2:F▲

ZF▼

Aktionsfolge:

Zustand:Z = uK = oW = oF = u

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 5

Anwendung Ziege, Kohlkopf und Wolf

Einschränkungen

Verbotene Zustände:

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

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 6

Anwendung Ziege, Kohlkopf und Wolf

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...

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 7

Anwendung Ziege, Kohlkopf und Wolf

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:

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 8

Anwendung Breitensuche: Ziege, Kohlkopf und Wolf

Suchbaum Z = oK = oW = oF = o

Z = oK = oW = oF = u

Z = uK = oW = oF = u

Z = oK = uW = oF = u

Z = oK = oW = uF = u

F▼

ZF▼ KF▼

WF▼

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 9

Anwendung Breitensuche

Suchbaum Z = oK = oW = oF = o

Z = oK = oW = oF = u

Z = uK = oW = oF = u

Z = oK = uW = oF = u

Z = oK = oW = uF = u

F▼

ZF▼ KF▼

WF▼

Verbotene Zustände

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 10

Anwendung Breitensuche

Suchbaum Z = oK = oW = oF = o

Z = oK = oW = oF = u

Z = uK = oW = oF = u

Z = oK = uW = oF = u

Z = oK = oW = uF = u

F▼

ZF▼ KF▼

WF▼

Verbotene Zustände

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 11

Anwendung Breitensuche

Suchbaum Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼

ZF▲ F▲

Z = oK = oW = oF = o

Z = uK = oW = oF = o

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 12

Anwendung Breitensuche

Suchbaum Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼

ZF▲ F▲

Z = oK = oW = oF = o

Z = uK = oW = oF = o

Dieser Zustand ist identisch mit dem Anfangszustand.

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

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 13

Anwendung Breitensuche

Suchbaum Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼

ZF▲ F▲

Z = oK = oW = oF = o

Z = uK = oW = oF = o

Dieser Zustand ist identisch mit dem Anfangszustand.

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 14

Anwendung Breitensuche

Suchbaum

Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

KF▼

F▼

WF▼Z = uK = oW = oF = u

Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼

F▲

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 15

Anwendung Breitensuche

Suchbaum

Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

KF▼

F▼

WF▼Z = uK = oW = oF = u

Dieser Zustand wurde bereits expandiert

Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼

F▲

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 16

Anwendung Breitensuche

Suchbaum Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

KF▼

F▼

WF▼Z = uK = oW = oF = u

Dieser Zustand wurde bereits expandiert

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 17

Anwendung Breitensuche

Suchbaum Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

KF▼ WF▼

Z = uK = uW = oF = o

Z = uK = oW = oF = o

Z = oK = uW = oF = o

F▲

ZF▲

KF▲

Bereits expandierter Zustand

Verbotener Zustand

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 18

Anwendung Breitensuche

Suchbaum Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

KF▼ WF▼

Z = uK = uW = oF = o

Z = uK = oW = oF = o

Z = oK = uW = oF = o

Z = uK = oW = uF = o

Z = uK = oW = oF = o

Z = oK = oW = uF = o

F▲

ZF▲

KF▲ F▲

ZF▲

WF▲

Bereits expandierter Zustand

Verbotener Zustand

Bereits expandierter Zustand

Verbotener Zustand

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 19

Anwendung Breitensuche

Suchbaum Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

KF▼ WF▼

Z = uK = uW = oF = o

Z = uK = oW = oF = o

Z = oK = uW = oF = o

Z = uK = oW = uF = o

Z = uK = oW = oF = o

Z = oK = oW = uF = o

F▲

ZF▲

KF▲ F▲

ZF▲

WF▲

Bereits expandierter Zustand

Verbotener Zustand

Verbotener Zustand

Bereits expandierter Zustand

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 20

Anwendung Breitensuche

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

Z = uK = oW = oF = u

ZF▼

F▲

Z = uK = oW = oF = o

Z = uK = uW = oF = u

Z = uK = oW = uF = u

Z = oK = uW = oF = o

Z = oK = oW = uF = o

Z = oK = uW = uF = u

Z = oK = uW = uF = u

Z = oK = uW = uF = o

Z = oK = uW = uF = o

Z = uK = uW = uF = u

F▲

WF▼ZF▼

KF▼

ZF▲

ZF▼

F▲

ZF▼

ZF▲

WF▼

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 21

Anwendung Breitensuche

Die entstehenden Pläne

Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼ F▲

Z = uK = oW = oF = o

Z = uK = oW = uF = u

ZF▲WF▼

Z = oK = oW = uF = o

Z = oK = uW = uF = u

Z = oK = uW = uF = o

F▲KF▼ ZF▼

Z = uK = uW = uF = u

Z = oK = oW = oF = o

Z = uK = oW = oF = u

ZF▼ F▲

Z = uK = oW = oF = o

Z = uK = uW = oF = u

ZF▲ZF▼

Z = oK = uW = oF = o

Z = oK = uW = uF = u

Z = oK = uW = uF = o

F▲WF▼ ZF▼

Z = uK = uW = uF = u

Lehrstuhl für Operations Research und Systemtheorie Planen Folie 22

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