第八章 分支与限界.doc

1、1第八章 分支与限界8.1 分支与限界法的基本思想一、基本思想：1、在 结点估算沿着它的各儿子结点搜索时，目标函数可能取得的“界”，_e2、把儿子结点和目标函数可能取得的“界”，保存在优先队列或堆中，3、从队列或堆中选取“界”最大或最小的 结点向下搜索，直到叶子结点，_e4、若叶子结点的目标函数的值，是结点表中的最大值或最小值，则沿叶子结点到根结点的路径所确定的解，就是问题的最优解，由该叶子结点所确定的目标函数的值，就是解这个问题所得到的最大值或最小值二、目标函数“界”的特性：是部分解， 是相应的界),()21kxx ),(),(211kxboundxbound1、对最小值问题，称为下界，意思

2、是向下搜索所可能取得的值最小不会小于这些下界。若 是所得到的部分解，满足：),(21kxX（8.1.1）),(),( 2121 kxboundxboundbound 2、对最大值问题，称为上界，意思是向下搜索所可能取得的值最大不会大于这些上界。若 是所得到的部分解，满足：),(21kxX ),(),( 21211 kxboundxboundbound 三、两种分支方法：设解向量 ， 的取值范围为有穷集 ， ， 。),2x i iSiin|i11、每棵子树都有 个分支：i最坏情况下，结点表的空间为 ，)(21nnO若状态空间树是完全 叉树， ，结点表的空间为 。n )(nO2、每棵子树只有两个分

3、支， 取特定值的分支、及不取特定值的分支：ix状态空间树是完全二叉树，最坏情况下结点表的空间为 )2(n8.2 货郎担问题有向赋权图 ，顶点集 。),(EVG),(10nvV为图的邻接矩阵， 表示顶点 到顶点 的关联边的长度，又把 称为费用矩阵。cijcivj c28.2.1 费用矩阵的特性及归约：图 的最短哈密尔顿回路，lG：回路的费用。因为中的元素 表示顶点 到顶点 的关联边的费用，)(wijcivj一、哈密尔顿回路与费用矩阵的关系：引理 8.1 令 是一个有向赋权图， 是图 的一条哈密尔顿回路， 是图),(EVlGc的费用矩阵，则回路上的边对应于费用矩阵 中每行每列各一个元素。c证明 图

4、 有 个顶点，Gn费用矩阵第 行元素：顶点 到其它顶点的出边费用；iiv费用矩阵第 列元素：其它顶点到顶点 的入边费用。iv是图 的一条哈密尔顿回路，l是回路中的任意一个顶点， ，iv 10n在回路中只有一条出边，对应于费用矩阵中第 行的一个元素；i在回路中只出现一次，费用矩阵的第 行有且只有一个元素与其对应。i i在回路中只有一条入边，费用矩阵中第 列也有且只有一个元素与其对应。v回路中有 个不同顶点，费用矩阵的每行每列都有且只有一个元素与回路中的顶n点的出边与入边一一对应。例：，图 8.1(a)中 5 城市的货郎担问题的费用矩阵，令 是哈密尔顿回路，回路上的边对应于费用矩阵中的元素0241

5、30vl。310,cc 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 25 41 32 28 0 0 16 7 3 lh0 =25 0 0 16 3 3 1 5 18 31 26 1 0 13 26 21 lh1 =5 1 0 13 2 21 2 20 16 7 1 2 19 15 6 0 lh2 =1 2 19 15 2 0 3 10 51 25 6 3 4 45 19 0 lh3 =6 3 4 45 19 0 4 23 9 7 1 4 16 2 0 4 lh4 =7 4 16 2 0 0 ch3 =4 （ a） （ b） （ ） 图 8.1 5 城市货郎担问题的费用矩阵及

6、其归约二、费用矩阵的归约1、行归约和列归约定义 8.1 费用矩阵 的第 行（或第 列）中的每个元素减去一个正常数 (或 )，cij ilhjc得到一个新的费用矩阵 ，使得 中第 行（或第 列）中的最小元素为 0，称为费用矩阵ij的行归约(或列归约)。称 为行归约常数，称 为列归约常数。ilhch例：把图 8.1(a)中归约常数 ， ， ， ， 。250l1l12l63lh74l列归约常数 ，所得结果如图 8.1(c)所示。43c2、归约矩阵3定义 8.2 对费用矩阵 的每一行和每一列都进行行归约和列归约，得到一个新的费用c矩阵 ，使得 中每一行和每一列至少都有一个元素为 0，称为费用矩阵的归约

7、。矩阵 称c c为费用矩阵 的归约矩阵。称常数 h（8.2.1）10niiiclh为矩阵 的归约常数。c例：对图 8.1(a)中的费用矩阵进行归约，得到图 8.1(c)所示归约矩阵。归约常数 h为 4876152h3、归约矩阵与哈密尔顿回路的关系定理 8.1 有向赋权图 ， 的哈密尔顿回路 ， 的费用矩阵 ， 是以),(EVGlGc)(lw计算的回路费用。 是 的归约矩阵，归约常数为 ， 是以 计算的回路费用，有：cch)(wc（8.2.2）hlwl)(证明 和 分别是 和 的第 行第 列元素，ijijcij， jilc 1,0,ni是以 计算的哈密尔顿回路的费用，令)(l ljicl,)(是

8、 计算的同一条哈密尔顿回路的费用，令)(lwcljilw,)(由引理 8.1，回路上的边对应于 中每行每列各一个元素。有chlwclhlwnjjiiljilji )()( 10,定理证毕。定理 8.2 有向赋权图 ， 是 的最短哈密尔顿回路， 是 的费用矩阵，),(EVGl cG是 的归约矩阵，令 是图 的邻接矩阵，则 也是 的最短的哈密尔顿回路。ccG证明 用反证法证明。若 不是图 的最短的哈密尔顿回路，l则 中必存在另一条回路 ，是 中最短的哈密尔顿回路，*l同时，它也是 中的一条回路。G和 分别是以 计算的 和 的费用，有：)(lw)*lcl*其中， 是正整数。)(*lw是 的一条回路，

9、令 和 是分别以 计算的回路 和 的费用。*l )(*lcl*4由定理 8.1，有 hlwl)( hlwl)()(*其中， 是费用矩阵 的归约常数。因此hclll )()(*是 中比 更短的哈密尔顿回路，与定理的前提相矛盾。*lGl所以， 也是 的最短的哈密尔顿回路。8.2.2 界限的确定和分支的选择先求图 费用矩阵 的归约矩阵 ，得到归约常数cch再转换为求取与 相对应的图 的最短哈密尔顿回路问题。G和 分别是 和 的最短哈密尔顿回路的费用，)(lwl有 。h)(的最短哈密尔顿回路的费用，最少不会少于 。Gh是货郎担问题状态空间树中根结点 的下界。h XXw)(例：图 8.1(a)中归约常数

10、 48 便是该问题的下界。该问题的最小费用不会少于 48。8.2.2.1 界限的确定1、搜索策略选取沿某一边出发的路径，作为分支结点 ；Y不沿该边出发的其它所有路径集合，作为另一个分支结点 。Y2、选取沿 方向的路径时，结点 下界 的确定),(ji )(w的哈密尔顿回路 ，费用矩阵 ，以 计算的回路费用 。Glc)(lw是 的归约矩阵，归约常数为 ，以 计算的回路费用 ，chlwhllwij)()(1） ，处理不可能经过的边ji2）矩阵降阶，删去第 行第 列所所有元素，得到降阶后的矩阵ij c3）归约 ，得归约常数 ，有c )(hlwl)(hcllijhYw例：图 8.1(a)及图 8.1(c

11、)的 5 城市货郎担问题的费用矩阵、及其归约矩阵。选取从顶点 出发，沿着 的边前进，1v),(01v则该回路的边包含费用矩阵中的 。c删去 中的第 1 行和第 0 列的所有元素， c素 置为。01图 8.1(c)中 55 的归约矩阵，降阶为图 8.2(b)所示的 44 的矩阵。5进一步进行归约，得到图 8.2(c)所示的归约矩阵，其归约常数为 5。表明沿 出发，经边 的回路，其费用至少不会小于 485 = 53。1v),(01v 0 1 2 3 4 1 2 3 4 1 2 3 4 0 0 16 3 3 0 16 3 3 0 13 0 0 lh0 =3 1 0 13 2 21 2 15 2 0

12、2 13 2 0 2 19 15 2 0 3 45 19 0 3 43 19 0 3 4 45 19 0 4 2 0 0 4 0 0 0 4 16 2 0 0 ch1 =2 （ a） （ b） （ c） 图 8.2 Y 结点对费用矩阵的降阶处理4）处理不可能经过的边：(1) 不和其它已经选择的边相连接，把 置为，如图 8.3(a)所示；jiv jic(2) 和以前选择的边连接成 ，把 置为，如图 8.3(b)所示；lkjivl(3) 和以前选择的边连接成 ，把 置为，如图 8.3(c)所示；k(4) 和以前选择的边连接成 ，把 置为，如图 8.3(d)所示；jiljc j l l j k j

13、i i i j k i k l (a) (b) (c) (d) 图 8.3 选择有向边时的几种可能情况5） 父亲结点 ，下界 ，降阶后的归约常数为 ，结点 的下界为X)(whY（8.2.3）hY)(3、不沿 方向的结点 下界 的确定,ji )(Y1）回路不包含 边， 置为。（不降阶）jivijc2） （8.2.4）mnn,10,10 kjikjkijd3）结点 的下界为：Y（8.2.5）ijdXw)()例：在图 8.1(a)中，根结点作为父亲结点 ，则 。X48)(w选择边 向下搜索作为结点为 ，结点为 的下界为：),(01vY53)()h结点 的下界为：Y 6148)() ijdXwY68.

