分支限界法和最佳优先搜索之间的区别

Question

我正在研究我的论文工作中的分支限界和最佳优先搜索，但发现网络上关于这两个概念存在很多矛盾。起初我认为分支限界只是通过剪枝高成本解决方案的分支（使用启发式），并且不优先考虑搜索（在修剪后的树的其余部分上执行简单的DFS或BFS）。然而，后来我发现许多资源也说BB对状态进行排名，并首先考虑具有更高排名的节点（一种优先搜索）。如果是这样，那么BB和最佳优先搜索之间到底有什么区别呢？

- Barpa

Answer 1

这两个概念相关（有时甚至可以将它们结合使用），但您应该专注于它们的基本差异，因为它们的名称所示：

分支定界通过对变量进行分支（=测试变量的值）来全面探索搜索空间。这会创建几个子问题，例如在二进制变量上进行分支会创建一个变量=0的问题和一个变量=1的问题。然后，您可以继续递归地解决它们。技术的“边界”方面涉及估计可以在子问题中获得的解决方案的界限。如果子问题只能产生糟糕的解决方案（与先前找到的解决方案相比），则可以放心跳过搜索空间的那部分。

最佳优先尝试尽快找到解决方案，首先查看搜索空间的最有趣部分（最有趣=估计）。它不会分割搜索空间，只会尝试尽快达到一个/某个解决方案。

这两种方法都尝试跳过搜索空间的部分调查。它们的使用和效率取决于问题设置。最佳优先需要您指定“探索最有趣解决方案”的标准，这有时可能很难/不可能。分支定界仅在您可以对子问题进行有意义/不太宽泛的限制时才有趣。这取决于您考虑的问题...

- Origin

---

我理解的是：最佳优先搜索仅考虑到达状态的成本（即从根状态到该状态的成本总和）进行排名，但BB使用估计的通过该状态获得完整解决方案的最小成本。我理解的对吗？ - Barpa

不，最佳优先搜索尝试使用全局成本估计来选择下一个要处理的节点，而不仅仅是当前成本。考虑一个导航问题，你可以使用Dijkstra算法创建最短路径树。只看到达当前状态的成本正是Dijkstra算法所做的，通过选择具有最低暂定距离的节点来解决下一个节点。通过将最佳优先搜索应用于它，您可以得到A算法，因为在A中，您始终选择具有最低总成本估计的节点。 - Origin

抱歉，但我现在更加困惑了。您说最佳优先选择下一个节点时使用全局成本估计。难道全局成本估计不是分支限界用于与当前状态边界进行比较的全局界限（下限或上限）吗？ - Barpa

这取决于您的问题设置，可能是相同的。请记住，最佳优先是一种选择标准（“我将调查哪个当前状态”），而分支限界更多地基于先前结果进行修剪（如果已经找到更好的解决方案，则可以丢弃状态，因为它们只会导致不良解决方案）。正如我之前所说，这两种方法有时可以结合使用，绝对不是互斥的。 - Origin

回答不错，但评论中有些混淆。请记住，A是最佳优先搜索算法的一个例子。最佳优先搜索根据评估节点的函数f，首先探索最有前途的节点。这个函数f可以由两部分组成，g（已知确定值）和h（启发式估计）。对于A，f=g+h。但你也可以有一个只使用f=g的最佳优先算法，或者另一个最佳优先算法（通常称为“贪婪”，但这个形容词有很多含义，并且在许多情况下使用），它只使用f=h。 - dolphin