|
|
pl:prolog:pllib:best-first_framework_2 [2019/06/27 15:50] |
pl:prolog:pllib:best-first_framework_2 [2019/06/27 15:50] (aktualna) |
| ====== Best-first framework 2 ====== |
| {{tag>framework problem_solving}} |
| ===== Description ===== |
| Concise best first framework for problem solving |
| |
| **Source**: The Art of Prolog |
| ===== Download ===== |
| Program source code: {{best-first_framework_2.pl}} |
| ===== Listing ===== |
| <code prolog> |
| /* |
| 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 |
| </code> |
| ===== Comments ===== |
| |