14、2.2.2 分支的选择选择分支的思想方法：1. 沿 的方向选择，使所选择的路线尽可能短；0ijc2. 沿 最大的方向选择，使 尽可能大；d)(Yw令 是 的元素集合， 是 中使 达最大的元素 ，即：Sij klDSijdkld（8.2.6）maxijSkldD边 就是所选择的分支方向。lkv例：图 8.1(a)中的费用矩阵归约为 8.1(c)中矩阵，根结点的下界 48)(Xw有 ，搜索方向的选择如下：043234210ccc5d171d2024d34 33。170Dkl所选择的方向为边 ，据此建立结点 和 。此时，01vY（8.2.7）klDXwY)()8.2.3 货郎担问题的求解过程结点数据

15、结构： typedef struct node_data Type cnn; /* 费用矩阵 */int row_initn; /* 费用矩阵的当前行映射为原始行 */int col_initn; /* 费用矩阵的当前列映射为原始列 */int row_curn; /* 费用矩阵的原始行映射为当前行 */int col_curn; /* 费用矩阵的原始列映射为当前列 */int adn; /* 回路顶点邻接表 */int k； /* 当前费用矩阵的阶 */Type w; /* 结点的下界 */ NODE;分支限界法求解货郎担问题的求解过程：1. 分配堆缓冲区，初始化为空堆；2. 建立结点 ，

