在 Prolog 中查找无环图的路径长度

Question

好的，我有图表：

并且我希望能够创建一个规则来查找从 X 到 Y 的所有路径及其长度（边数）。为了例如，从 a 到 e 的另一条路径存在于 d、f 和 g。它的长度是 4.

到目前为止，我的代码如下所示：

edge(a,b).
edge(b,e).
edge(a,c).
edge(c,d).
edge(e,d).
edge(d,f).
edge(d,g).

path(X, Y):- 
    edge(X, Y).

path(X, Y):-
    edge(X, Z), 
    path(Z, Y).

我有点不确定我应该如何处理这个问题。我输入了很多不起作用的规则，现在我很困惑。所以，我想我会把它带回到基础，看看你们能想出什么。如果可能的话，我也想知道您为什么要这样做。提前谢谢你。

Answer 1

这种情况已经问过好几次了。首先，您的 edge/2 谓词不完整，缺少像 edge(c,d)、edge(f,g) 或 edge(g,e) 这样的边。其次，您需要存储已访问节点的列表以避免创建循环。然后，当访问一个新节点时，您必须在 Path 变量中检查这个新节点是否尚未访问。但是，Path 尚未实例化。所以你需要一个延迟谓词来检查循环（all_dif/1）。这是使用 https://whosebug.com/users/4609915/repeat.

的惰性实现的简化版本

go(X, Y) :-
    path(X, Y, Path),
    length(Path, N),
    write(Path), write(' '), write(N), nl.
    
path(X, Y, [X, Y]):- 
    edge(X, Y).
path(X, Y, [X | Path]):-
    all_dif(Path),
    edge(X, Z), 
    path(Z, Y, Path).

%
%which uses a dynamic predicate for defining path
%Here is the lazy implementation of loop-checking
all_dif(Xs) :-                          % enforce pairwise term inequality
   freeze(Xs, all_dif_aux(Xs,[])).      % (may be delayed)

    all_dif_aux([], _).
    all_dif_aux([E|Es], Vs) :-               
       maplist(dif(E), Vs),                 % is never delayed
       freeze(Es, all_dif_aux(Es,[E|Vs])).  % (may be delayed)

下面是一些带有评论的执行

?- go(a,e).
[a,b,e] 3 %%% three nodes: length=2
true ;
[a,c,d,f,g,e] 6
true ;
[a,c,f,g,e] 5
true ;
[a,d,f,g,e] 5
true ;
false. %%% no more solutions

这是对您问题的回复吗？

在 Prolog 中查找无环图的路径长度

Finding the path length of an Acyclic Graph in Prolog

prolog

directed-acyclic-graphs