Prolog中的广度优先

Question

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

没有采取无限的分支？

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

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

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