Prolog/Search techniques

From Wikibooks, the open-content textbooks collection

Prolog's default search algorithm is depth-first search (DFS), which is sometimes not convenient: DFS doesn't always find the solution for all problems, and when it does, it might not find the optimal solution.

Let's say we want to find the shortest path through a directed graph with nodes represented by symbols and arc by the predicate arc/2. Then we can easily implement iterative deepening search to find the shortest path:

path(X,Z,Path) :-
    length(Path,_),
    path_r(X,Z,Path).
 
path_r(Z,Z,[]).
path_r(X,Z,[X|Path]) :-
    arc(X,Y),
    path(Y,Z,Path).

path/3 backtracks over paths, ordered by length, if at least one path exists. Let's try it out:

?- path(a,g,P).
P = [a] ;
P = [a, b, f] ;
P = [a, c, d, f] ;
P = [a, b, c, d, f]

How this works: when length/2 is called with a variable first argument, it generates a the desired length containing fresh variables. When, in addition, the second argument is a variable, it backtracks over all possible lengths starting at zero and stepping by one. The helper predicate path_r is called each time with a fixed path length.