比较深度优先分支定界算法和IDA*搜索算法

Question

我想要比较和了解深度优先、分支和界限算法与IDA*算法之间的精确差异。我浏览了互联网，但我找不到清晰的解释。请帮帮我！

Answer 1

IDA*执行f成本有限深度优先搜索，修剪比当前成本界限更昂贵(使用下界启发式)的路径。它逐渐增加边界，直到找到解决方案。

DFBnB在树中搜索，跟踪到目前为止找到的最佳解决方案，逐渐降低最佳解决方案的成本，直到它是最优的。DFBnB还使用下限启发式来修剪任何比当前最佳解决方案更昂贵的路径。

一些算法，如预算树搜索，可以同时进行两种类型的剪枝-使用当前成本界限和到目前为止找到的最佳解决方案。