Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:prolog:pllib:best-first_framework [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 +====== Best-first framework ======
 +{{tag>​framework problem_solving}}
 +===== Description =====
 +Best first framework for problem solving
 +
 +**Source**: ​ The Art of Prolog
 +===== Download =====
 +Program source code: {{best-first_framework.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, where Frontier contains the current ​
 + states under consideration,​ and 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),​
 + updates(Moves,​Path,​State,​States),​
 + legals(States,​States1),​
 + news(States1,​History,​States2),​
 + evaluates(States2,​Values),​
 + inserts(Values,​Frontier,​Frontier1),​
 + solve_best(Frontier1,​[State|History],​FinalPath).
 +
 +/*
 +   ​updates(Moves,​Path,​State,​States) :-
 + States is the list of possible states accessible from the 
 + current State, according to the list of possible Moves,
 + where Path is a path from the initial node to State.
 +*/
 +
 +     ​updates([Move|Moves],​Path,​State,​[(State1,​[Move|Path])|States]) :-
 + update(State,​Move,​State1),​ updates(Moves,​Path,​State,​States).
 +     ​updates([],​Path,​State,​[]).
 +
 +/*
 +   ​legals(States,​States1) :-
 + States1 is the subset of the list of States that are legal.
 +*/
 +
 +     ​legals([(S,​P)|States],​[(S,​P)|States1]) :-
 + legal(S), legals(States,​States1).
 +     ​legals([(S,​P)|States],​States1) :-
 + not legal(S), legals(States,​States1).
 +     ​legals([],​[]).
 +
 +/*
 +   ​news(States,​History,​States1) :-
 + States1 is the list of states in States but not in History.
 +*/
 +     ​news([(State,​Path)|States],​History,​States1) :-
 + member(State,​History),​ news(States,​History,​States1).
 +     ​news([(State,​Path)|States],​History,​[(State,​Path)|States1]) :-
 + not member(State,​History),​ news(States,​History,​States1).
 +     ​news([],​History,​[]).
 +
 +/*
 +   ​evaluates(States,​Values) :- 
 + Values is the list of tuples of States augmented by their value.
 +*/
 +     ​evaluates([(State,​Path)|States],​[state(State,​Path,​Value)|Values]) :-
 + value(State,​Value),​ evaluates(States,​Values).
 +     ​evaluates([],​[]).
 +
 +/*
 +   ​inserts(States,​Frontier,​Frontier1) :-
 + Frontier1 is the result of inserting States into the current Frontier.
 +*/
 +     ​inserts([Value|Values],​Frontier,​Frontier1) :-
 + insert(Value,​Frontier,​Frontier0),​
 + inserts(Values,​Frontier0,​Frontier1).
 +     ​inserts([],​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.
 +
 +%  Program 20.6     Best first framework for problem solving
 +</​code>​
 +===== Comments =====
  
pl/prolog/pllib/best-first_framework.txt · ostatnio zmienione: 2019/06/27 15:50 (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