Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:pllib:breadth-first_search_2 [2019/06/27 15:50] |
pl:prolog:pllib:breadth-first_search_2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== 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 ===== | ||