16、拷贝到 ， 初始化为 ；归约 ，计算归约常数 ，下XccX.k.ncX. h界 ；初始化回路的顶点邻接表 ；hw. ad3. 按(8.2.4)式，由 中所有 的元素 ，计算 ；.0ijijcij4. 按(8.2.6)式，选取使 达最大的元素 作为 ，选择边 作为分支方向；ijdklklDlkv75. 建立儿子结点 ， 拷贝到 ， 拷贝到 ， 拷贝到 ；把 中的YcX.cY.adX.adY.kX.kY.c.置为，归约 ；计算结点 的下界 ；把结点 按 插入最小堆中； klc ww6. 建立儿子结点 ， 拷贝到 ， 拷贝到 ， 拷贝到 ； 的.有关元素置为；7. 降阶 , 减 1，归约降阶后的 ，

17、按(8.2.3)式计算结点 的下界 ； cY.kcY. Y.8. 若 ，直接判断最短回路的两条边，并登记于路线邻接表 ，使 ；2 ad.0k9. 把结点 按 插入最小堆中；w.10. 取下堆顶元素作为结点 ，若 ，算法结束；否则，转 3；X0.k例 8.1 求解图 8.1(a)所示的 5 城市货郎担问题。该问题的求解过程如图 8.4 所示，过程如下： 0 1 2 3 4 0 0 16 3 3 下 界 =48 1 0 13 2 21 2 19 15 2 0 3 4 45 19 0 4 16 2 0 0 A 1 2 3 4 (1,0) (1,0) 0 1 2 3 4 0 13 0 0 下 界 =5

