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 ===== | ||
| + | <code prolog> | ||
| + | % 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" | ||
| + | </code> | ||
| + | ===== Comments ===== | ||
