在Prolog中进行广度优先搜索 [英] Breadth First Search in Prolog

问题描述

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

I'm new to Prolog and currently implementing DFS (depth-first search) and BFS (breadth-first search) algorithms. My DFS works fine as the code below, but the BFS is terminated and aborted when it reaches the leaf node (it doesn't backtrack and continue searching). I also read some sample code about this but there are some functions they don't define like s(Node, NewNode)... so it's hard to understand, or the version use Queue is too complicated.

这是我的代码：
一些地面函数：

Here is my code: Some ground functions:

%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时：

The Path is something like the Queue list. For example when call DFS:

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

BFS：

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

推荐答案

首先， s（A，B）就像您的 connect2（A，B，_）。

您应该使接口谓词明确：

You should make your interface predicates explicit:

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

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

Maintaining a queue in BFS is not complicated at all. Instead of Visited, have VisitedLists queue (pop from front; add at end; thus 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 ).

达到目标后，路径为实例化：

When the goal is reached, Path is instantiated:

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

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

The interface call needs to be adjusted correspondingly. It should be

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

后记：重复追加 ing当然会导致二次速度减慢，因此为了提高效率，应使用差异列表重新编写（也是一项简单的任务）。

later note: repeated appending of course causes quadratic slowdown, so for efficiency this should be re-written with difference lists (also a straightforward task).

这篇关于在Prolog中进行广度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！