3
7idsearch(N,P) <-
8 h(N,HN) &
9 dbsearch([node(N,[],0)],HN,[node(N,[],0)],natural,P).
10
16
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
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