Codice SICStus Prolog

Contenuto del file

:-use_module(library(lists)).

% USER THEORY %

% 1)Precondizioni degli operatori

applicabile(move_to_table(X), 1, S) :- 
	member(clear(X), S), 
	member(on(X,Y), S). 
applicabile(move_from_table(X,Y), 1, S) :- 
	member(on_table(X), S), 
	member(clear(X), S), 
	member(clear(Y), S),
	X\=Y. 
applicabile(move(X,Y), 1, S) :- 
	member(clear(X), S), 
	member(on(X,Z), S), 
	member(clear(Y), S),
	X\=Y.
	
%PREDICATO DI SUPPORTO AGGIUNTO PER UTILIZZARE 
%LE STRATEGIE DI RICERCA NON INFORMATE 
%ANCHE SE 'APPLICABILE' SPECIFICA UN COSTO
applicabile(A, S):-
	applicabile(A, _, S).

% 2)Definizione delle azioni

trasforma(move_to_table(X),S,[on_table(X), clear(Y) | S1]) :- 
	my_delete(on(X,Y),S,S1). 
trasforma(move_from_table(X,Y),S, [on(X,Y) | S2]) :- 
	my_delete(on_table(X),S,S1), 
	my_delete(clear(Y),S1,S2). 
trasforma(move(X,Y),S,[on(X,Y),clear(Z) | S2]) :- 
	my_delete(clear(Y),S,S1), 
	my_delete(on(X,Z),S1,S2).

% 3)STATO INIZIALE E FINALE

iniziale([on_table(b),clear(b),on_table(a), on(c,a), clear(c)]). 
 
finale(S) :- 
	member(on_table(c),S), 
	member(on(b,c), S),
	member(on(a,b),S), 
	member(clear(a),S). 




% 4) EVENTUALE EURISTICA
hstar(S,0):- 	
	finale(S),!. 
hstar(S,3-N):- 
	my_intersection([on(a,b),on(b,c),on_table(c)],S,L), 
	length(L,N).


% PREDICATI COMUNI %

uguale([], []). 
uguale([X | REST1], S2) :- 
	member(X, S2), 
	my_delete(X, S2, REST2), 
	uguale(REST1, REST2).
		
my_delete(El, [], []).
my_delete(El, [El|T], T1):-
	!,
	my_delete(El, T, T1).
my_delete(El, [H|T], [H|T1]):-
	my_delete(El, T, T1).
	
	
my_intersection([], S2, []).
my_intersection([H|T], S2, [H|T3]):-
	member(H, S2),
	!,
	my_intersection(T, S2, T3).
	
my_intersection([H|T], S2, S3):-
	my_intersection(T, S2, S3).


% DEPTH-FIRST SEARCH STRATEGY %

soluzione(SOLUZIONE):-
	iniziale(S), 
	solve(S, [], SOLUZIONE).
	
solve(S, _, []) :- 
	finale(S), !. 

solve(S, VISITATI, [OP | RESTO]):- 
	applicabile(OP, S), 
	trasforma(OP, S, NUOVO_S), 
	\+(visitato(NUOVO_S, VISITATI)), 
	solve(NUOVO_S, [S | VISITATI], RESTO).
	
visitato(S, [S1 | _]) :- 
	uguale(S, S1),!. 
	
visitato(S, [_ | REST]) :- 
	visitato(S, REST).
	
	
	
	
	
% BREADTH-FIRST SEARCH STRATEGY %

soluzione_ampiezza(SOLUZIONE):- 
	iniziale(S), 
	solve_ampiezza([[S, [], []]], SOLUZIONE). 

solve_ampiezza([[S,PATH, LISTA_OP] | _ ],LISTA_OP):- 
	finale(S). 

solve_ampiezza([[S,PATH,LISTA_OP]|REST],LISTA_OP1):- 
	finale(S), !, 
	solve_ampiezza(REST, LISTA_OP1). 

solve_ampiezza([[S,PATH,LISTA_OP]|REST],SOL):- 
	ins_applicabili(S, APPLIC),
	ins_trasformati(S,PATH,LISTA_OP,APPLIC,NUOVI),
	append(REST,NUOVI,LISTA),
	solve_ampiezza(LISTA,SOL). 

ins_applicabili(S, OPERAT) :- 
	setof(OP, applicabile(OP,S), OPERAT), !. 

ins_applicabili(S,[]).	
	
member_uguale(S, [S1 | T]):-
	uguale(S, S1), !.

member_uguale(S, [S1 | T]):-
	member_uguale(S, T).	
	
ins_trasformati(_,_,_,[],[]). 
ins_trasformati(S,PATH,LISTA_OP,[OP | REST],ALTRI):- 
	trasforma(OP, S, NUOVO_S), 
	member_uguale(NUOVO_S, PATH),!, 
	ins_trasformati(S, PATH, LISTA_OP, REST, ALTRI). 

