我正在研究分支和绑定和最佳优先搜索我的论文工作，但在网上发现了很多关于这两个概念的矛盾。首先，我认为分支和绑定仅修剪以高成本解决方案结尾的分支（使用启发式）并且不优先搜索（在修剪后对树的其余部分执行简单的 DFS 或 BFS）。但是，后来我发现许多资源说 BB 也对状态进行排名，并优先考虑排名较高的节点（优先搜索）。如果是这样，BB和最佳优先搜索之间到底有什么区别？
问问题
7442 次
1 回答
7
这两个概念是相关的（有时您甚至可以将它们组合起来），但您应该只关注它们之间的根本区别，正如它们的名称所暗示的那样：
分支定界通过对变量进行分支来详尽地探索搜索空间（=测试变量的值）。这会产生几个子问题，例如在二进制变量上的分支会产生一个变量 =0 的问题和一个它 =1 的问题。然后，您可以继续递归地解决它们。该技术的“边界”方面包括估计可以在子问题中获得的解决方案的边界。如果子问题只能产生不好的解决方案（与以前找到的解决方案相比），您可以安全地跳过搜索空间的那部分探索。
最好首先通过首先查看搜索空间中最有趣的部分（最有趣=估计）来尽可能快地找到解决方案。它不会分割搜索空间，只会尝试尽快找到解决方案。
这两种方法都试图跳过对部分搜索空间的调查。它们的使用和效率取决于问题设置。Best first 要求您为“最有趣的探索解决方案”指定一个标准，这有时可能很难/不可能。只有当您可以对子问题施加的界限有意义/不太宽泛时，分支定界才有意义。这取决于您正在考虑的问题...
于 2013-06-25T15:34:36.857 回答