Prolog 中的广度优先搜索

Question

我是 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,
    append(Visited, [T|Extend], Visited2),
    append(Path, [T|Extend], [Next|Path2]),
    breadth_first(Next, Goal, Visited2, Path2).

路径类似于队列列表。例如调用 DFS 时：

?- depth_first(1, 28, [1], P).

BFS:

?- breadth_first(1, 28, [1], []).

Answer 1

首先，s(A,B)的通常概念就像你的connect2(A,B,_)。

你应该使你的接口谓词显式：

depth_first( Start, Goal, Path):-
    depth_first( Start, Goal, [Start], Path).

在 BFS 中维护队列一点也不复杂。而不是 Visited，而是 VisitedLists 队列（从前面弹出；在末尾添加；因此 FIFO）：

consed( A, B, [B|A]).

bfs( Goal, [Visited|Rest], Path) :-                     % take one from front
    Visited = [Start|_],            
    Start \== Goal,
    findall( X,
        ( connected2(X, Start, _), \+ member(X, Visited) ),
        [T|Extend]),
    maplist( consed(Visited), [T|Extend], VisitedExtended),      % make many
    append( Rest, VisitedExtended, UpdatedQueue),       % put them at the end
    bfs( Goal, UpdatedQueue, Path ).

目标达成后，Path实例化：

bfs(Goal, [[Goal|Visited]|_], Path):- 
    reverse([Goal|Visited], Path).

接口调用需要相应调整。应该是

breadth_first( Start, Goal, Path):- bfs( Goal, [[Start]], Path).

稍后注意： 重复 appending 当然会导致二次减速，因此为了提高效率，这应该用差异列表重写（也是一个简单的任务）。

Prolog 中的广度优先搜索

Breadth First Search in Prolog

breadth-first-search

prolog