Prolog中的广度优先搜索算法

Question

在Prolog中使用广度优先搜索方案的一般想法是什么？

不选择无限分支？

在Prolog中使用广度优先搜索的一般方法是否存在？我已经在Google上搜索了一些资料，但对于新手来说并没有找到太多有用信息。

- Ricardo

Answer 1

我听说过“议程搜索”。在遍历数据、关系、规则等树状结构时，您需要维护一个“议程”（即列表），以确定下一步要做什么。当您进入一个节点时，将其子节点放入议程中，并继续处理议程的第一个元素，然后将其弹出。这样，如果您将新项放在议程末尾，可以实现广度优先搜索；如果将它们放在议程前面，则可以实现深度优先搜索。

使用Prolog很容易实现它。

编辑：在这里我可能会给出一个实现提示。这是议程搜索算法的基本实现。

agenda_search([N|T],Mode):-
    doWithNode(N),           % do whatever you do the searching for
    getNodeChildren(N,C),
    (Mode=bf ->              % bf or df (depth-first)
        append(T,C,A);
        append(C,T,A)),
    agenda_search(A,Mode).

它依赖于外部谓词 doWithNode ，表示您要对每个节点执行的操作（例如，将节点数据与搜索术语进行比较，序列化节点内容等）。而 getNodeChildren 会将给定节点的子项列表绑定到 C 上（即，此谓词实际上知道树结构及如何查找子节点）。当然， doWithNode 谓词可能需要其他参数来完成其工作，这些参数也会显示在 agenda_search 的参数列表中。

您可以像这样调用它：

agenda_search([RootNode], bf)   % for breadth-first search

并且

agenda_search([RootNode], df)   % for depth-first search

我还在这个网页上找到了一些关于议程搜索的解释。议程搜索的好处是你可以很容易地在df和bf两种变体之间切换并尝试不同的结果。算法在内存方面表现良好，因为议程（即仍需探索的节点）每次只捕捉树中的一小部分节点（即所谓的边缘节点）。

- ThomasH

Answer 2

广度优先搜索的优点是可以找到所有解决方案。深度优先搜索可能会陷入无限分支中。

缺点是广度优先搜索使用了大量内存，因此通常不用于执行。

如果您想使用它，您需要使用某种类型的队列来显式实现它。

编辑：如果您想在不使用太多内存的情况下获得广度优先搜索的优势，则可以使用迭代加深。这是带有深度限制的深度优先搜索，您可以逐步增加深度限制。这会导致一些重复计算，但如果您的搜索空间没有长时间的线性伸展而没有分支，则这种重复计算很小。

- starblue

Answer 3

agenda_search的代码应该可以正常工作。 为了提高效率，你可能希望考虑使用另一种数据结构；事实上，在广度优先模式下，整个节点列表(T)将被append(T,C,A)遍历。 例如，您可以使用SICStus的library(queues)模块。 广度优先搜索将如下所示（由谓词start/1、后继谓词s/2和目标谓词goal/1参数化）。请注意，我还添加了循环检查。

bfs(Res) :- start(Start), empty_queue(EQ),
  queue_append(EQ,[e(Start,[])],Q1),
  bfs1(Q1,Res).
bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue),
   bfs2(Next,Path,NQ,Res).
bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res).
bfs2(H,Path,NQ,Res) :-  
              findall(e(Succ,[H|Path]),
                      (s(H,Succ),\+ member(Succ,Path)),AllSuccs),
              queue_append(NQ,AllSuccs,NewQueue),
              bfs1(NewQueue,Res).

（您还可以尝试用更好的数据结构替换/补充路径组件；例如，AVL树。） 一个要解决的示例问题是：

start(env(0,0)).
s(env(X,Y),env(X1,Y)) :- X1 is X+1.
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1.
goal(env(3,3)).

您还可以通过使用启发式函数计算优先级来替换队列。然后，您将得到A*搜索（它可以模拟深度优先、广度优先、最佳优先等）。 Bratko的书（人工智能逻辑编程）应该是阅读这些材料的好来源。

- Michael