我如何知道在到达预期节点之前是否已访问图中的所有节点?
How can I know if all nodes have been visited in a graph before reaching the intended node?
我有这种类型的知识库:
connect(a, b).
connect(a, d).
connect(a, e).
connect(b, a).
connect(b, c).
...
我的objective是,给定起点和终点,在到达最终节点之前,遍历所有现有节点一次。
到目前为止,这是我得到的:
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).
我使用一个列表来保存我经过的每个节点,在进入递归调用之前,我确保我将要访问的节点不属于该列表。
现在我需要确保在到达最后一个节点之前遍历所有现有节点。我完全不知道如何处理这个问题。我怎么能确定我在到达最后一个节点之前访问了所有其他节点?
您已将网络定义为边列表。收集所有节点的快速而简单的方法是,例如:
findall(X, ( connect(X, _) ; connect(_, X) ), Xs),
sort(Xs, Nodes)
这将首先收集您在 connect/2
中列出的所有 "from" 和 "to",然后通过排序和删除重复项来制作一个集合。
到那时你可以将这个集合与你找到的路径进行比较(在制作一个集合之后)。
显然,您的谓词失败很重要,因为没有路径访问 connect/2
定义的网络中的所有节点。
您可以使用自己的代码(不使用 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 成员的连接节点。
我有这种类型的知识库:
connect(a, b).
connect(a, d).
connect(a, e).
connect(b, a).
connect(b, c).
...
我的objective是,给定起点和终点,在到达最终节点之前,遍历所有现有节点一次。
到目前为止,这是我得到的:
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).
我使用一个列表来保存我经过的每个节点,在进入递归调用之前,我确保我将要访问的节点不属于该列表。
现在我需要确保在到达最后一个节点之前遍历所有现有节点。我完全不知道如何处理这个问题。我怎么能确定我在到达最后一个节点之前访问了所有其他节点?
您已将网络定义为边列表。收集所有节点的快速而简单的方法是,例如:
findall(X, ( connect(X, _) ; connect(_, X) ), Xs),
sort(Xs, Nodes)
这将首先收集您在 connect/2
中列出的所有 "from" 和 "to",然后通过排序和删除重复项来制作一个集合。
到那时你可以将这个集合与你找到的路径进行比较(在制作一个集合之后)。
显然,您的谓词失败很重要,因为没有路径访问 connect/2
定义的网络中的所有节点。
您可以使用自己的代码(不使用 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 成员的连接节点。