中国科学技术大学算法导论课件（全套12讲）之分支限界法

简介：
本课程件为中国科学技术大学《算法导论》系列教学资源之一，专注于讲解分支限界法。涵盖十二个专题讲座，全面解析该方法在问题求解中的应用与技巧。 ### 分支限界法知识点详解 #### 一、分支限界法概述 分支限界法是一种在计算机科学领域用来搜索解空间树以寻找最优解的方法，特别适用于需要找到最佳解决方案的问题。 **基本思想：** 该方法的核心在于通过剪枝策略裁减那些不能带来最优结果的子树，在探索过程中提高效率。通常采用广度优先或最小耗费最大收益的方式进行搜索。 **搜索策略：** 在扩展节点时，分支限界法会生成所有可能的儿子结点，并从当前活跃结点列表中选择下一个要扩展的结点。为了更有效地做出这个选择，会在每个活结点处计算一个函数值（优先级），并根据这些数值来挑选最有潜力的结点进行进一步搜索。 #### 二、分支限界法与回溯法的区别 1. **求解目标不同：** - 回溯法通常用于找到所有符合约束条件的解决方案。 - 分支限界法则更侧重于快速定位一个最优解，而非寻找所有的可行方案。 2. **搜索方法差异：** - 回溯采取深度优先策略进行探索。 - 而分支限界则倾向于使用广度优先或最佳优先的方法来遍历问题空间。 3. **扩展结点的方式不同：** - 在分支限界中，每个活跃节点仅被选为扩展节点一次，并且一旦选择就会生成所有儿子节点。 - 回溯法则允许一个节点多次成为扩展对象进行探索。 4. **存储需求差异：** - 相较于回溯法，分支限界通常需要更多的内存空间来保存搜索过程中产生的结点信息，尤其是在广度优先的场合下更为明显。 #### 三、分支限界法求解步骤 1. **定义问题的空间范围**：明确所有可能解决方案构成的集合。 2. **构建解空间树结构**：将上述可能性组织成一棵树的形式，其中每个节点代表一个特定的状态或选择。 3. **采用广度优先搜索等方式进行探索** - 保证每一个活结点仅被扩展一次； - 每次从当前活跃列表中选取最有利的结点作为新的起点； - 根据限界策略剔除那些无法导向最优解的新生成节点； - 将剩下的新生成节点加入到待处理队列，继续选择和拓展下一个最有前景的节点。 - 直至所有潜在解决方案都被检查完毕。 #### 四、分支限界法的具体实现 ##### 1. 队列式(FIFO)分支限界法 - **特点**：活结点表按照先进先出的原则进行管理，类似于队列结构； - **应用场景**：适用于需要按顺序处理节点的情况； ##### 2. 优先级队列式分支限界法 - **特点**: 每个结点根据其对应的状态价值或耗费量来决定优先级。 - **应用场景**：适合于寻找具有最小成本或者最大收益的解的问题。 #### 五、应用实例分析 **0-1背包问题** - **描述**：给定一系列物品和一个限制容量的背包，每种物品都有其重量和价值。目标是选择合适的组合放入包中以使总价值最大化而不超过负载。 - **解决方案空间**: 包含所有可能的选择方案； - **解空间树结构**: 通过二叉树的形式展示每个物品是否被加入背包的一种或多种可能性。 **单源最短路径问题** - **描述**：给定一个有向图，其中每条边有一个权重值。目标是从一个特定的起始节点出发找到到达其他所有顶点的最小距离。 - **解空间树**: 以起点为根构造一棵树，每个结点代表从初始状态到某个中间位置的状态转移； - **搜索策略**：利用优先级队列分支限界法按照路径长度进行优先选择。 #### 六、总结 分支限界方法是一种解决最优化问题的有效技术，特别适合于解空间庞大但可以通过剪枝减少探索范围的场景。通过采用适当的搜索和修剪策略可以显著提高求解效率。