分枝界限法
什么是分枝界限法
分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解[1]。
分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解[2]。
分枝界限法的基本思想[3]
1、基本思想
分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。
2、分枝节点的选择
对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言）。怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原则：
1）从最小下界分枝（队列式FIFO分枝限界法）：每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点，此结点即为下次分枝的结点。
2）从最新产生的最小下界分枝（优先队列式分枝限界法）：从最新产生的各子集中选择具有最小的下界的结点进行分枝。
优点：节省了空间；
缺点：需要较多的分枝运算，耗费的时间较多。
这两个原则更进一步说明了，在算法设计中的时空转换概念。
分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。
分枝界限法的步骤[4]
分枝界限法是组合优化问题的有效求解方法，其步骤如下所述：
步骤一：假如问题的目标为最小化，则设定目前最优解的值Z=∞
步骤二：根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。
步骤三：计算每一个新分枝出来的节点的下限值（Lower bound，LB）
步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：
步骤五：判定是否仍有尚未被洞悉的节点，假如有，则进行步骤二，假如已无尚未被洞悉的节点，则演算停止，并得到最优解。
Kolen等曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节点数范围为6-15。当节点数为6时，计算机演算所花费的时间大约1分钟（计算机型为VAZ11/785），当节点数扩大至12时，计算机有内存不足的现象产生，所以分枝定界法比较适用于求解小型问题。Held和Karp指出分枝定界法的求解效率，与其界限设定的宽紧有极大的关系。
分枝界限法的算法实例[3]
1、型推销员问题
设有5个城v1,v2,v3,v4,v5 ,从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。其费用矩阵如下：
trix}infty%26amp;14%26amp;1%26amp;16%26amp;2\ 14%26amp;infty%26amp;25%26amp;2%26amp;3\1%26amp;25%26amp;infty%26amp;9%26amp;9\16%26amp;2%26amp;9%26amp;infty%26amp;6\2%26amp;3%26amp;9%26amp;6%26amp;inftyend{bmatrix}">
将矩阵D对角线以上的元素从小到大排列为：
d13,d15,d24,d45,d34,d35KKKK
取最小的5个求和得：d13 + d15 + d24 + d45 = 14
用
width="178" height="53">表示，要构成一个回路，所以每个顶点的下标在回路的所有边中各出现两次。（1）中显然5出现了3次，若用d35代替d15则d13 + d35 + d24 + d25 + d45 = 21即
width="208" height="55">
搜索过程可以表示如下图：
width="504" height="367">
图（2）的下界为21，图（3）的下界为20，都大于19故没有进一步搜索的价值，因此（5）为最佳路径：
2、型推销员问题
D = (dij)n * n即
。不妨把D看成旅费，即从vi到vj的旅费与vj到vi不一样。
trix}infty%26amp;24%26amp;34%26amp;14%26amp;15\ 19%26amp;infty%26amp;20%26amp;9%26amp;6\7%26amp;9%26amp;infty%26amp;6%26amp;8\23%26amp;10%26amp;22%26amp;infty%26amp;7\20%26amp;8%26amp;11%26amp;20%26amp;inftyend{bmatrix}">
对D的每行减去该行的最小元素，或每列减去该列的最小元素，得一新矩阵，使得每行每列至少都有一个0元素。
width="486" height="121">
第一列和第三列没有为0的元素，所以第一列和第三列分别减去其最小元素1和3得：
trix}infty%26amp;10%26amp;17%26amp;0%26amp;1\ 12%26amp;infty%26amp;11%26amp;3%26amp;0\0%26amp;3%26amp;infty%26amp;0%26amp;2\15%26amp;3%26amp;12%26amp;infty%26amp;0\11%26amp;0%26amp;0%26amp;12%26amp;inftyend{bmatrix}_{45}">
由于从任一vi出发一次，进入vi也是一次，所以问题等价于求trix}infty%26amp;10%26amp;17%26amp;0%26amp;1\ 12%26amp;infty%26amp;11%26amp;3%26amp;0\0%26amp;3%26amp;infty%26amp;0%26amp;2\15%26amp;3%26amp;12%26amp;infty%26amp;0\11%26amp;0%26amp;0%26amp;12%26amp;inftyend{bmatrix}_{45}">
的最佳路径，下标45是估计的界，即旅费起码为45单位（每个点出发都去最小值）。
由于矩阵D第一行第四列元素为0，故从v1出发的路径应选择v1 %26minus; %26minus; v4，为了排除v1出发进入其他点和从其他点进入v4的可能，并封锁v4到v1的路径，在矩阵中除去第一行和第四列，并将第四列第一行元素15改为∞。得：
trix}12%26amp;infty%26amp;11%26amp;0\ 0%26amp;3%26amp;infty%26amp;2\infty%26amp;3%26amp;12%26amp;0\11%26amp;0%26amp;0%26amp;inftyend{bmatrix}_{45}">
类似的从v2出的路径应选v2 %26minus; %26minus; v5，消第v2行和第v5列，并将第v5行第v2列元素改为∞得：
trix}0%26amp;3%26amp;infty\infty%26amp;3%26amp;12\11%26amp;infty%26amp;0end{bmatrix}_{45}">
这时第二行没有0元素，减去最小元素3得：
trix}0%26amp;3%26amp;infty\infty%26amp;0%26amp;9\11%26amp;infty%26amp;0end{bmatrix}_{45}">
搜索过程如下图：
width="557" height="488">
最后得到最佳路径为：
分枝界限法的算法分析[3]
1、算法优点：可以求得最优解、平均速度快。
因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。
2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。
存在的问题：分支定界法可应用于大量组合优化问题。其要害技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别。
参考文献
分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解[1]。
分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解[2]。
分枝界限法的基本思想[3]
1、基本思想
分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。
2、分枝节点的选择
对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言）。怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原则：
1）从最小下界分枝（队列式FIFO分枝限界法）：每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点，此结点即为下次分枝的结点。
优点：检查子问题较少，能较快地求得最佳解；
缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间。
2）从最新产生的最小下界分枝（优先队列式分枝限界法）：从最新产生的各子集中选择具有最小的下界的结点进行分枝。
优点：节省了空间；
缺点：需要较多的分枝运算，耗费的时间较多。
这两个原则更进一步说明了，在算法设计中的时空转换概念。
分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。
分枝界限法的步骤[4]
分枝界限法是组合优化问题的有效求解方法，其步骤如下所述：
步骤一：假如问题的目标为最小化，则设定目前最优解的值Z=∞
步骤二：根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。
步骤三：计算每一个新分枝出来的节点的下限值（Lower bound，LB）
步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：
此节点的下限值大于等于Z值。
已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，燕以此为可行解的值。
此节点不可能包含可行解。
步骤五：判定是否仍有尚未被洞悉的节点，假如有，则进行步骤二，假如已无尚未被洞悉的节点，则演算停止，并得到最优解。
Kolen等曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节点数范围为6-15。当节点数为6时，计算机演算所花费的时间大约1分钟（计算机型为VAZ11/785），当节点数扩大至12时，计算机有内存不足的现象产生，所以分枝定界法比较适用于求解小型问题。Held和Karp指出分枝定界法的求解效率，与其界限设定的宽紧有极大的关系。
分枝界限法的算法实例[3]
1、型推销员问题
设有5个城v1,v2,v3,v4,v5 ,从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。其费用矩阵如下：
trix}infty%26amp;14%26amp;1%26amp;16%26amp;2\ 14%26amp;infty%26amp;25%26amp;2%26amp;3\1%26amp;25%26amp;infty%26amp;9%26amp;9\16%26amp;2%26amp;9%26amp;infty%26amp;6\2%26amp;3%26amp;9%26amp;6%26amp;inftyend{bmatrix}">将矩阵D对角线以上的元素从小到大排列为：
d13,d15,d24,d45,d34,d35KKKK
取最小的5个求和得：d13 + d15 + d24 + d45 = 14
用
width="178" height="53">表示，要构成一个回路，所以每个顶点的下标在回路的所有边中各出现两次。（1）中显然5出现了3次，若用d35代替d15则d13 + d35 + d24 + d25 + d45 = 21即width="208" height="55">搜索过程可以表示如下图：
width="504" height="367">图（2）的下界为21，图（3）的下界为20，都大于19故没有进一步搜索的价值，因此（5）为最佳路径：
2、型推销员问题
D = (dij)n * n即
。不妨把D看成旅费，即从vi到vj的旅费与vj到vi不一样。trix}infty%26amp;24%26amp;34%26amp;14%26amp;15\ 19%26amp;infty%26amp;20%26amp;9%26amp;6\7%26amp;9%26amp;infty%26amp;6%26amp;8\23%26amp;10%26amp;22%26amp;infty%26amp;7\20%26amp;8%26amp;11%26amp;20%26amp;inftyend{bmatrix}">对D的每行减去该行的最小元素，或每列减去该列的最小元素，得一新矩阵，使得每行每列至少都有一个0元素。
width="486" height="121">第一列和第三列没有为0的元素，所以第一列和第三列分别减去其最小元素1和3得：
trix}infty%26amp;10%26amp;17%26amp;0%26amp;1\ 12%26amp;infty%26amp;11%26amp;3%26amp;0\0%26amp;3%26amp;infty%26amp;0%26amp;2\15%26amp;3%26amp;12%26amp;infty%26amp;0\11%26amp;0%26amp;0%26amp;12%26amp;inftyend{bmatrix}_{45}">由于从任一vi出发一次，进入vi也是一次，所以问题等价于求
trix}infty%26amp;10%26amp;17%26amp;0%26amp;1\ 12%26amp;infty%26amp;11%26amp;3%26amp;0\0%26amp;3%26amp;infty%26amp;0%26amp;2\15%26amp;3%26amp;12%26amp;infty%26amp;0\11%26amp;0%26amp;0%26amp;12%26amp;inftyend{bmatrix}_{45}">的最佳路径，下标45是估计的界，即旅费起码为45单位（每个点出发都去最小值）。
由于矩阵D第一行第四列元素为0，故从v1出发的路径应选择v1 %26minus; %26minus; v4，为了排除v1出发进入其他点和从其他点进入v4的可能，并封锁v4到v1的路径，在矩阵中除去第一行和第四列，并将第四列第一行元素15改为∞。得：
trix}12%26amp;infty%26amp;11%26amp;0\ 0%26amp;3%26amp;infty%26amp;2\infty%26amp;3%26amp;12%26amp;0\11%26amp;0%26amp;0%26amp;inftyend{bmatrix}_{45}">类似的从v2出的路径应选v2 %26minus; %26minus; v5，消第v2行和第v5列，并将第v5行第v2列元素改为∞得：
trix}0%26amp;3%26amp;infty\infty%26amp;3%26amp;12\11%26amp;infty%26amp;0end{bmatrix}_{45}">这时第二行没有0元素，减去最小元素3得：
trix}0%26amp;3%26amp;infty\infty%26amp;0%26amp;9\11%26amp;infty%26amp;0end{bmatrix}_{45}">搜索过程如下图：
width="557" height="488">最后得到最佳路径为：
分枝界限法的算法分析[3]
1、算法优点：可以求得最优解、平均速度快。
因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。
2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。
存在的问题：分支定界法可应用于大量组合优化问题。其要害技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别。
参考文献
- ↑ 邓宇佑(硕士).求解医院运输部门运输中心个数最佳化之研究
- ↑ 《作业研究》[M].第七章 整数规划
- ↑ 3.03.13.2 分枝界限法
- ↑ 夏新海.物流配送车辆调度优化研究[D].武汉理工大学,2004年
热门专栏
热门词条
应收账款
区域货币
区间估计
金融危机
资本成本
CPI（Consumer Price Index）
汇率
资产
经济
美元
单向定单
租赁期
外汇通
服务
外汇佣金
SME
ISO
认可
增量成本
什一税
CFO
MIT
加工
销售
MG金融集团
股价反弹
抽签偿还
股利收入
技术
空头陷阱
资本
REF
市场
中国股市
中小企业
备付金率
美国
两会
价格
吊空
指数
股灾
葡萄牙币
调至市价
pt
清算
电子汇兑
税粮
下降三角形
FDI
Writer
外汇
银行
投资
管理
阴烛
MACD
width
冲账
Theta
短期同业拆借
货币
peg
外汇交易法
金融中介理论
企业
艾略特波段理论的含义
消费发展战略
黄金
巴塞尔资本协议
贴现现金流
联系汇率制度
拔档
美国贝勒大学
汇差清算率
延期付款汇票
产品
短期国际商业贷款
Exposure
集中竞价
计期汇票
金融
标准普尔（S&P）
公司
不完全竞争市场理论 (金融)
正利差
分期付款汇票
软通货
出口物价指数
资金
选择权买方
百分比回撤
无记名汇票最低报价戴维·凯特标准·普尔 500指数抵押品持平德国工业产值德国消费者物价指数成本协同效益
股票
非农就业人口
交易
道琼斯公用事业平均指数
持平
指示汇票
产品竞争力
财务指标 盈利能力比率
德国伊弗研究所景气调查
外汇实盘交易方式
外汇实盘交易指令
国际收支差额