/* Una possibile soluzione del Problema dei missionari e dei cannibali */ /* Strutture Dati: Riva_Sin: [_,_,_,_,_,_,_] Riva_Dx: [_,_,_,_,_,_,_] */ /* Funzioni di Servizio */ /* Verifica se la barca e' disponibile sulla riva opportuna */ is_boat([b|_]). is_boat([_|Coda]) :- is_boat(Coda). /* Cancella una persona dalla riva opportuna */ del(People,[People|Lista],Lista) :- !. del(People,[X|Lista],[X|Y]):- del(People,Lista,Y). /* Aggiunge una persona sulla riva opportuna */ %add(X,Lista,[X|Lista]). /* sortata per pogter confrontare gli stati - vedi dopo */ add(X,Lista,Sorted):-msort([X|Lista],Sorted), !. /* Restituisce il numero di persone presenti su una riva */ /* number_of(People,Riva,Numero) da fare */ number_of(_,[],0) :- !. number_of(People,[People|Resto],N1) :- !, number_of(People,Resto,N), N1 is N+1. number_of(People,[_|Resto],N) :- !, number_of(People,Resto,N). /* ********************************************************** */ /* Vincoli su ogno riva il numero di missionari deve essere <= di quello dei cannibali oppure sulla riva non ci sono missionari */ /* a seguito di spostamento di un "m" oppure un "c" */ vincolo_1(m,Da_Riva,A_Riva) :- number_of(m,Da_Riva,X), number_of(c,Da_Riva,Y), (X-1 =:= 0 ; X-1 >= Y), number_of(m,A_Riva,Z), number_of(c,A_Riva,T), (Z+1 =:= 0 ; Z+1 >= T), !. vincolo_1(c,Da_Riva,A_Riva) :- number_of(c,Da_Riva,X), number_of(m,Da_Riva,Y), (Y =:= 0 ;X-1 =< Y), number_of(c,A_Riva,Z), number_of(m,A_Riva,T), (T =:= 0 ; Z+1 =< T), !. /* a seguito di spostamento di due "m" oppure due "c" */ vincolo_2(m,Da_Riva,A_Riva) :- number_of(m,Da_Riva,X), number_of(c,Da_Riva,Y), (X-2 =:= 0 ; X-2 >= Y), number_of(m,A_Riva,Z), number_of(c,A_Riva,T), (Z+2 =:= 0 ; Z+2 >= T), !. vincolo_2(c,Da_Riva,A_Riva) :- number_of(c,Da_Riva,X), number_of(m,Da_Riva,Y), (Y =:= 0 ;X-2 =< Y), number_of(c,A_Riva,Z), number_of(m,A_Riva,T), (T =:= 0 ; Z+2 =< T), !. /* a seguito di spostamento di "mc" */ vincolo_3(Da_Riva,A_Riva) :- number_of(c,Da_Riva,X), number_of(m,Da_Riva,Y), (Y-1 =:= 0 ; X-1 =< Y-1), number_of(c,A_Riva,Z), number_of(m,A_Riva,T), (T+1 =:= 0 ; Z+1 =< T+1), !. /* ********************************************************** */ /* Spostamento delle persone */ /* un "m" oppure un "c" */ naviga_1_Sin_Dx(People,Riva_Sin1,Riva_Dx1,Riva_Sin3,Riva_Dx3) :- del(b,Riva_Sin1,Riva_Sin2), del(People,Riva_Sin2,Riva_Sin3), add(b,Riva_Dx1,Riva_Dx2), add(People,Riva_Dx2,Riva_Dx3). naviga_1_Dx_Sin(People,Riva_Sin1,Riva_Dx1,Riva_Sin3,Riva_Dx3) :- del(b,Riva_Dx1,Riva_Dx2), del(People,Riva_Dx2,Riva_Dx3), add(b,Riva_Sin1,Riva_Sin2), add(People,Riva_Sin2,Riva_Sin3). /* due "m" oppure due "c" */ naviga_2_Sin_Dx(People,Riva_Sin1,Riva_Dx1,Riva_Sin4,Riva_Dx4) :- del(b,Riva_Sin1,Riva_Sin2), del(People,Riva_Sin2,Riva_Sin3), del(People,Riva_Sin3,Riva_Sin4), add(b,Riva_Dx1,Riva_Dx2), add(People,Riva_Dx2,Riva_Dx3), add(People,Riva_Dx3,Riva_Dx4). naviga_2_Dx_Sin(People,Riva_Sin1,Riva_Dx1,Riva_Sin4,Riva_Dx4) :- del(b,Riva_Dx1,Riva_Dx2), del(People,Riva_Dx2,Riva_Dx3), del(People,Riva_Dx3,Riva_Dx4), add(b,Riva_Sin1,Riva_Sin2), add(People,Riva_Sin2,Riva_Sin3), add(People,Riva_Sin3,Riva_Sin4). /* una coppia "mc" */ naviga_3_Sin_Dx(Riva_Sin1,Riva_Dx1,Riva_Sin4,Riva_Dx4) :- del(b,Riva_Sin1,Riva_Sin2), del(m,Riva_Sin2,Riva_Sin3), del(c,Riva_Sin3,Riva_Sin4), add(b,Riva_Dx1,Riva_Dx2), add(m,Riva_Dx2,Riva_Dx3), add(c,Riva_Dx3,Riva_Dx4). naviga_3_Dx_Sin(Riva_Sin1,Riva_Dx1,Riva_Sin4,Riva_Dx4) :- del(b,Riva_Dx1,Riva_Dx2), del(m,Riva_Dx2,Riva_Dx3), del(c,Riva_Dx3,Riva_Dx4), add(b,Riva_Sin1,Riva_Sin2), add(m,Riva_Sin2,Riva_Sin3), add(c,Riva_Sin3,Riva_Sin4). /* ********************************************************** */ /* le mosse */ /* di un "m" oppure un "c" */ move_1_Sin_Dx(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2) :- is_boat(Riva_Sin1), number_of(People,Riva_Sin1,X), X >= 1, vincolo_1(People,Riva_Sin1,Riva_Dx1), naviga_1_Sin_Dx(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2). move_1_Dx_Sin(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2) :- is_boat(Riva_Dx1), number_of(People,Riva_Dx1,X), X >= 1, vincolo_1(People,Riva_Dx1,Riva_Sin1), naviga_1_Dx_Sin(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2). /* di due "m" oppure due "c" */ move_2_Sin_Dx(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2) :- is_boat(Riva_Sin1), number_of(People,Riva_Sin1,X), X >= 2, vincolo_2(People,Riva_Sin1,Riva_Dx1), naviga_2_Sin_Dx(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2). move_2_Dx_Sin(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2) :- is_boat(Riva_Dx1), number_of(People,Riva_Dx1,X), X >= 2, vincolo_2(People,Riva_Dx1,Riva_Sin1), naviga_2_Dx_Sin(People,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2). /* di una coppia "mc" */ move_3_Sin_Dx(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2) :- is_boat(Riva_Sin1), number_of(m,Riva_Sin1,X), X >= 1, number_of(c,Riva_Sin1,Y), Y >= 1, vincolo_3(Riva_Sin1,Riva_Dx1), naviga_3_Sin_Dx(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2). move_3_Dx_Sin(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2) :- is_boat(Riva_Dx1), number_of(m,Riva_Dx1,X), X >= 1, number_of(c,Riva_Dx1,Y), Y >= 1, vincolo_3(Riva_Dx1,Riva_Sin1), naviga_3_Dx_Sin(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2). /* ********************************************************** */ /* l' intero problema move(Riva_Sin,Riva_Dx,Soluzione) dove Riva_Sin,Riva_Dx rappresentano uno stato del problema. Nella chiamata iniziale saranno lo stato iniziale move termina quando si raggiunge lo stato finale oppure quando si raggiunge un limite di profondita` nella ricorsione. */ /* Raggiunta una soluzione - Stampa la lista delle mosse nell' ordine giusto */ move([],_,Soluzione) :- reverse(Soluzione,S),write(S),nl. /* Se la soluzione parziale supera il limite di Lim mosse fallisci. Questo provoca il backtracking e l' esplorazione di una altra parte dell' albero di ricerca quando ci sono piu` di Lim chiamate ricorsive (Il problema si risolve con 10). */ move(_,_,Soluzione) :- length(Soluzione,N), limite(Lim), N > Lim , !, fail. /* le possibili mosse da sinistra a destra */ move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_2_Sin_Dx(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['mm->'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_2_Sin_Dx(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['cc->'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_3_Sin_Dx(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['mc->'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_1_Sin_Dx(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['m->'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_1_Sin_Dx(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['c->'|Soluzione]). /* le possibili mosse da destra a sinistra */ move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_1_Dx_Sin(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['<-c'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_1_Dx_Sin(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['<-m'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_2_Dx_Sin(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['<-mm'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_2_Dx_Sin(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['<-cc'|Soluzione]). move(Riva_Sin1,Riva_Dx1,Soluzione) :- move_3_Dx_Sin(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), move(Riva_Sin2,Riva_Dx2,['<-mc'|Soluzione]). /* il goal Provate usando */ limite(10). /* limite di profondita` 10. E` la lunghezza minima, non ci sono cicli*/ % limite(12). /* limite di profondita` 12. Trovate anche soluzioni contenenti dei cicli*/ /* la prima soluzione */ problema1 :- move([m,m,m,c,c,c,b],[],[]). /* tutte le soluzioni (entro la lunghezza Lim) */ tutte1 :- move([m,m,m,c,c,c,b],[],[]), fail. /* Altro modo: si tiene una traccia degli stati per evitare i cicli move(Riva_Sin,Riva_Dx,N,Traccia) dove N serve a indentare la stampa e viene incrementato ad ogni chiamata ricorsiva. Traccia contiene gli stati gia` attraversati (nella forma Riva_Sin/Riva_Dx) N. B. Per poter confrontare gli stati le liste devono contenere m, c, b in un ordine definito. Per questo le rive vengono sortate ogno volta che si aggiungono elementi. */ /* stato finale */ move([],_,N,_) :- tab(N), write(fine),nl. /* mosse da sinistra a destra */ move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_2_Sin_Dx(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write(Riva_Sin1/Riva_Dx1/'cc->'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_2_Sin_Dx(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'mm->'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_1_Sin_Dx(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'m->'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_1_Sin_Dx(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'c->'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_3_Sin_Dx(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'mc->'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). /* mosse da destra a sinistra */ move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_1_Dx_Sin(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'<-c'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_1_Dx_Sin(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'<-m'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_2_Dx_Sin(m,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'<-mm'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_2_Dx_Sin(c,Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'<-cc'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). move(Riva_Sin1,Riva_Dx1,N,Traccia) :- move_3_Dx_Sin(Riva_Sin1,Riva_Dx1,Riva_Sin2,Riva_Dx2), not member(Riva_Sin2/Riva_Dx2,Traccia), N2 is N + 2, tab(N2), write( Riva_Sin1/Riva_Dx1/'<-mc'/Riva_Sin2/Riva_Dx2),nl, move(Riva_Sin2,Riva_Dx2,N2,[Riva_Sin2/Riva_Dx2|Traccia]). /* goal principale */ /* Confrontate i tempi di esecuzione con la soluzione precedente che adotta il limite di profondita`. Eliminare a priori la possibilita` di cicli e` molto piu` efficiente. */ /* la prima soluzione */ problema2 :- move([b,c,c,c,m,m,m],[],0,[[b,c,c,c,m,m,m]/[]]). /* tutte le soluzioni */ tutte2 :- move([b,c,c,c,m,m,m],[],0,[[b,c,c,c,m,m,m]/[]]), fail. /* Esempi di OUTPUT output di tutte1. 44 ?- tutte1. [cc->, <-c, cc->, <-c, mm->, <-mc, mm->, <-c, cc->, <-c, cc->] [cc->, <-c, cc->, <-c, mm->, <-mc, mm->, <-c, cc->, <-m, mc->] [mc->, <-m, cc->, <-c, mm->, <-mc, mm->, <-c, cc->, <-c, cc->] [mc->, <-m, cc->, <-c, mm->, <-mc, mm->, <-c, cc->, <-m, mc->] No output di tutte2. 45 ?- tutte2. [b, c, c, c, m, m, m] / [] / cc-> / [c, m, m, m] / [b, c, c] [c, m, m, m] / [b, c, c] / <-c / [b, c, c, m, m, m] / [c] [b, c, c, m, m, m] / [c] / cc-> / [m, m, m] / [b, c, c, c] [m, m, m] / [b, c, c, c] / <-c / [b, c, m, m, m] / [c, c] [b, c, m, m, m] / [c, c] / mm-> / [c, m] / [b, c, c, m, m] [c, m] / [b, c, c, m, m] / <-mc / [b, c, c, m, m] / [c, m] [b, c, c, m, m] / [c, m] / mm-> / [c, c] / [b, c, m, m, m] [c, c] / [b, c, m, m, m] / <-c / [b, c, c, c] / [m, m, m] [b, c, c, c] / [m, m, m] / cc-> / [c] / [b, c, c, m, m, m] [c] / [b, c, c, m, m, m] / <-c / [b, c, c] / [c, m, m, m] [b, c, c] / [c, m, m, m] / cc-> / [] / [b, c, c, c, m, m, m] fine [] / [b, c, c, c, m, m, m] / <-c / [b, c] / [c, c, m, m, m] [] / [b, c, c, c, m, m, m] / <-mc / [b, c, m] / [c, c, m, m] [c] / [b, c, c, m, m, m] / <-m / [b, c, m] / [c, c, m, m] [b, c, m] / [c, c, m, m] / mc-> / [] / [b, c, c, c, m, m, m] fine [] / [b, c, c, c, m, m, m] / <-c / [b, c] / [c, c, m, m, m] [] / [b, c, c, c, m, m, m] / <-cc / [b, c, c] / [c, m, m, m] [b, c, c, m, m, m] / [c] / m-> / [c, c, m, m] / [b, c, m] [b, c, c, c, m, m, m] / [] / c-> / [c, c, m, m, m] / [b, c] [b, c, c, c, m, m, m] / [] / mc-> / [c, c, m, m] / [b, c, m] [c, c, m, m] / [b, c, m] / <-m / [b, c, c, m, m, m] / [c] [b, c, c, m, m, m] / [c] / cc-> / [m, m, m] / [b, c, c, c] [m, m, m] / [b, c, c, c] / <-c / [b, c, m, m, m] / [c, c] [b, c, m, m, m] / [c, c] / mm-> / [c, m] / [b, c, c, m, m] [c, m] / [b, c, c, m, m] / <-mc / [b, c, c, m, m] / [c, m] [b, c, c, m, m] / [c, m] / mm-> / [c, c] / [b, c, m, m, m] [c, c] / [b, c, m, m, m] / <-c / [b, c, c, c] / [m, m, m] [b, c, c, c] / [m, m, m] / cc-> / [c] / [b, c, c, m, m, m] [c] / [b, c, c, m, m, m] / <-c / [b, c, c] / [c, m, m, m] [b, c, c] / [c, m, m, m] / cc-> / [] / [b, c, c, c, m, m, m] fine [] / [b, c, c, c, m, m, m] / <-c / [b, c] / [c, c, m, m, m] [] / [b, c, c, c, m, m, m] / <-mc / [b, c, m] / [c, c, m, m] [c] / [b, c, c, m, m, m] / <-m / [b, c, m] / [c, c, m, m] [b, c, m] / [c, c, m, m] / mc-> / [] / [b, c, c, c, m, m, m] fine [] / [b, c, c, c, m, m, m] / <-c / [b, c] / [c, c, m, m, m] [] / [b, c, c, c, m, m, m] / <-cc / [b, c, c] / [c, m, m, m] [b, c, c, m, m, m] / [c] / c-> / [c, m, m, m] / [b, c, c] No */