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
41add_paths_db([],_,_,F,F).
42add_paths_db([NN|R],Path,PL,F0,[node(NN,Path,PL)|F1])