Prolog中的广度优先

Question

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

不服用无限分支？

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

Answer 1

宽度优先的优势在于您可以找到所有解决方案。随着深度优先，你可以陷入无限的分支。

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

如果你想使用它，你需要明确地使用某种类型的队列来实现它。

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

Answer 2

有一些我知道的“议程搜索”。在遍历树（数据，关系，规则......）时，你维护一个关于接下来要做什么的“议程”（列表）。当你进入一个节点时，你把他的孩子放在议程上，然后继续你弹出的议程的第一个元素。这样，如果您在议程末尾添加新项目，则可以获得宽度优先。如果你把它们放在议程前面，你可以先深入研究。

用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之间切换，并与结果一起玩。该算法在记忆方面表现相当好，因为议程，仍然需要探索的节点，只能捕捉树中任何时候（所谓的边缘）的（或多或少）小部分节点。

Answer 3

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

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