prolog - 在到达预期节点之前，我如何知道是否已经访问了图中的所有节点？

Question

我有这种类型的知识库：

connect(a, b).
connect(a, d).
connect(a, e).
connect(b, a).
connect(b, c).
...

我的目标是，给定一个起源和一个命运，在到达最终节点之前遍历所有现有节点一次。

到目前为止，这就是我所得到的：

path(O, D, L):-
    path(O, D, [O], L).

path(D, D, _, [D]).
path(O, D, A, [O|T]):-
    connect(O, I),
    \+ member(I, A),
    path(I, D, [I|A], T).

为了处理双重连接，例如connect(a, b). connect(b, a).，我使用一个列表来保存我经过的每个节点，并且在进入递归调用之前，我确保我要访问的节点不属于该列表。

现在我需要确保在到达最后一个节点之前遍历所有现有节点。我完全不知道如何解决这个问题。我怎么能确定我在到达最后一个节点之前访问了所有其他节点？

score 2 · Accepted Answer

您可以使用自己的代码（不使用 findall）进行测试，只需稍作改动即可。与其丢弃已访问节点的列表，不如保留它。因此，将 path/4 更改为 path/5，如下所示：

path(D, D, V, V, [D]).
path(O, D, A, V, [O|T]):-
    connect(O, I),
    \+ member(I, A),
    path(I, D, [I|A], V, T).

现在您可以查询 path(a,c,[a], Visited, Path) 并测试是否存在任何不是 Visited 成员的连接节点。

score 1 · Accepted Answer

您已将网络定义为边列表。收集所有节点的一种快速而简单的方法是，例如：

findall(X, ( connect(X, _) ; connect(_, X) ), Xs),
sort(Xs, Nodes)

这将首先收集您在您的中列出的所有“发件人”和“收件人” connect/2，然后通过排序和删除重复项来制作一组。

那时，您可以将此集合与您找到的路径进行比较（也可以在制作集合之后）。

显然，您的谓词失败很重要，因为没有路径可以访问由定义的网络中的所有节点connect/2。

2 回答 2