小编Trầ*_*Tín的帖子

我是 Prolog 的新手，目前正在实现 DFS（深度优先搜索）和 BFS（广度优先搜索）算法。我的 DFS 工作正常，如下面的代码，但 BFS 在到达叶节点时终止并中止（它不会回溯并继续搜索）。我还阅读了一些关于此的示例代码，但是有一些函数没有定义，例如 s(Node, NewNode)...所以很难理解，或者版本使用 Queue 太复杂。

这是我的代码：一些地面功能：

%connected(+Start, +Goal, -Weight)
connected(1,7,1).
connected(1,8,1).
connected(1,3,1).
connected(7,4,1).
connected(7,20,1).
connected(7,17,1).
connected(8,6,1).
connected(3,9,1).
connected(3,12,1).
connected(9,19,1).
connected(4,42,1).
connected(20,28,1).
connected(17,10,1).

connected2(X,Y,D) :- connected(X,Y,D).
connected2(X,Y,D) :- connected(Y,X,D).

next_node(Current, Next, Path) :-
    connected2(Current, Next, _),
    not(member(Next, Path)).

DFS 实现：

depth_first(Goal, Goal, _, [Goal]).
depth_first(Start, Goal, Visited, [Start|Path]) :-
    next_node(Start, Next_node, Visited),
    write(Visited), nl,
    depth_first(Next_node, Goal, [Next_node|Visited], Path).

BFS 实现：

breadth_first(Goal, Goal, _,[Goal]).
breadth_first(Start, Goal, Visited, Path) :-
    findall(X,
            (connected2(X,Start,_),not(member(X,Visited))),
            [T|Extend]),
    write(Visited), nl, …