[算法设计与分析-从入门到入土] 分支限界法
个人导航
知乎：https://www.zhihu.com/people/byzh_rc
CSDN：https://blog.csdn.net/qq_54636039
注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码
参考文章：各方资料
文章目录
- [算法设计与分析-从入门到入土] 分支限界法
- 个人导航
- 分支限界法branch and bound
- 1.旅行商问题TSP
分支限界法branch and bound
分支限界法与回溯法均会生成搜索树并寻找解, 但：
- 回溯法：搜索满足特定性质的解（可多个）
- 分支限界法：通常专注于对给定函数进行最大化或最小化计算（核心目标是最优解）
分支限界法的关键在于“界限计算”与“剪枝”:
- 在搜索树的每个节点x处，计算一个界限：该界限代表以x为根的子树后续可能生成的解的取值范围
- 剪枝规则：若当前节点x的界限比已找到的最优界限更差，则剪去以x为根的子树
（不再继续搜索该分支，减少无效计算）
若算法目标是最小化代价函数，该函数需满足以下单调性：
对于所有的部分解( x 1 , x 2 , … , x k − 1 ) (x_1, x_2, \dots, x_{k-1})(x1,x2,…,xk−1)及其扩展解( x 1 , x 2 , … , x k ) (x_1, x_2, \dots, x_k)(x1,x2,…,xk)，必须满足：
cost ( x 1 , x 2 , … , x k − 1 ) ≤ cost ( x 1 , x 2 , … , x k ) \text{cost}(x_1, x_2, \dots, x_{k-1}) \leq \text{cost}(x_1, x_2, \dots, x_k)cost(x1,x2,…,xk−1)≤cost(x1,x2,…,xk)
- 若某个部分解( x 1 , x 2 , … , x k ) (x_1, x_2, \dots, x_k)(x1,x2,…,xk)的代价 ≥ 之前已计算出的最优解代价，则直接舍弃该部分解
- 若已找到代价为c的最优解，任何代价≥c的部分解都无需继续扩展
1.旅行商问题TSP
TSP: Travelling Salesman Problem
给定一组城市，以及每对城市之间的代价函数（可表示距离、时间、费用等），要求找出一条最小代价的回路
该回路需满足“恰好访问每个城市一次，最终回到起点”
下界计算(约减代价矩阵):
对于TSP的任意完整回路，其代价对应代价矩阵中“每一行、每一列各取一个元素”的总和（即每个城市出发和到达各一次）
若从代价矩阵A的任意一行或一列的所有元素中减去一个常数r，则新矩阵中任意回路的代价，比原矩阵A中同一回路的代价恰好减少r
基于此，可通过行/列减常数的操作，构造“约减代价矩阵”——使矩阵的每一行、每一列至少包含一个值为0的元素（简化后续计算）
- A为n×n的原始代价矩阵
- ( r 1 , r 2 , . . . , r n ) (r_1, r_2, ..., r_n)(r1,r2,...,rn)为从矩阵第1行到第n行分别减去的常数
- ( c 1 , c 2 , . . . , c n ) (c_1, c_2, ..., c_n)(c1,c2,...,cn)为从矩阵第1列到第n列分别减去的常数
则任意完整回路代价的一个下界y为：
y = ∑ i = 1 n r i + ∑ i = 1 n c i y = \sum_{i=1}^{n} r_i + \sum_{i=1}^{n} c_iy=i=1∑nri+i=1∑nci
例子:
先将代价矩阵化为约减代价矩阵:
再逐步决策, 更新矩阵:
