Best-first framework 2

Description

Concise best first framework for problem solving

Source: The Art of Prolog

Download

Program source code: best-first_framework_2.pl

Listing

/*
solve_best(Frontier,History,Moves) :-
      Moves is the sequence of moves to reach a desired final state 
	from the initial state. Frontier contains the current states 
	under consideration. History contains the states visited previously.
*/
 
:-  op(900,fy,not).
 
     solve_best([state(State,Path,Value)|Frontier],History,Moves) :- 
	final_state(State), reverse(Path,[],Moves).
     solve_best([state(State,Path,Value)|Frontier],History,FinalPath) :-
	findall(M,move(State,M),Moves),
	update_frontier(Moves,State,Path,History,Frontier,Frontier1),
	solve_best(Frontier1,[State|History],FinalPath).
 
update_frontier([Move|Moves],State,Path,History,Frontier,Frontier1) :-
   	update(State,Move,State1),
	legal(State1),
	value(State1,Value),
	not member(State1,History),
	insert(state(State1,[Move|Path],Value),Frontier,Frontier0),
	update_frontier(Moves,State,Path,History,Frontier0,Frontier1).
update_frontier([],State,Path,History,Frontier,Frontier).
 
 
     insert(State,[],[State]).
     insert(State,[State1|States],[State,State1|States]) :- 
	lesseq_value(State,State1).
     insert(State,[State1|States],[State|States]) :- 
	equals(State,State1).
     insert(State,[State1|States],[State1|States1]) :-
	greater_value(State,State1), insert(State,States,States1).
 
     equals(state(S,P,V),state(S,P1,V)).
 
     lesseq_value(state(S1,P1,V1),state(S2,P2,V2)) :- S1 \== S2, V1 =< V2.
 
     greater_value(state(S1,P1,V1),state(S2,P2,V2)) :- V1 > V2.
 
	reverse([X|Xs],Acc,Ys) :- reverse(Xs,[X|Acc],Ys).
	reverse([],Ys,Ys).
 
%  Program 20.7     Concise best first framework for problem solving

Comments

pl/prolog/pllib/best-first_framework_2.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0