18、3 0 0 16 3 3 下 界 =65 2 13 2 0 1 0 9 8 3 43 19 0 2 15 15 2 0 4 0 0 0 3 0 45 19 0 下 界 =5 (3,4) B (3,4) 下 界 =72 4 12 2 0 0 1 2 3 1 2 3 4 下 界 =65 (3,0) C (3,0) 下 界 =7 0 13 0 0 13 0 0 1 2 3 4 0 1 2 3 4 2 1 0 2 13 2 0 0 0 16 3 0 0 16 3 3 4 0 0 3 24 0 1 0 9 8 1 0 9 8 （ 0,3） D (0,3) 4 0 0 0 2 15 2 0 2 3 15

19、2 0 1 2 1 2 3 E 4 2 0 0 3 45 19 0 0 2 0 0 (1,2) H (1,2) 4 0 2 0 0 0 4 2 1 0 1 3 4 1 2 3 4 I F 4 0 0 0 0 3 下 界 =65 0 0 16 3 下 界 =73 下 界 =6 G 2 2 0 1 1 0 下 界 =68 4 2 0 2 15 2 0 (0,1) J (0,1) 4 2 0 0 1 3 1 3 4 K 下 界 =65 2 2 0 0 0 下 界 =70 4 0 2 2 0 L 4 0 0 M 图 8.4 用分支限界法解 5 城市货郎担问题的过程88.2.4 几个辅助函数的实现数据结

20、构： typedef struct node_data Type cnn; /* 费用矩阵 */int row_initn; /* 费用矩阵的当前行(下标)映射为原始行(内容) */int col_initn; /* 费用矩阵的当前列(下标)映射为原始列(内容)*/int row_curn; /* 费用矩阵的原始行(下标)映射为当前行(内容) */int col_curn; /* 费用矩阵的原始列(下标)映射为当前列(内容) */int adn; /* 回路顶点邻接表 */int k； /* 当前费用矩阵的阶 */Type w; /* 结点的下界 */ NODE;NODE *xnode; /*

21、 父亲结点指针 */NODE *ynode; /* 儿子结点指针 */NODE *znode; /* 儿子结点指针 */int n_heap; /* 堆元素个数 */typedef struct /* 堆结构数据 */NODE *p; /* 指向结点元素的指针*/Type w; /* 所指向结点的下界,堆元素的关键字 */ HEAP; ：与顶点 （出）相邻接的顶点（入）序号。iadi例：的回路由边 、 、 、 、 组成，数组 中的登记情况：03v214v1034vad 0 1 2 3 4 ad 1 2 4 0 3 图 8.5 回路顶点邻接表的登记情况算法中使用下面的几个函数：Type row_

22、min(NODE * node ,int row,Type 4. int i;5. if (node-crow0crow1) 6. temp = node-crow0; second = node-crow1;7. 8. else 9. temp = node-crow1; second = node-crow0;10. 11. for (i=2;ik;i+) 12. if (node-crowicrowi;14. 15. else if (node-crowicrowi;17. 18. return temp;19. 运行时间： 。)(nO工作单元个数： 。12、Type col_min(N

23、ODE * node ,int col,Type 4. Type temp,temp1,sum = 0;5. for (i=0;ik;i+) /* 行归约 */6. temp = row_min(node,i,temp1); /* 行归约常数 */107. for (j=0;jk;j+)8. node-cij -= temp;9. sum += temp; /* 行归约常数累计 */10. 11. for (j=0;jk;j+) /* 列归约 */ 12. temp = col_min(node,j,temp1); /* 列归约常数 */13. for (i=0;ik;i+)14. node-

24、cij -= temp;15. sum += temp; /* 列归约常数累计 */16. 17. return sum; /* 返回归约常数*/18. 运行时间： 时间。)(2nO工作单元个数： 。14、函数 edge_sel 计算 ，选择搜索分支的边。返回 的值，出边顶点序号 和入klDklDvk边顶点序号 。vl1. Type edge_sel(NODE * node,int 4. Type temp,d = 0;5. Type *row_value = new Typenode-k;6. Type *col_value = new Typenode-k;7. for (i=0;ik;i

25、+) /* 每一行的次小值 */8. row_min(node,i,row_valuei);9. for (i=0;ik;i+) /* 每一列的次小值 */10. col_min(node,i,col_valuei);11. for (i=0;ik,i+) /* 对费用矩阵所有值为 0 的元素*/12. for (j=0;jk;j+) /* 计算相应的 temp 值 */13. if (node-cij=0) 14. temp = row_valuei + col_valuej;15. if (tempd) /* 求最大的 temp 值于 d */16. d = temp; vk = i; vl = j;17. /* 保存相应的行、列号 */18. 19. 20.