分枝界限法.docx

分枝界限法
算法的基本思想
基本思想
分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也 各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进 行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支） ，并为
每个子集内的解的值计算一个下界或上界（称为定界） 。在每次分支后，对凡是界限超出已知可行解
值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了， 从而缩小了搜索范围。 这一过程一直进行到找出可行解为止， 该可行解的值不大于任何子集的界限。
因此这种算法一般可以求得最优解。
将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。
分枝节点的选择
对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何 子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言） 。怎样选择搜索树上的节点作
为下次分枝的节点呢？有两个原则：
a） 从最小下界分枝（队列式 FIFO分枝限界法）：每次算完界限后，把搜索树上当前所有叶节 点的界限进行比较。找出限界最小的节点，此结点即为下次分枝的结点。
优点：检查子问题较少，能较快地求得最佳解
缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间
b） 从最新产生的最小下界分枝（优先队列式分枝限界法）
从最新产生的各子集中选择具有最小的下界的结点进行分枝。
缺点：节省了空间
缺点：需要较多的分枝运算，耗费的时间较多
这两个原则更进一步说明了，在算法设计中的时空转换概念。
分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、 背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题，分枝与界限的步骤和内容可 能不同，但基本原理是一样的。
算法实现过程（通过推销员问题来说明分支定界法的思想）
1 •型推销员问题
设有5个城 Vi ,V2,V3，V4，V5,从某一城市出发，遍历各城市一次且仅一次，最后返回原地,
求最短路径。其费用矩阵如下:
i； 14
14 00
D= 1 25
16 2
'2 3
1
16
2
25
2
3
9
9
9
oO
6
9
6
□0
将矩阵D对角线以上的元素从小到大排列为:
d13,d15, d24, d25, d45,d34, d35
取最小的5个求和得： d13 - d15 d24 d25 • d45 = 14
（1）
d13 d15 d24
14
d25 d45
表示，要构成一个回路，所以每个顶点的下标在回路的所有边中各出
现两次。（1）中显然
5出现了 3次，若用
d35代替d15则d13
d35 d 24 d25 ' d45 = 21
⑵d13
d35
d24 d25
21
d45
搜索过程可以表示如下图:
d45
d 24 d 25 d 34
d 45
19
图（2）的下界为
21,
（3）的下界为
20,都大于19故没有进一步搜索的价值，因此（
5）为
最佳路径:

即从 Vi到Vj