1

图表如下图所示。我必须告诉两个节点之间是否有路径并打印路径。例如：我的查询是路径（a，c）。那么它将返回True。现在，当我将查询作为路径（g，f）给出时，Ist ​​和第二个结果为 True，之后它没有终止，而是开始循环。我是序言的新手。请提出一些解决方案，以在获得正确数量的路径后停止递归图表 这些是事实

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


    path(X,Y):- arc(X,Y).
    path(X,Y):- arc(X,Z),path(Z,Y).
4

1 回答 1

1

您正在遍历有向图。假设它是非循环的，这应该枚举所有可能的路径：

path(X,Y) :- % a path exists from X to Y 
  arc(X,Y)   % IF an edge exists *from* X *to* Y
  .          %
path(X,Y) :- % Otherwise, a path exists from X to Y
  arc(X,Z) , % IF an outbound path from X exists
  Z \== Y ,  % whose destination (Z) is NOT Y, and
  path(X,Y)  % a path exists from Z to Y
  .          % Easy!

我们在这里使用 \==/2 是因为这个谓词可能会被未绑定的参数调用。

另一种写法可能是：

path(X,Y) :-  % A path exists from X to Y
  arc(X,Z) ,  % IF an outbound path from X exists,
  (           % AND
    Z = Y     % Y is that destination (Z)
  ;           % OR
    path(Z,Y) % Y can be reached from Z.
  ) .

如果你的图是循环的，你需要构建并随身携带访问节点列表，这样你就可以跳过你已经看到的访问节点，以免陷入无限递归的兔子洞。

于 2013-11-07T20:43:45.873 回答