使用序言防止深度优先搜索循环

Question

有什么方法可以防止这段代码中的循环。

move(a,b).
move(b,a).
move(a,c).
move(b,d).
move(b,e).
move(d,h).
move(d,i).
move(e,j).
move(e,k).
move(c,f).
move(c,g).
move(f,l).
move(f,m).
move(g,n).
move(g,o).
goal(n).


goSolveTheMaze(Start,Way) :-
    dfs(Start, Way),!.

dfs(Goal, [Goal]) :-
   goal(Goal),!.

dfs(Start, [Start|Way])  :-
    move(Start, N),
    dfs(N, Way).

所以当 move(a,b) 移动到 (b,c) 时不要回到 (b,a), 当运行 goSolveTheMaze(a,path) 时。输出应该是 path=[a,c,g,n]。 ..................................................... ........................ ..................................................... ............

Answer 1

如果您向 dfs 添加第三个参数（您已经访问过的地方的列表）会怎么样？然后，您可以使用 \+/1 and member/2 来避免回到您去过的地方。

例如，如果您使用以下内容：

move(a,b).
move(b,a).
move(a,c).
move(b,d).
move(b,e).
move(d,h).
move(d,i).
move(e,j).
move(e,k).
move(c,f).
move(c,g).
move(f,l).
move(f,m).
move(g,n).
move(g,o).
goal(n).


goSolveTheMaze(Start,Way) :-
    dfs(Start, Way, [Start]),!.

dfs(Goal, [Goal], _) :-
   goal(Goal),!.

dfs(Start, [Start|Way], Visited)  :-
    move(Start, N),
    \+ member(N, Visited),
    dfs(N, Way, [N|Visited]).

然后查询：

?- goSolveTheMaze(a, X).

将产生结果：

X = [a, c, g, n]

更新回复评论“你能告诉我 \+ 做什么吗？”：

\+ 谓词在其论证无法证明时为真。因此，在上面的示例中，行 \+ member(N, Visited) 表示“当 N 不是访问列表的成员时”。

参见：https://www.swi-prolog.org/pldoc/man?predicate=%5C%2B/1

使用序言防止深度优先搜索循环

Prevent cycle in Depth first search using prolog

artificial-intelligence

prolog

depth-first-search