algorithm - 分支和界限

Question

有人可以为我解释一下分支定界搜索技术吗？我需要使用分支定界搜索算法从任何随机图的任何开始节点到结束节点找到一条成本最小的路径。

Answer 1

B&B的基本理念是：

1. 当解决一个优化问题（“找到一个满足标准 Y 的 X 以最小化成本 f(X)”）时，你会逐步构建一个解决方案——在任何时间点，你都有一个部分解决方案，它有一个成本。
2. 如果问题的性质是部分解决方案的成本只能保持不变或随着您继续添加部分而增加，那么您知道如果已经有部分解决方案，继续添加部分是没有意义的成本更低的完整解决方案。在这种情况下，您可以放弃（或“修剪”或“深挖”）此部分解决方案的进一步处理。

许多问题都具有后一种性质，使 B&B 成为一种广泛适用的算法技术。

搜索解决方案的过程可以用搜索树来表示，其中根节点表示尚未做出决定的起点，从节点引出的每条边都表示关于要包含在部分解决方案中的某事的决定。每个节点都是一个部分解决方案，包括从根到该节点做出的决策（边）。

示例：如果我们想解决数独难题，根节点将代表仅填写最初提供的数字的棋盘；从这个根开始可能有 9 条边，每条边代表将数字 1-9 分配给左上角单元格的决定。这 9 个部分解决方案节点中的每一个都可以有 8 个分支，表示对位置 (1, 2) 的单元格的有效分配，依此类推。通常，每条边代表程序中的一个递归步骤。

使用 B&B，在最好的情况下，可以尽早找到一个好的解决方案，这意味着可以在根附近修剪搜索树中没有希望的区域；但在最坏的情况下，将生成整个有效解决方案树。出于这个原因，B & B 通常只用于解决没有更快算法已知的问题（例如 NP-hard 问题）。

Answer 2

此链接提供了与 B & B 相关的概念的图形表示。

此链接在可下载的 zip 文件中提供了算法和示例 C# 代码的说明。

希望这可以帮助。

Answer 3

网络上有很多关于分支定界算法的参考资料。

在这里你可以找到一些理论解释。

而 C# 中的代码在这里

Answer 4

很棒的答案@j_random_hacker !!!!

请参阅 Papadimitriou 和 Steiglitz，组合优化中的第 439 页（示例 18.2）。

这本书是经典之作，它讨论了您的确切问题。