算法设计与分析 课件 第五章 分支限界

算法设计与分析分支限界的思想分支限界法是一种用于解决优化问题的算法，通过分支来生成解的候选，并使用界限来排除不可能的解，从而有效搜索地找到最优解。简单0/1背包问题的示例：有一个容量为10的背包，和三个物品：物品1：重量6，价值30物品2：重量5，价值14物品3：重量4，价值16求：先择合适物品，转入背包，价值最大的组合。分支限界的简单示例-回溯法图每个节点显示了当前的剩余容量(W)和累计价值(V)。树节点按层从字母A开始编号。节点A：起始点节点N：最优解节点H：无效解灰色节点：搜索节点分支限界的简单示例-分支限界图W:剩余重量V:当前价值UB:上界（当前价值+剩余物品的价值上界），采用分数背包法计算上界。节点A：起始点；节点F：最优解；节点D：超重节点；灰白色节点(C，G)：被剪枝的分支。简单示例-分支限界与回溯法比较W:剩余重量V:当前价值UB:上界（当前价值+剩余物品的价值上界）粉色节点A：起始点；红色节点D：超重节点；绿色节点：最优解；灰色节点(C，G)：被剪枝的分支。这是因为它们的上界低于已知的最佳解（46），所以不需要进一步探索。通过使用准确的上界，算法能更有效地剪枝，减少需要搜索的节点数量。每个节点显示了当前的剩余容量(W)和累计价值(V)。粉色节点(A)：起始点红色节点(H)：超重节点绿色节点(N)：最优解灰色节点：搜索节点除了超重条件触发剪枝之外，其他节点都要搜索到。示例中的两个算法采用的可能解树相同（选择或不选择产生的完全二叉树），搜索方法（DFS）一样。加上一个限界条件后，搜索效率提高了很多。求解问题的核心除了构造可能解树，还有设计好的限界条件！物流派送问题-限界条件的设计最小出边限界法：对于当前访问的城市，可以预先计算其到其他所有未访问城市的最短距离，然后用这个距离加上当前路径长度，如果结果已经超过当前最优路径长度，那么可以剪枝。这种剪枝策略利用了图的局部信息，可以有效减少搜索空间。物流派送问题-限界条件的设计未访问城市最小出边之和限界法：对于当前访问的城市，可以预先计算当前城市的最小出边、所有未访问城市的最小出边，然后用这些最小出边的累加和再加上当前路径长度，如果结果已经超过当前最优路径长度，那么可以剪枝。剪枝条件为：从当前城市出发，再走一遍未访问的城市的可行路线所经过的边长之和一定是大于当前城市的最小出边再加上所有未访问城市的最小出边。这种剪枝策略利用了图的部分信息，也可以有效减少搜索空间。由于未访问城市最小出边之和比未访问城市最小出边数值更大，直观上认为可以更早的提前剪枝，提高算法的效率。物流派送问题-限界条件的设计未访问城市最小出边之和限界法：物流派送问题-限界条件的设计BFS（广度优先搜索）方法和未访问城市最小出边之和的限界法：

当前路径长度加所有未访问城市最小出边之和作为搜索的选择条件和剪枝的下限界。

代码中使用了一个优先队列（使用最小堆实现），以实现广度优先搜索的贪心选择。队列中的元素按照预估的代价

(estimatedCost)

排序，使得具有较小预估代价的状态被优先探索。搜索中某节点的下限界大于当前最佳路径长度，则剪除以此节点为父节点的子树。这有助于减少搜索空间并提高效率。物流派送问题-限界条件的设计BFS（广度优先搜索）方法和未访问城市最小出边之和的限界法：

分支限界算法总结

0/1背包问题的处理：上界条件：在处理0-1背包问题时，使用了上界条件来进行剪枝。上界是指在当前节点下，理论上可能获得的最高价值。如果某个节点的上界已经低于已知的最优解，那么这个节点及其所有子节点都不会产生更高的价值，因此可以被剪枝。物流派送问题的处理：下界条件：在处理物流派送问题时，使用了下界条件来实施剪枝。下界是指在当前决策树节点下，可能获得的最低成本或最小代价。如果某个节点的下界已经高于已知的最优解，那么这个节点及其所有子节点