9

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

不取无限分支？

在 Prolog 中有没有使用广度优先的一般方法？我一直在谷歌搜索，我没有找到太多对新手有用的信息。

4

3 回答 3

7

广度优先的优点是你会找到所有的解决方案。使用深度优先，您可能会陷入无限分支。

缺点是广度优先占用大量内存，因此一般不用于执行。

如果你想使用它，你需要用某种队列显式地实现它。

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

于 2009-04-21T07:10:46.680 回答
7

我知道一些事情是“议程搜索”。在遍历树（数据、关系、规则……）时，您会维护下一步要做什么的“议程”（列表）。当您输入一个节点时，您将其子节点放在议程上，然后继续处理您弹出的议程的第一个元素。这样，如果您将新项目放在议程的末尾，您将获得广度优先。如果你把它们放在议程的前面，你就会得到深度优先。

使用 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，这些谓词代表您希望对每个节点执行的操作（例如，将节点数据与搜索词进行比较、序列化节点内容、asf.）。这getNodeChildren会将给定节点的子节点列表绑定到C（即这个谓词实际上知道树结构以及如何找到子节点）。当然，doWithNode谓词可能需要额外的参数来完成它的工作，这也会出现在agenda_search.

你可以像这样调用它：

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

和

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

我还在这个网页上找到了一些关于议程搜索的解释。议程搜索的好处是您可以轻松地在 df 和 bf 两个变体之间切换并使用结果。该算法在内存方面表现得非常好，作为议程，仍有待探索的节点在任何时候仅捕获（或多或少）一小部分节点（所谓的边缘）。

于 2009-07-22T08:20:48.717 回答
4

议程搜索的代码应该可以正常工作。为了提高效率，您可能希望考虑使用另一种数据结构；实际上，在广度优先模式下，整个节点列表 (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（下一个，路径，NQ，Res）。

bfs2(H,Path,_NQ,Res) :- 目标(H), reverse([H|Path],Res)。
bfs2(H,Path,NQ,Res) :-  
              findall(e(Succ,[H|Path]),
                      (s(H,Succ),\+ 成员(Succ,Path)),AllSuccs),
              queue_append(NQ,AllSuccs,NewQueue),
              bfs1（新队列，Res）。

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

开始（环境（0,0））。
s(env(X,Y),env(X1,Y)) :- X1 是 X+1。
s(env(X,Y),env(X,Y1)) :- Y1 是 Y+1。
目标（环境（3,3））。

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

于 2010-04-22T06:56:36.263 回答