Prolog中的广度优先

3 回答

• 7

  广度优先的优势在于您将找到所有解决方案 . 使用深度优先，您可以陷入无限分支 .

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

  如果你想使用它，你需要用某种队列明确地实现它 .

  Edit: 如果您希望在不使用大量内存的情况下获得广度优先搜索的优势，则可以使用迭代深化 . 这是深度优先搜索，具有深度限制，您可以连续增加 . 这会导致一些重复计算，但是如果您的搜索空间没有长线性延伸而没有分支，则此重复很小 .

  回复于 2024-04-29T02:59:39+08:00
• 4

  我必须知道下一步该做什么的“议程”（列表） . 当您输入节点时，将其子项放在议程上，然后继续执行您弹出的议程的第一个元素 . 这样，如果你把新项目放在议程的最后，那么你就会获得广度优先 . 如果你把它们放在议程的前面，你就会获得深度优先 .

  使用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
  

  我也找到了议程搜索on this web page的一些解释 . 议程搜索的好处在于您可以轻松地在两个变量df和bf之间切换并使用结果 . 该算法在记忆方面非常良好，因为议程仍然是要探索的节点，在任何时候（所谓的边缘）仅捕获树中的（或多或少）小部分节点 .

  回复于 2024-04-29T02:59:39+08:00
• 7

  agenda_search的代码应该可以正常工作 . 为了提高效率，您可能希望考虑使用其他数据结构;实际上，在广度优先模式中，整个节点列表（T）将通过追加（T，C，A）遍历 . 例如，您可以使用SICStus中的库（队列）模块 . 广度优先搜索将如下所示（由谓词start / 1，后继谓词s / 2和目标谓词目标/ 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).
  

  （您还可以尝试通过更好的数据结构替换/补充Path组件;例如，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的书（人工智能逻辑编程）应该是阅读这些材料的好资料 .

  回复于 2024-04-29T02:59:39+08:00