1% ITERATIVE-DEEPENING SEARCHER
    2% Copyright David Poole, 1996
    3
    4% idsearch(Ns,P) is true if path P is a path found from starting nodes Ns
    5% using iterative deepening search 
    6% Example query: idsearch([o103],P).
    7idsearch(Ns,P) <-
    8   add_paths_db(Ns,[],0,[],Fr) &
    9   dbsearch(Fr,0,Fr,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 unnaturally
   15
   16% The frontier is a list of  node(Node,Path,PathLength)
   17%   where Node is a node, Path is the path found to Node,
   18%   PathLength is the number of arcs in the path.
   19
   20dbsearch([node(N,P,DB)|_],DB,_,_,[N|P]) <-
   21   is_goal(N).
   22dbsearch([node(N,P,PL)|F1],DB,Q,H,S) <-
   23   PL<DB &
   24   neighbours(N,NNs) &
   25   PL1 is PL+1 &
   26   add_paths_db(NNs,[N|P],PL1,F1,F2) &
   27   dbsearch(F2,DB,Q,H,S).
   28dbsearch([node(_,_,PL)|F1],DB,Q,_,S) <-
   29   PL >= DB &
   30   dbsearch(F1,DB,Q,unnatural,S).
   31dbsearch([],DB,Q,unnatural,S) <-
   32   DB1 is DB+1 &
   33   dbsearch(Q,DB1,Q,natural,S).
   34
   35% add\_paths\_db(NNs,Path,PL,F_0,F_1) adds the
   36% neighbours NNs to the front of frontier F_0
   37% forming frontier F_1. The neighbors need to be
   38% converted to the form of elements of the frontier.
   39% Path is the path found to the neighbor, and PL
   40% is the path's length.
   41add_paths_db([],_,_,F,F).
   42add_paths_db([NN|R],Path,PL,F0,[node(NN,Path,PL)|F1])