1% ITERATIVE-DEEPENING A* SEARCHER using CILOG
    2% Copyright David Poole, 1996
    3
    4% idsearch(N,P) is true if path P is a path found from node N
    5% using iterative deepening A* search 
    6% Example query: ask idsearch(o103,P).
    7idsearch(N,P) <-
    8   h(N,HN) &
    9   dbsearch([node(N,[],0)],HN,[node(N,[],0)],natural,P).
   10
   11% dbsearch(F,DB,Q,How1,P) is true if a depth bound search from frontier F
   12% can find a path P of length >= DB.
   13% where Q is the initial frontier to (re)start from,
   14% How specifies whether the previous bound failed naturally or gives
   15% the minimum f-value for which the search failed.
   16
   17% The frontier is a list of  node(Node,Path,PathLength)
   18%   where Node is a node, Path is the path found to Node,
   19%   PathLength is the length of the path.
   20
   21dbsearch([node(N,P,DB)|_],DB,_,_,[N|P]) <-
   22   is_goal(N).
   23dbsearch([node(N,P,PL)|F1],DB,Q,H,S) <-
   24   h(N,HN) &
   25   HN+PL =< DB &
   26   neighbours(N,NNs) &
   27   add_paths_db(NNs,N,[N|P],PL,F1,F2) &
   28   dbsearch(F2,DB,Q,H,S).
   29dbsearch([node(N,_,PL)|F1],DB,Q,H,S) <-
   30   h(N,HN) &
   31   HN+PL > DB &
   32   min1(HN+PL,H,LUB) &
   33   dbsearch(F1,DB,Q,LUB,S).
   34dbsearch([],_,Q,NDB,S) <-
   35   NDB \= natural &
   36   dbsearch(Q,NDB,Q,natural,S).
   37
   38%   add_paths(NNs,N,Path,PL,F0,F1)
   39add_paths_db([],_,_,_,F,F).
   40add_paths_db([NN|R],N,Path,PL,F0,[node(NN,Path,PL1)|F1]) <-
   41   cost(N,NN,AC) &
   42   PL1 is PL+AC &
   43   add_paths_db(R,N,Path,PL,F0,F1).
   44
   45min1(E,natural,V) <- V is E.
   46min1(E,V,V) <- V\= natural & V =< E.
   47min1(E,V,V1) <-V\= natural & V > E & V1 is E