列出所有可到达的节点

Question

我有一个谓词是双向的，并告诉一个节点是否连接到另一个节点。 例如

has(a, b). 
has(b, c). 
has(d, b). 

现在我想列出所有可以达到（从一个特定节点）具有给定步数的节点。

connected_nodes(a, T, 2). 

因此应该输出

T = c 
T = d 

我当前的代码看起来是这样的：

connected_nodes(A, B, 0) :- write(A). 
connected_nodes(A, B, N) :- 
    N > 0, M is N - 1, 
    has(A, X), 
    connected_nodes(X, B, M). 

这适用于T = C，但不为T = d，因为这是一个双定向关系。

我是否按照递归方式正确思考或者如何以其他方式解决此问题？

Answer 1

你的connected谓词看起来不错。使基础案例依赖于has可能更有意义，但这取决于你。

但是，您说您的has谓词是“双向”，但您没有明确创建一个规则来表明这一点。

下面的代码是你的代码的“双向”的版本：但是你的查询现在返回a作为一个可能的答案太

has(a, b). 
has(b, c). 
has(d, b). 

bi_has(X,Y) :- has(X,Y). 
bi_has(X,Y) :- has(Y,X). 

connected_nodes(A, B, 0) :- write(A). 
connected_nodes(A, B, N) :- 
    N > 0, M is N - 1, 
    bi_has(A, X), 
    connected_nodes(X, B, M). 

注意。这使得，因为你从来没有明确表示你不想在2步后返回到同一个元素。

如果您不想要这种行为，那么您还需要保留到目前为止访问的元素列表（即累加器），并确认您没有重新访问元素。