Różnice między wybraną wersją a wersją aktualną.
| — |
pl:prolog:pllib:ida_algorithm [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== Ida algorithm ====== | ||
| + | {{tag>algorithms}} | ||
| + | ===== Description ===== | ||
| + | An implementation of the IDA* algorithm. | ||
| + | |||
| + | **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. | ||
| + | ===== Download ===== | ||
| + | Program source code: {{ida_algorithm.pl}} | ||
| + | ===== Listing ===== | ||
| + | <code prolog> | ||
| + | % Figure 12.10: An implementation of the IDA* 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. | ||
| + | |||
| + | % idastar( Start, Solution): | ||
| + | % Perform IDA* search; Start is the start node, Solution is solution path | ||
| + | |||
| + | idastar( Start, Solution) :- | ||
| + | retract( next_bound(_)), fail % Clear next_bound | ||
| + | ; | ||
| + | asserta( next_bound( 0)), % Initialise bound | ||
| + | idastar0( Start, Solution). | ||
| + | | ||
| + | idastar0( Start, Sol) :- | ||
| + | retract( next_bound( Bound)), % Current bound | ||
| + | asserta( next_bound( 99999)), % Initialise next bound | ||
| + | f( Start, F), % f-value of start node | ||
| + | df( [Start], F, Bound, Sol) % Find solution; if not, change bound | ||
| + | ; | ||
| + | next_bound( NextBound), | ||
| + | NextBound < 99999, % Bound finite | ||
| + | idastar0( Start, Sol). % Try with new bound | ||
| + | |||
| + | % df( Path, F, Bound, Sol): | ||
| + | % Perform depth-first search within Bound | ||
| + | % Path is the path from start node so far (in reverse order) | ||
| + | % F is the f-value of the current node, i.e. the head of Path | ||
| + | |||
| + | df( [N | Ns], F, Bound, [N | Ns]) :- | ||
| + | F =< Bound, | ||
| + | goal( N). % Succeed: solution found | ||
| + | |||
| + | df( [N | Ns], F, Bound, Sol) :- | ||
| + | F =< Bound, % Node N within f-bound | ||
| + | s( N, N1), not member( N1, Ns), % Expand N | ||
| + | f( N1, F1), | ||
| + | df( [N1,N | Ns], F1, Bound, Sol). | ||
| + | |||
| + | df( _, F, Bound, _) :- | ||
| + | F > Bound, % Beyond Bound | ||
| + | update_next_bound( F), % Just update next bound | ||
| + | fail. % and fail | ||
| + | |||
| + | update_next_bound( F) :- | ||
| + | next_bound( Bound), | ||
| + | Bound =< F, ! % Do not change next bound | ||
| + | ; | ||
| + | retract( next_bound( Bound)), !, % Lower next bound | ||
| + | asserta( next_bound( F)). | ||
| + | |||
| + | </code> | ||
| + | ===== Comments ===== | ||
