# Różnice

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 ===== + + % 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)). + + ​ + ===== Comments =====
pl/prolog/pllib/ida_algorithm.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)