An implementation of IDA star
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% IDA* implemented using assert and %
% retract. %
% An implementation without assert or %
% retract requires an agenda and some %
% way of keeping track of the paths. %
% Thus losing the space advantage of %
% depth first search. %
% %
% Author. J.P.E. Hodgson %
% Date Started 11/30/1994 %
% Last Changed 1/4/95 %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% This code runs under standard prolog. The minor
% modifications required for ALS, Quintus, BIM
% and LPA prolog are indicated as necessary.
%
:- dynamic(next_bound/1).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The user must supply the heuristic relation
% value(+Node, -Value), and the successor relation
% successor(+Node, -ChildNode, -TransitionCost).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ida_star(+Start, % Node to start from
% -Soln) % Solution
%
ida_star(Start, Soln) :-
abolish(next_bound/1), % in ALS prolog abolish(next_bound,1)
value(Start, H),
asserta(next_bound(infinity)), % set bound for next search.
ida_star(parent,[], Start/0,H,Start, Soln).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%
% ida_star(+master_slave, % is this a master or a slave
% +Path, % Path to node before current node
% +Node/Cost, % Pairing of current node and cost to reach it
% +CurrentBound, % Bound for current search
% +Start, % Start, needed for next search.
% -NewPath % New path.
% Goal reached.
ida_star(_,Path, Node/G, _,Start, [Node|Path]) :-
goalreached(Node).
% Normal search. Depth first with cutoff if bound is exceeded.
% Checks to see if next bound needs to be reset lower.
ida_star(_,Path, Node/G, Bound, Start,Soln) :-
successor(Node, Node1, C),
not member(Node1, Path), % no looping.
G1 is G + C, value(Node1, H1), F1 is G1 + H1,
revise_next_bound(F1, Bound),
lesseq(F1,Bound), % acceptable node
ida_star(slave,[Node|Path], Node1/G1, Bound,Start, Soln).
% Normal search failed, try to go deeper. This clause
% is only available to the master search.
ida_star(master,_, _, Bound, Start, Soln) :-
next_bound(Next),
Next = Bound -> (write('Search has failed'),nl )
;
( % Do deeper search
reset_next_bound,
ida_star(master,[], Start/0, Next, Start, Soln)
).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% revise_next_bound(+Val, +CurrentBound)
%
% update the asserted value of next_bound.
% This must always succeed.
%
revise_next_bound(Val, Current) :- lesseq(Val, Current), !.
revise_next_bound(Val,Current ) :-
next_bound(Next),
(better(Val, Next) ->
retract(next_bound(Next)),
asserta(next_bound(Val));
true).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% reset_next_bound/0 if a new search is started
% next bound needs to be set to infinity.
%
reset_next_bound :- retract(next_bound(Val)), asserta(next_bound(infinity)).
%%%%%%%%%%%%%%%%%%%%%
%
% better(+V1,+V2) true if V1 is less than V2, V2 may be infinity
%
better(Val, infinity) :- !.
better(Val, V1) :-
Val < V1, !.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% lesseq(+V1, +V2) true if V1 is V1 is less than or equal to V2,
% V2 may be infinity.
%
lesseq(F, infinity) :- !.
lesseq(F, Bd) :- F =< Bd.
]]>
Jonathan Hodgson
Last Changed: 30/11/1994