阳江市网站建设_网站建设公司_支付系统_seo优化

[算法设计与分析-从入门到入土] 分支限界法

个人导航

知乎：https://www.zhihu.com/people/byzh_rc

CSDN：https://blog.csdn.net/qq_54636039

注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码

参考文章：各方资料

分支限界法branch and bound

分支限界法与回溯法均会生成搜索树并寻找解, 但：

• 回溯法：搜索满足特定性质的解（可多个）
• 分支限界法：通常专注于对给定函数进行最大化或最小化计算（核心目标是最优解）

分支限界法的关键在于“界限计算”与“剪枝”:

1. 在搜索树的每个节点x处，计算一个界限：该界限代表以x为根的子树后续可能生成的解的取值范围
2. 剪枝规则：若当前节点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∑n​ri​+i=1∑n​ci​
例子:

先将代价矩阵化为约减代价矩阵:

再逐步决策, 更新矩阵: