在Prolog中的深度优先搜索。访问节点一次

Question

dfs(S, Visited, Path) :-
    move(S, S2),
    \+member(S2, Visited),
    dfs(S2, [S2|Visited], Path).

您好，

上面的代码是Prolog中dfs的原型。但是，move基于回溯，因此我失去了Visited列表，所以无法确保只访问每个节点一次。 如何在不使用全局变量和类似方法的情况下解决这个问题- 我想使用纯逻辑解决方案。

- Gilgamesz

---

你需要一些额外的逻辑机制来实现这个。但是通常情况下，我们很高兴多次访问节点，只要避免循环即可。请参见path/4以了解避免循环的一般解决方案。 - false

Answer 1

您可以使用迭代（基于栈）的方法来进行深度优先搜索，而不是递归，如如何实现非递归方法的图形深度优先搜索中所解释的那样。

调用Move来检查可能的邻居。这里的区别在于您首先循环遍历可能的候选者。通过始终将它们放在堆栈的前面，我们会迭代地首先进入深度，因为堆栈的顶部将首先被探索。

例如，可以使用findall来查找可能的下一个候选者。 示例：

%% Dfs starting from a root
dfs(Root) :-
    dfs([Root], []).
%% dfs(ToVisit, Visited)
%% Done, all visited
dfs([],_).
%% Skip elements that are already visited
dfs([H|T],Visited) :-
    member(H,Visited),
    dfs(T,Visited).
%% Add all neigbors of the head to the toVisit
dfs([H|T],Visited) :-
    not(member(H,Visited)),
    findall(Nb,move(H,Nb),Nbs),
    append(Nbs,T, ToVisit),
    dfs(ToVisit,[H|Visited]).

- Sam Segers

---

这不是迭代加深算法吗？而且我正在跟踪访问的节点，那么怎么可能有多个呢？ - Sam Segers

你是对的。然而，OP“想使用纯逻辑解决方案”。无论是findall/3还是not都不符合这一要求。 - false