|
|
— |
pl:prolog:pllib:breadth-first_search_2 [2019/06/27 15:50] (aktualna) |
| ====== Breadth-first search 2 ====== |
| {{tag>searching}} |
| ===== Description ===== |
| A more efficient program than that of szukanie_wszerz for the breadth-first search The improvement is based on using the difference-pair representation for the list of candidate paths. |
| |
| **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. |
| ===== Download ===== |
| Program source code: {{breadth-first_search_2.pl}} |
| ===== Listing ===== |
| <code prolog> |
| % Figure 11.11 A more efficient program than that of Figure 11.10 for |
| % the breadth-first search. The improvement is based on using |
| % the difference-pair representation for the list of candidate paths. |
| % Procedure extend is as in Figure 11.10. |
| |
| :- 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. |
| |
| % solve( Start, Solution): |
| % Solution is a path (in reverse order) from Start to a goal |
| |
| solve( Start, Solution) :- |
| breadthfirst( [ [Start] | Z] - Z, Solution). |
| |
| breadthfirst( [ [Node | Path] | _] - _, [Node | Path] ) :- |
| goal( Node). |
| |
| breadthfirst( [Path | Paths] - Z, Solution) :- |
| extend( Path, NewPaths), |
| conc( NewPaths, Z1, Z), % Add NewPaths at end |
| Paths \== Z1, % Set of candidates not empty |
| breadthfirst( Paths - Z1, Solution). |
| |
| |
| |
| extend( [Node | Path], NewPaths) :- |
| bagof( [NewNode, Node | Path], |
| ( s( Node, NewNode), not member( NewNode, [Node | Path] ) ), |
| NewPaths), |
| !. |
| |
| extend( Path, [] ). |
| </code> |
| ===== Comments ===== |
| |