Graphen	Tiefensuche Breitensuche Heuristische Suche Haus des Nikolaus Bauer,Kohl,Wolf,Ziege Missionare und Kannibalen Pfad: Startseite / Fächer / Informatik / Prolog / Graphen / Bauer,Kohl,Wolf,Ziege
Autor: mk 03.04.2007 12:43:00 2131	Bauer, Kohl, Wolf und Ziege

Problem

Ein Bauer kommt mit Kohlkopf, Wolf und Ziege an einen Fluss, den er überqueren will. Es gibt ein Boot, das nur Platz für zwei hat und das nur der Bauer rudern kann. Wenn Ziege und Kohlkopf unbeaufsichtigt zusammen sind, so frisst die Ziege den Kohl. Ebenso wird der Wolf die Ziege fressen, wenn der Bauer nicht aufpasst.
Wie kommt die Gesellschaft heil ans andere Ufer?

% ein Zustand ist z.B. [[b, k, w], [z]] , (Bauer, Kohlkopf, Wolf | Ziege)

% nur der Bauer kann rudern, das Boot hat höchsten Platz für zwei
ueberfahrt([b]).
ueberfahrt([b,w]).
ueberfahrt([b,z]).
ueberfahrt([b,k]).

% Fahrt von links nach rechts
next([L1,R1],[L2,R2]):-ueberfahrt(Ue),subset(Ue,L1),subtract(L1,Ue,H1),
                       sort(H1,L2),L2 \= [k,w,z],L2 \= [w,z],L2 \= [k,z],
                       subtract([b,k,w,z],L2,H2),sort(H2,R2),
                       R2 \= [k,w,z],R2 \= [w,z],R2 \= [k,z].

% Fahrt von rechts nach links

Aufgaben

• Erläutere das Prädikat next.
• Ergänze das Prädikat next für den Fall einer Fahrt von rechts nach links.
• Ermittle mit Hilfe des Prolog-Programms den Graphen des Problems.
• Ermittle mit Tiefensuche eine Lösung.
• Ermittle mit Breitensuche eine Lösung.

Graph

Links

• www.plastelina.net

lokal