Różnice między wybraną wersją a wersją aktualną.
|
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) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== 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 ===== | ||
