|
Autor: mk 12.08.2007 10:23:40 2927 |
|
||
| Graphen |
Tiefensuche
Breitensuche
Heuristische Suche
Haus des Nikolaus
Bauer,Kohl,Wolf,Ziege
|
|
|
Missionare und Kannibalen |
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?
/* [[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).
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]]]
