 |
|||
| HSG |
|
Problem
Drei Missionare stehen mit drei Kannibalen am Ufer eines Flusses. Um ihn zu überqueren, können sie ein Boot benutzen, das
aber höchstens zwei (drei) Personen zugleich trägt. Bei der Überquerung dürfen die Kannibalen nie in der Überzahl sein,
weder im Boot noch an einem Ufer, da sie sonst ihren alten Sitten folgend den bzw. die Missionare verspeisen.
Wie kommen die Missionare und die Kannibalen an das andere Ufer?
Vorschlag eines Prolog-Programms zur Lösung
/* [[2,3],[1,0,b]] beschreibt den Zustand, dass am linken Ufer 2 Missionare und
3 Kannibalen sind, am rechten Ufer 1 Missionar und 0 Kannibalen und das Boot */
/* ueberfahrt(2,1). beschreibt eine Überfahrt mit 2 Missionaren und
einem Kannibalen */
ueberfahrt(1,0).
ueberfahrt(1,1).
ueberfahrt(2,0).
ueberfahrt(0,1).
ueberfahrt(0,2).
% ueberfahrt(2,1).
%Überfahrt von links nach rechts
next([[Ml1,Kl1,b],[Mr1,Kr1]],[[Ml2,Kl2],[Mr2,Kr2,b]]):-
ueberfahrt(M,K),Ml1-M >= 0,Ml2 is Ml1-M,Kl1-K >= 0,
Kl2 is Kl1-K,Mr2 is Mr1+M,Kr2 is Kr1+K,
(Ml1 >= Kl1;Ml1 =:= 0),(Mr1 >= Kr1;Mr1 =:= 0),
(Ml2 >= Kl2;Ml2 =:= 0),(Mr2 >= Kr2;Mr2 =:= 0).
%Überfahrt von rechts nach links
next([[Ml1,Kl1],[Mr1,Kr1,b]],[[Ml2,Kl2,b],[Mr2,Kr2]]):-
ueberfahrt(M,K),Ml2 is Ml1+M,Kl2 is Kl1+K,
Mr1-M >= 0,Mr2 is Mr1-M,Kr1-K >= 0,Kr2 is Kr1-K,
(Ml1 >= Kl1;Ml1 =:= 0),(Mr1 >= Kr1;Mr1 =:= 0),
(Ml2 >= Kl2;Ml2 =:= 0),(Mr2 >= Kr2;Mr2 =:= 0).
breitensuche(Start,Ziel,Loesung):-breitensuche([Start],[],Ziel,Loesung).
breitensuche(Pfad,Pfade,Ziel,Loesung):-Pfad=[Ziel|_],Pfad=Loesung,!.
breitensuche(Pfad,Pfade,Ziel,Loesung):-Pfad=[KnotenA|_],
findall([KnotenN|Pfad],
(next(KnotenA,KnotenN),not(member(KnotenN,Pfad))),
GefundenePfade),
append(Pfade,GefundenePfade,NeuePfade),
NeuePfade=[PfadN|RestPfade],
breitensuche(PfadN,RestPfade,Ziel,Loesung).
Aufgaben
- Erläutere das Prädikat next.
- Ermittle mit Hilfe des Prolog-Programms den Graphen des Problems.
- Ermittle mit Tiefensuche eine Lösung.
- Ermittle mit Breitensuche eine Lösung.
Mögliche Lösung
Bitte beachten, dass obige Breitensuche den Lösungsweg umgedreht ausgibt.
L = [[[3, 3, b], [0, 0]], [[2, 2], [1, 1, b]], [[3, 2, b], [0, 1]], [[3, 0], [0, 3, b]], [[3, 1, b], [0, 2]],
[[1, 1], [2, 2, b]], [[2, 2, b], [1, 1]], [[0, 2], [3, 1, b]], [[0, 3, b], [3, 0]], [[0, 1], [3, 2, b]],
[[1, 1, b], [2, 2]], [[0, 0], [3, 3, b]]]
- Ein Missionar und ein Kannibale fahren ans andere Ufer.
- Der Missionar fährt allein zurück.
- Die zwei verbleibenden Kannibalen fahren ans andere Ufer.
- Ein Kannibale fährt zurück.
- Zwei Missionare fahren ans andere Ufer.
- Ein Missionar und ein Kannibale fahren zurück.
- Zwei Missionare fahren ans andere Ufer.
- Ein Kannibale fährt zurück.
- Zwei Kannibalen fahren ans andere Ufer.
- Ein Missionar fährt zurück.
- Der Missionar und der Kannibale fahren ans andere Ufer.
Links
- www.plastelina.net - zum Nachspielen der Lösung
