Concise best first framework for problem solving
Source: The Art of Prolog
Program source code: best-first_framework_2.pl
/* 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