2

上下文，首先。我有以下双向图。

图形

在 Prolog 中表示如下：

relation(a,c).
relation(b,d).
relation(c,d).
relation(d,e).
relation(e,f).

connection(X,Y) :- relation(X,Y).
connection(X,Y) :- relation(Y,X).

所以我有节点之间的关系，然后节点之间的连接相关，正如我之前所说，在两个方向上。

我想要做的是一个序言定义，path(X,Y)能够判断图中两个节点之间是否存在路径（如果两个节点之间至少存在一条路径，则为 true，如果两个节点之间不存在路径，则为 false）。

因此，此模型中的目标输出应如下所示：

?- path(a,d).
true.

?- path(b,a).
true. 

?- path(f,b).
true

?  path(a,g).  % The node g doesn't exist
false.

我知道这涉及使用访问列表，并且我已经看到了这样的示例，但是给出了两个节点之间的所有可能路径。然而，这不是我要找的。我正在寻找的是一个定义，它检测两个节点之间是否存在路径，而不是给出两个节点之间的所有可能路径。

编辑：所以，感谢@mbratch，我现在可以将建议的问题调整为解决方案：

relation(a,c).
relation(b,d).
relation(c,d).
relation(d,e).
relation(e,f).

connection(X,Y) :- relation(X,Y).
connection(X,Y) :- relation(Y,X).

path_exists(X,Y) :- path(X,Y,_), !.

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connection(A,B).
travel(A,B,Visited,Path) :-
       connection(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).
4

1 回答 1

2

您想要得到的通常称为“二元关系的传递闭包”。

我们可以通过使用这样的来获得：connection/2 closure/3

% Q: 哪个` To`可以通过从`From`开始的`connection`到达？
?- 闭包（连接，从，到）。

首先，让我们运行 OP 给出的查询：

?- closure(connection,a,d).
  true                                % OK: succeeds non-deterministically
; false.                      

?- closure(connection,b,a).
  true                                % OK: succeeds non-deterministically
; false.

?- closure(connection,f,b).
  true                                % OK: succeeds non-deterministically
; false.

?- closure(connection,a,g).
false.                                % OK: finitely fails

让我们问最一般的查询！

?- closure(connection,X,Y).
  X = a, Y = c
; X = a, Y = d
; X = a, Y = e
; X = a, Y = f
; X = a, Y = b
; X = b, Y = d
; X = b, Y = e
; X = b, Y = f
; X = b, Y = c
; X = b, Y = a
; X = c, Y = d
; X = c, Y = e
; X = c, Y = f
; X = c, Y = b
; X = d, Y = e
; X = d, Y = f
; X = e, Y = f
; X = c, Y = a
; X = d, Y = b
; X = d, Y = c
; X = d, Y = a
; X = e, Y = d
; X = e, Y = b
; X = e, Y = c
; X = e, Y = a
; X = f, Y = e
; X = f, Y = d
; X = f, Y = b
; X = f, Y = c
; X = f, Y = a
false.
于 2015-09-03T11:46:14.810 回答