Prolog/搜索技术

Prolog 的默认搜索算法是 深度优先搜索 (DFS)，它有时并不方便：DFS 并不总是能找到所有问题的解决方案，即使它能找到，也可能找不到最佳解决方案。

假设我们想在一个有向图中找到最短路径，其中节点由符号表示，弧由谓词 arc/2 表示。然后我们可以轻松实现 迭代加深搜索 来找到最短路径。

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 按长度对路径进行回溯，如果存在至少一条路径，则会进行回溯。让我们试一试。

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

工作原理：当 length/2 以变量作为第一个参数被调用时，它会生成一个包含新变量的指定长度的列表。此外，如果第二个参数也是一个变量，它会从零开始，每次递增一个，对所有可能的长度进行回溯。每次都用固定的路径长度调用辅助谓词 path_r。