ins_trasformati(S,PATH,LISTA_OP,[OP | REST], [[NUOVO_S,[S | PATH],[OP | LISTA_OP]]|ALTRI]):- 
	trasforma(OP,S,NUOVO_S), 
	ins_trasformati(S, PATH, LISTA_OP, REST, ALTRI). 



% A* SEARCH STRATEGY %

insieme_applicabili_astar(STATO,OPERATORI) :- 
	setof([OP,PESO], 
	applicabile(OP,PESO,STATO),OPERATORI),!. 

insieme_applicabili_astar(STATO,[]).

soluzione_astar(SOLUZIONE):- 
	iniziale(S), 
	hstar(S, VALORE), 
	solve_astar([[S,[[],0],VALORE]],[],SOLUZIONE). 

solve_astar([[S,[PATH,COSTO],_]|_],_, [PATH,COSTO]):- 
	finale(S). 

solve_astar([[S,[PATH,COSTO],STIMA]|REST],VIS,SOL):- 
	insieme_applicabili_astar(S, OP), 
	ins_trasf_astar(S,PATH,COSTO,OP,NUOVI), 
	aggiorna(NUOVI,REST,REST1,VIS,VISITATI1), 
	solve_astar(REST1,[[S,STIMA]|VISITATI1],SOL).

ins_trasf_astar(_, _, _, [], []). 

ins_trasf_astar(S,PATH,COSTO,[[OP,PESO]|REST_OP], [[NUOVO_S,[[OP | PATH],COSTO1],VAL]| REST_ST]) :- 
	trasforma(OP, S, NUOVO_S), 
	COSTO1 is COSTO+PESO, 
	hstar(NUOVO_S,STIMA), 
	VAL is COSTO1 + STIMA, 
	ins_trasf_astar(S,PATH,COSTO,REST_OP,REST_ST).
	
aggiorna([], DA_VIS, DA_VIS, VIS, VIS).  

aggiorna([[S,[PATH,COSTO],STIMA]|REST],DA_VIS, NEW_DA_VIS, VIS, NEW_VIS):- 
	member([S1, STIMA1], VIS), 
	uguale(S, S1),
	STIMA1=<STIMA, !, 
	aggiorna(REST,DA_VIS,NEW_DA_VIS,VIS,NEW_VIS). 

aggiorna([[S,[PATH,COSTO],STIMA]|REST],DA_VIS, NEW_DA_VIS, VIS, NEW_VIS):- 
	member([S1, STIMA1], VIS),
	uguale(S, S1), 
	STIMA1 > STIMA, !, 
	my_delete([S1, STIMA1], VIS, VIS1), 
	insert([S, [PATH,COSTO], STIMA],DA_VIS,DA_VIS1), 
	aggiorna(REST,DA_VIS1,NEW_DA_VIS,VIS1,NEW_VIS). 
	
aggiorna([[S,[PATH,COSTO],STIMA]|REST],DA_VIS, NEW_DA_VIS, VIS, NEW_VIS):- 
	member([S1, _, STIMA1], DA_VIS), 
	uguale(S, S1),
	STIMA1 =< STIMA, !, 
	aggiorna(REST,DA_VIS,NEW_DA_VIS, VIS, NEW_VIS).

aggiorna([[S,[PATH,COSTO],STIMA]|REST],DA_VIS, NEW_DA_VIS, VIS, NEW_VIS):- 
	member([S1, _, STIMA1], DA_VIS), 
	uguale(S, S1),
	STIMA1 > STIMA, !, 
	my_delete([S1, _, STIMA1], DA_VIS, DA_VIS1), 
	insert([S,[PATH,COSTO],STIMA],DA_VIS1, DA_VIS2), 
	aggiorna(REST,DA_VIS2,NEW_DA_VIS,VIS,NEW_VIS). 	
	
aggiorna([[S,[PATH,COSTO],STIMA]|REST],DA_VIS, NEW_DA_VIS, VIS, NEW_VIS):- 
	insert([S, [PATH,COSTO], STIMA], DA_VIS, DA_VIS1), 
	aggiorna(REST,DA_VIS1,NEW_DA_VIS,VIS,NEW_VIS). 

insert([S, X, STIMA], [], [[S, X, STIMA]]). 

insert([S,X,STIMA], [[S1,X1,STIMA1]|REST], [[S,X,STIMA], [S1,X1,STIMA1]|REST]):- 
	STIMA =< STIMA1, !. 

insert([S,X,STIMA],[[S1,X1,STIMA1]|REST], [[S1,X1,STIMA1]|NEW_REST]):- 
	insert([S,X,STIMA], REST, NEW_REST).