# Różnice

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

 — pl:prolog:pllib:rbfs_algorithm [2019/06/27 15:50] (aktualna) Linia 1: Linia 1: + ====== Rbfs algorithm ====== + {{tag>​searching}} + ===== Description ===== + A best-first search program that only requires space linear in the depth of search (RBFS algorithm). + + **Source**: ​ PROLOG programming for artificial intelligence,​ 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. + ===== Download ===== + Program source code: {{rbfs_algorithm.pl}} + ===== Listing ===== + + % Figure 12.13  A best-first search program that only requires ​ + % space linear in the depth of search (RBFS algorithm). ​ + + :- op( 900, fy, not). + + % not Goal): negation as failure; ​ + %   Note: This is often available as a built-in predicate, + %   often written as prefix operator "​\+",​ e.g. \+ likes(mary,​snakes) + + not Goal  :- + Goal, !, fail + ; + true. + + % Linear-space best-first search; the RBFS algorithm ​ + % The program assumes 99999 is greater than any f-value + + % bestfirst( Start, Solution): Solution is a path from Start to a goal + + bestfirst( Start, Solution) :- + rbfs( [], [ (Start, 0/0/0) ], 99999, _, yes, Solution). + + % rbfs( Path, SiblingNodes,​ Bound, NewBestFF, Solved, Solution): + %   Path = path so far in reverse order + %   ​SiblingNodes = children of head of Path + %   Bound = upper bound on F-value for search from SiblingNodes + %   ​NewBestFF = best f-value after searching just beyond Bound + %   ​Solved = yes, no, or never + %   ​Solution = solution path if Solve = yes + % + %   ​Representation of nodes: Node = ( State, G/F/FF) + %   where G is cost till State, F is static f-value of State, ​ + %   FF is backed-up value of State + + rbfs( Path, [ (Node, G/F/FF) | Nodes], Bound, FF, no, _)  :- + FF > Bound, !. + + rbfs( Path, [ (Node, G/F/FF) | _], _, _, yes, [Node | Path]) ​ :- + F = FF,     % Only report solution once, when first reached; then F=FF + goal( Node). + + rbfs( _, [], _, _, never, _)  :- !.   % No candidates, dead end! + + rbfs( Path, [ (Node, G/F/FF) | Ns], Bound, NewFF, Solved, Sol)  :- + FF =< Bound, ​                   % Within Bound: generate children + findall( Child/​Cost, ​ + ( s( Node, Child, Cost), not member( Child, Path)), + ​Children),​ + inherit( F, FF, InheritedFF), ​  % Children may inherit FF + succlist( G, InheritedFF,​ Children, SuccNodes), ​ % Order children + bestff( Ns, NextBestFF), ​       % Closest competitor FF among siblings + min( Bound, NextBestFF, Bound2), !, + rbfs( [Node | Path], SuccNodes, Bound2, NewFF2, Solved2, Sol), + continue(Path,​ [(Node,​G/​F/​NewFF2)|Ns],​ Bound, NewFF, Solved2, Solved, Sol). + + % continue( Path, Nodes, Bound, NewFF, ChildSolved,​ Solved, Solution) + + continue( Path, [N | Ns], Bound, NewFF, never, Solved, Sol)  :- !, + rbfs( Path, Ns, Bound, NewFF, Solved, Sol).    % Node N a dead end + + continue( _, _, _, _, yes, yes, Sol). + + continue( Path, [ N | Ns], Bound, NewFF, no, Solved, Sol)  :- + insert( N, Ns, NewNs), !,      % Ensure siblings are ordered by values + rbfs( Path, NewNs, Bound, NewFF, Solved, Sol). + + succlist( _, _, [], []). + + succlist( G0, InheritedFF,​ [Node/C | NCs], Nodes) :- + G is G0 + C, + h( Node, H), + F is G + H, + max( F, InheritedFF,​ FF), + succlist( G0, InheritedFF,​ NCs, Nodes2), + insert( (Node, G/F/FF), Nodes2, Nodes). + + inherit( F, FF, FF)  :-    % Child inherits father'​s FF if + FF > F, !.               % father'​s FF greater than father'​s F + + inherit( F, FF, 0). + + insert( (N, G/F/FF), Nodes, [ (N, G/F/FF) | Nodes]) :- + bestff( Nodes, FF2), + FF =< FF2, !. + + insert( N, [N1 | Ns], [N1 | Ns1])  :- + insert( N, Ns, Ns1). + + bestff( [ (N, F/G/FF) | Ns], FF).   % First node - best FF + + bestff( [], 99999). ​     % No nodes - FF = "​infinite"​ + ​ + ===== Comments =====
pl/prolog/pllib/rbfs_algorithm.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)