Das Missionare und Kannibalen Problem in Prolog

save [missionare.pl]

__________________________________________________________________


/*
   ----------------------------------------------------------------
      Opwis, K. & Ploetzner, R. (1996). Kognitive Psychologie
        mit dem Computer: Ein Einfuehrungskurs zur Simulation 
        geistiger Leistungen mit Prolog. 
        Heidelberg: Spektrum Akademischer Verlag.
 
      Kapitel 2.4: Suche in implizit definierten Suchraeumen
   ----------------------------------------------------------------
*/

% tiefensuche/3
% Aufruf der Tiefensuche 

tiefensuche(Start,Ziel,Loesung) :-
   tiefe([[Start]],Ziel,Pfad),
   reverse(Pfad,Loesung).

% Prueft, ob ein Loesungsweg vorliegt

tiefe([[Ziel|Sequenz]|_],Ziel,[Ziel|Sequenz]).

% Expandiert einen Zustand und ueberprueft die Nachfolger sukzessive 
% in der Reihenfolge, in der sie gefunden wurden.

tiefe([Weg|Alternativen],Ziel,Pfad) :-
   nachfolgepfade(Weg,Nachfolgepfade),
   append(Nachfolgepfade,Alternativen,Suchliste),
   tiefe(Suchliste,Ziel,Pfad).

% breitensuche/3
% Aufruf der Breitensuche 

breitensuche(Start,Ziel,Loesung) :-
   breite([[Start]],Ziel,Pfad),
   reverse(Pfad,Loesung).

% Prueft, ob ein Loesungsweg vorliegt

breite([[Ziel|Sequenz]|_],Ziel,[Ziel|Sequenz]).

% Expandiert einen Zustand und fuegt die Nachfolger an das Ende der Liste 
% mit allen zu pruefenden Suchpfaden.

breite([Weg|Alternativen],Ziel,Pfad) :-
   nachfolgepfade(Weg,Nachfolgepfade),
   append(Alternativen,Nachfolgepfade,Suchliste),
   breite(Suchliste,Ziel,Pfad).

% nachfolgepfade/2 
% Expansion eines Zustands: Liefert alle zulaessigen, d.h. nicht 
% zu Zyklen fuehrenden Nachfolgezustaenden.

nachfolgepfade([Vorgaenger|Zustaende],Nachfolgepfade) :-
   findall([Nachfolger,Vorgaenger|Zustaende],
           (nachfolger(Vorgaenger,Nachfolger),
            not(member(Nachfolger,[Vorgaenger|Zustaende]))),
           Nachfolgepfade).

% nachfolger/2
% Liefert einen moeglichen Nachfolgezustand in drei Schritten:
% Schritt 1: Auswahl der im gegebenen Zustand moeglichen Bewegungen
% Schritt 2: Ausfuehrung der Bewegungen (Aktualisierung der Situation)
% Schritt 3: Pruefung, ob der resultierende Zustand ein im Sinne der Regeln 
%            zulaessiger Zustand ist.

nachfolger(Vorgaenger,Nachfolger) :-
    auswahl(Vorgaenger,Personen),
    aktualisiere(Vorgaenger,Personen,Nachfolger),
    zulaessig(Nachfolger).

/* Missionaren-und-Kannibalen Problem */

% auswahl/2
% Definiert die moeglichen Bewegungen entsprechend der Spielregeln

% Fall 1: moegliche Bewegung zweier Personen (zwei Missionare oder Kannibalen 
%         oder je ein Missionar und Kannibale) von links nach rechts

auswahl(mk(links,[M,K],_),[Person_1,Person_2]) :-
   append(M_1,_,M),
   append(K_1,_,K),
   append(M_1,K_1,[Person_1,Person_2]).

% Fall 2: moegliche Bewegung eines Missionars von links nach rechts

auswahl(mk(links,[M,_],_),[Missionar]) :-
   append([Missionar],_,M).

% Fall 3: moegliche Bewegung eines Kannibalen von links nach rechts

auswahl(mk(links,[_,K],_),[Kannibale]) :-
   append([Kannibale],_,K).

% Fall 4-6: Analog zu Fall 1-3, aber Bewegungen von rechts nach links

auswahl(mk(rechts,_,[M,K]),[Person_1,Person_2]) :-
   append(M_1,_,M),
   append(K_1,_,K),
   append(M_1,K_1,[Person_1,Person_2]).

auswahl(mk(rechts,_,[M,_]),[Missionar]) :-
   append([Missionar],_,M).

auswahl(mk(rechts,_,[_,K]),[Kannibale]) :-
   append([Kannibale],_,K).

/* Zustandsaktualisierung */

aktualisiere(mk(Boot_alt,L_alt,R_alt),Personen,mk(Boot,L,R)) :-
   akt_boot(Boot_alt,Boot),
   akt_ufer(Personen,Boot_alt,L_alt,R_alt,L,R).

% Aktualisierung der Position des Bootes

akt_boot(links,rechts).
akt_boot(rechts,links).

% Aktualisierung der Situation auf den beiden Ufern

akt_ufer([],_,L,R,L,R).

akt_ufer([m|Rest],links,[M_1,K_1],[M_2,K_2],L,R) :-
   append([m],M_1_neu,M_1),
   append([m],M_2,M_2_neu),
   akt_ufer(Rest,links,[M_1_neu,K_1],[M_2_neu,K_2],L,R).

akt_ufer([k|Rest],links,[M_1,K_1],[M_2,K_2],L,R) :-
   append([k],K_1_neu,K_1),
   append([k],K_2,K_2_neu),
   akt_ufer(Rest,links,[M_1,K_1_neu],[M_2,K_2_neu],L,R).

akt_ufer([m|Rest],rechts,[M_1,K_1],[M_2,K_2],L,R) :-
   append([m],M_2_neu,M_2),
   append([m],M_1,M_1_neu),
   akt_ufer(Rest,rechts,[M_1_neu,K_1],[M_2_neu,K_2],L,R).

akt_ufer([k|Rest],rechts,[M_1,K_1],[M_2,K_2],L,R) :-
   append([k],K_2_neu,K_2),
   append([k],K_1,K_1_neu),
   akt_ufer(Rest,rechts,[M_1,K_1_neu],[M_2,K_2_neu],L,R).

% zulaessig/1
% Pruefung, ob ein Zustand zulaessig ist.

zulaessig(mk(_,L,R)) :-
   not(illegal(L)),
   not(illegal(R)).

% illegal/1
% Ein Zustand ist unzulaessig, wenn auf einer der beiden Uferseiten 
% die Kannibalen in der Ueberzahl sind.

illegal([[m],[k,k|_]]).
illegal([[m,m],[k,k,k|_]]).


% Hilfspraedikat.
% member/2
% Prueft, ob ein Element in einer Liste enthalten ist.

member(Element,[Element|_]).

member(Element,[_|Rest]) :-
     member(Element,Rest).

% Hilfspraedikat.
% not/1
% Realisiert 'negation by failure'

not(Aussage) :-
   call(Aussage), !, fail.
not(_).

% Hilfspraedikat.
% reverse/2
% Dreht eine Liste um.

reverse(Liste_1,Liste_2) :-
     reverse(Liste_1,[],Liste_2).

% reverse/3
% Dreht eine Liste unter Nutzung einer Hilfsvariablen um.

reverse([Element|Rest],Akkumulator,Liste_2) :-
     reverse(Rest,[Element|Akkumulator],Liste_2).

reverse([],Liste,Liste).