设计郑宗汉郑晓明第8章分支与限界

1、考：1、分支限界的基本思想2、分支限界的方法3、算法流程4、具体实例，画图5、时间，空间复杂性用回溯法求解问题时, 寻找第一个可行解是盲目搜索, 只有在找到一个可行解之后目标函数的界目标函数的界才有意义。这种搜索是盲目进行的。但从某个e_结点进行搜索时, 先估算目先估算目标函数的界标函数的界, 再确定是否向下搜索的方再确定是否向下搜索的方法法启发人们去寻求另一种搜索模式, 这就是分支与限界法。1) 在分支结点即e_结点上, 估算沿着其各个子结点搜索时, 目标函数可能取得的界界;2) 把子结点子结点和目标函数可能取得的界界保存在一张结点表结点表中(优先队列优先队列或堆堆);/费用矩阵3) 从优先

2、队列或堆中选取界最大界最大(小小)的e_结点向下搜索, 直到叶结点;8.1 分支与限界法的基本思想分支与限界法的基本思想考简答：1.1. 基本思想（基本思想（4 4）4) 若叶结点叶结点的目标函数值目标函数值是结点表结点表中的最大最大(小小)值值, 则该值为问题的最优最优解值解值, 沿该叶结点到根结点的路径所确定的解解是问题的最优解最优解; 若叶结点的目标函数值不是结点表中的最大(小)值, 则继续搜索。这样, 从根结点开始, 每遇到一个e_结点, 就对其各个子结点进行估算, 以此更新结更新结点表点表: 丢弃不需要的结点, 加入新结点。再选取界为极值界为极值的结点, 重复上述过程。随着搜索过程的

3、不断深入, 结点表中目标函数的值越来越接近问题的解。可见, 分支限界法不像回溯法那样盲目地向前搜索, 也不是遇到死结点才往回走, 而是根据结点表中不断更新根据结点表中不断更新的信息的信息来调整自己的搜索方向, 有选有选择、有目标地向前搜索择、有目标地向前搜索; 也不像回溯法那样单纯地沿着父结点一层层地向上回溯, 而是依据结点表中的信息进依据结点表中的信息进行回溯行回溯。2. 目标函数界的特性目标函数界的特性 部分解:(x1,xk); 界: bound(x1,xk)(1)对最小值最小值问题, 称为下界下界, 意思是向下搜索取得的值不会小于不会小于这些下界, 即 bound(x1) bound(x

4、1,x2) bound(x1,x2,xk-1) bound(x1,x2,xk)(2)对最大值最大值问题, 称为上界上界, 意思是向下搜索取得的值不会大于不会大于这些上界, 即 bound(x1) bound(x1,x2) bound(x1,x2,xk-1) bound(x1,x2,xk)3. 分支与限界法的两种典型方式分支与限界法的两种典型方式设解向量解向量x=(x1,x2,xn), 其中 xi的取值范围为有穷集si, |si|=ni,1in。使用分支与限界法求解具体问题时, 可采用下述两种典型方式:(1)从根结点向下搜索时, 分别估算估算n1个子个子结点结点的目标函数的值bound(x1),

5、 把它们保存在结点表中, 并删除根结点删除根结点在结点表中的登记项。再从结点表中选取下界最小选取下界最小(大大)的结点, 作为下一次搜索的起点。 该过程一直持续到叶结点, 得到一个可行解x=(x1,x2,xn)。 若 结 点 表 中 某 结 点 的 下 界 大 于若 结 点 表 中 某 结 点 的 下 界 大 于bound(x1,x2,xn), 则删除之则删除之。(2)从根结点向下搜索时, 预先通过某种方式处理, 从所有子结点中挑选一个从所有子结点中挑选一个作为一个分支结点作为一个分支结点, 目标函数值为bound(x1); 其余子结点的集合作为另一分支, 目标函数值为bound(x1)。再选

6、取界最小界最小(大大)的分支结点的分支结点, 继续上述处理, 直到得到界最小界最小(大大)的叶结点的叶结点为止。该结点对应的解为问题的最优最优解解, 相应的解值为最优解值最优解值。选择方式2时需先解决下述问题: 如何选择分支? 如何计算目标函数的界？4. 复杂性分析复杂性分析方式方式1: 每棵子树ni个分支。最坏情况下, 结点表空间为o(n1n2nn-1)。若为完全n叉树, 则t(n)=o(nn); 若为完全二叉树, 则t(n)=o(2n)方式方式2: 每棵子树2个分支。t(n)=o(2n)8.2.1 费用矩阵的特性及归约费用矩阵的特性及归约引理引理8.1 令g=(v,e)是一个有向赋权图,

7、l是图g的一条hamilton回路, c是图g的费用矩阵, 则回路上的边边对应于费用矩费用矩阵阵中每行每列各一个元素每行每列各一个元素。8.2 tsp问题问题 例如, 5顶点tsp问题的费用矩阵如下图所示, l=v0v3v1v4v2v0是hamilton回路, 回路上的边边对应于费用矩阵中元素c03,c31,c14,c42,c20。每行每列各1元素 25413228518312620167110512562397114321021043定义定义8.1 费用矩阵c的第i行中每个元素减去一个正常数lhi, 得到一个新费用矩阵, 使得新矩阵中第i行的最小元素为0, 该过程称为费用矩阵的行归约行归约。

8、lhi称为行归约常数行归约常数。费用矩阵c的第j列中每个元素减去一个正常数chj, 得到一个新费用矩阵, 使得新矩阵中第j列的最小元素为0, 该过程称为费用矩阵的列归约列归约。chj称为列归列归约常数约常数。 25 41 32 285 18 31 2620 16 7 110 51 25 623 9 7 11 4321021043 0 16 7 30 13 26 2119 15 6 04 45 19 016 2 0 4 lh2=1lh1=5lh0=25lh4=7lh3=62104343210先做行归约，再做列归约ch3=4 0 16 7 30 13 26 2119 15 6 04 45 19 0

9、16 2 0 4 2104343210 0 16 3 30 13 22 2119 15 2 04 45 19 016 2 0 0 2104343210定义定义8.2 对费用矩阵c的每一行和每一列进行行归约行归约和列归约列归约, 得到一个新费用矩阵, 使得新费用矩阵中每一行和每一列至少有一个元素为0, 该过程称为费用矩阵的归约费用矩阵的归约。所得新费用矩阵称为费用矩阵c的归约矩阵归约矩阵。1010niiniichlhh称为矩阵c的归约常数（行归约，列归约归约常数（行归约，列归约的和）的和）。 归约常数h = (25+5+1+6+7)+4 = 48 254132285 1831262016 7 1

10、105125 623 9 7 11 4321021043 0 16 7 30 1326211915 6 04 4519 016 2 0 4 2104343210 0 16 3 30 1322211915 2 04 4519 016 2 0 0 2104343210定理定理8.1 令g=(v,e)是一个有向赋权图, l是图的一条hamilton回路, c是图g的费用矩阵, w(l)是以费用矩阵c计算的回路l的费用。c是c的归约矩阵, 归约常数为h, w (l)是以归约矩阵c计算的回路l的费用, 则有: w(l) = w (l) + h定理定理8.2 令g=(v,e)是一个有向赋权图, l是图g的

11、一条最短最短hamilton回路, c是图g的费用矩阵, c是c的归约矩阵, 令c是图g的费矩阵用, 则 l是图g 的一条最最短短hamilton回路。先求图g的费用矩阵c的归约矩阵归约矩阵, 得到归约常数h, 再求与归约矩阵对应的图g的最短最短hamilton回路, 则w(l) = w (l) + h可见, 图g的最短hamilton回路的费用最少不会少于最少不会少于h。因此, h是tsp问题中根结点根结点x的下界下界。8.2.2 界限的确定和分支的选择界限的确定和分支的选择 1. 界限的确定界限的确定 方式方式2选取沿某一边出发的路径, 作为搜索的一个分支结点, 称为结点结点y; 不沿该边

12、出发的所有其它路径的集合, 作为另一分支结点, 称为结点结点y 。下面以5顶点tsp问题的费用矩阵费用矩阵及其归约矩阵归约矩阵为例, 说明结点结点y及结点结点y 的下界下界的确定方法。 25 41 32 285 18 31 2620 16 7 110 51 25 623 9 7 11 4321021043 0 16 3 30 1322 2119 15 2 04 4519 016 2 0 0 2104343210若选取从v1出发, 沿边(v1,v0)前进, 则该回路的边包含费用c10。由于回路中包含c的每行每列元素各一个, 故c中第1行和第0列的所有元素在后面计算中将不起作用, 可删去。由于回路

13、中肯定不包含边由于回路中肯定不包含边(v0,v1), 否则会构成一个小回否则会构成一个小回路路, 故可把边故可把边(v0,v1)断开断开, 即即置置c01 = 。得如下。得如下44矩阵矩阵:0 16 3 315 2 04519 02 0 0 32044321 16 3 315 2 04519 02 0 0 32044321继续对降阶后的44矩阵进行归约: 16 3 315 2 04519 02 0 0 32044321 13 0 013 2 04319 00 0 0 32044321归约常数为: 3+2=5初始费用矩阵的归约常数为48这表明从v1出发, 经边(v1,v0)的回路费用不会小于不会

14、小于48+5 = 53 结点结点y下界的确定方法下界的确定方法:当搜索深度为m, 并选取(vi,vj) 作为一个分支结点时, 可按下法确定其下界:(1)删去费用矩阵第i行及第j列所有元素, 把n-m阶费用矩阵降阶为n-m-1阶矩阵c;(2)把此后不可能经过的有向边的权此后不可能经过的有向边的权值置为值置为 。这需要和已选择的有向边一起考虑, 有以下几种情况:1) vivj不与已选边相连, 置cji为; 2) vivj与已选边连成vivjvkvl, 置cli为;3) vivj与已选边连成vkvivjvl, 置clk为;4) vivj与已选边连成vkvlvivj, 置cjk为;(3)对降阶后的矩阵

15、c进行归约, 得归约常数归约常数h 。(4)令x表示y的父结点, 则结点结点y的的下界下界w(y)可由下式确定: w(y) = w(x)+h 结点结点y 下界的确定方法下界的确定方法: 不降阶不降阶(1) 因y是沿其它边其它边(非非vivj边边)向下搜索的分支结点, 该分支对应的回路中不包含边vivj, 故可以把y结点相应的费用矩阵中的cij置为 。(2)该分支对应的回路中必包含第i行的某个元素及第j列的某个元素。令dij表示第i行中除cij外的最小元素与第j列中除cij外的最小元素之和, 即minmin, 10, 10kjiknkikjknkijccd(3)结点y的下界: w(y ) = w

16、(x)+dij 25 41 32 285 18 31 2620 16 7110 51 25 623 97 11 4321021043 0 16 3 30 13 22 2119 15 2 04 45 19 016 2 0 0 2104343210考虑上述5顶点tsp问题:归约常数h=48, 根结点w(x)=48从v1出发, 选择非非(v1,v0)边向下搜索,则 y 的的下界下界: w(y )=w(x)+dij=65(1)沿cij=0的方向选择, 使所选择的路线尽可能短;(2)沿dij最大的方向选择, 使w(y)尽可能大。2. 分支的选择分支的选择归约矩阵c中每行每列至少包含一个0元素元素。于是,

17、 选择分支的基本方法选择分支的基本方法:令s是归约矩阵中cij=0的元素集合, dkl是s中使dij最大的元素, 即dkl=maxsdij 则边(vk,vl)为所选择的分支方向。注: dij为第i行除cij外的最小元素与第j列除cij外的最小元素之和。考虑上述5顶点tsp问题,其归约矩阵如右所示: 0 16 3 30 13 22 2119 15 2 04 45 19 016 2 0 0 2104343210dij最大的元素为d10=17, 由此确定所选择的方向为v1v0, 建立分支结点y和y: w(y )= w(x)+dkl= 48+17= 65c01=c10=c24=c34=c42 =c43

18、=0d01=3+2=5, d10=13+4=17 d24=2+0=2, d34=4+0=4d42=0+13=13, d43=0+2=2使用分支限界法的求解过程中, 将动态生成很多结点, 用结点表结点表存放动态生成的结点信息。由于必须按费用的下界费用的下界来确定搜索方向, 故可用优先队列优先队列或堆堆来维护结点表。在此使用最小堆最小堆维护结点表。8.2.3 tsp问题的求解过程问题的求解过程 分支限界法求解分支限界法求解tsp的求解过程的求解过程:(1) 分配堆堆缓冲区, 初始化为空堆;(2) 建立父结点建立父结点x。x的费用矩阵x.c初始化为费用矩阵c, x的费用矩阵的阶x.k初始化为n; 归

19、约x.c得归约常数h, 令结点x的下界x.w=h; 初始化回路的顶点邻接表x.ad;(3) 由归约后的x.c中所有cij=0的元素计算计算dij:minmin, 10, 10kjiknkikjknkijccd(4)选取dij最大的元素dkl, 边vkvl为分支方向;(5)建立子结点建立子结点y 。把x的费用矩阵x.c复制到y .c; 把y.c中元素ckl置为, 得到y.c; 按w(y )=w(x)+dkl计算y的下界y .w; 把x的回路顶点邻接表x.ad复制到y .ad, x.k复制到y .k; 把结点结点y 按y.w插入最小堆;(6)建立子结点建立子结点y。把x的费用矩阵x.c复制到y.c

20、, 把x的回路顶点邻接表x.ad复制到y.ad, x.k复制到y.k; 按回路顶点邻接表y.ad把费用矩阵y.c的有关元素置为的有关元素置为 ;(7)删去删去y.c的第的第k行第行第l列元素列元素, 使y.k减1, 即费用矩阵y.c的阶数减1; 归约降阶后的费用矩阵y.c, 按w(y)=w(x)+h计算结点y的下界y.w;(8)若y.k=2, 直接判断最矩回路的两条边, 并登记到邻接表y.ad, 使y.k=0;(9)把结点结点y按y.w插入最小堆;(10)取堆顶元素作为结点x, 若x.k=0且x.w为结点表结点表中的最大最大(小小)值值, 则算法结束, 否则转(3)计算dij。例例8.1 求解

21、下图所示的5顶点tsp问题。 25 41 32 285 18 31 2620 16 7 110 51 25 623 9 7 11 4321021043 0 16 3 30 1322 2119 15 2 04 4519 016 2 0 0 2104343210解解: 用分支限界法求解5顶点tsp问题 的过程如下: 0 16 3 30 1322211915 2 04 4519 016 2 0 0 2104343210h=48下界下界48a 13 0 013 2 04319 00 0 0 32044321d10=17h=3+2下界下界53 0 16 3 3 0 9 81515 2 00 4519 0

22、12 2 0 0 2104343210下界下界48+17=65bc(1,0)(1,0) 13 0 013 2 04319 00 0 0 32044321h=3+2=5下界下界53b(3,4) 13 011 00 0 4203210 13 0 013 2 024 0 0 0 0 32044321h=19下界下界72d34=19h=2下界下界55de(3,4)0 04221d03=13h=11下界下界66f 0 11 00 0 420321h=13下界下界68g(0,3)(0,3) 0 16 3 3 0 9 81515 2 00 4519 012 2 0 0 2104343210下界下界48+17

23、=65c(3,0)(3,0) 0 16 3 3 0 9 83 15 2 0 4519 00 2 0 0 2104343210h=12下界下界77i0 16 3 0 9 815 2 02 0 0 21044321d30=12h=0下界下界65hh=0下界下界65h(1,2)0 3 2 02 0 4204310 16 3 1 015 2 02 0 0 21044321h=8下界下界73d12=8h=0下界下界65jk(1,2)2 00 4243d01=5h=0下界下界65l420431h=5下界下界70m(0,1)(0,1)0 16 3 0 9 815 2 02 0 0 21044321 0 2

24、00 0 , (3,0), (1,2), (0,1), 得: (3,0)(0,1)(1,2)(2,4)(4,3)8.2.4 几个辅助函数的实现几个辅助函数的实现 结点结点数据结构: 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;n

25、ode *xnode;/父亲结点指针node *ynode;/儿子结点指针node *znode;/儿子结点指针int n_heap;/堆元素个数typedef struct /堆结构数据 node *p; /指向结点元素的指针 type w; /所指结点的下界, 堆元素的关键字 heap; 算法中使用的几个函数算法中使用的几个函数:type row_min(node *node, int row, type &second ); /计算矩阵行的最小值type col_min(node *node, int col, type &second); /计算矩阵列的最小值type

26、array_red(node *node); /归约所指结点的费用矩阵type edge_sel(node *node, int &vk, int &vl); /计算dkl, 选择搜索分支的边void del_rowcol(node *node, int vk, int vl); /删除费用矩阵第vk行、vl列void edge_byp(node *node, int vk, int vl); /登记回路顶点邻接表, 旁路有关边node *initial(type c, int n);/初始化1. row_min函数的实现函数的实现/row_min(node *node,int

27、 row,type &second)函数返回node所指向结点的费用矩阵中第row行的最小值,次小值回送于引用变量second。 type row_min(node *node, int row, type &second)type temp; int i; if (node-crow0crow1) temp = node-crow0; second = node-crow1; else temp = node-crow1; second = node-crow0; for (i=2; ik; i+) if (node-crowicrowi; else if (node-cro

28、wicrowi; return temp; 运行时间: o(n)工作单元个数: (1)2. col_min函数的实现函数的实现type col_min(node *node, int col, type &second)返回node所指结点的费用矩阵中第col列的最小值, 次小值回送于引用变量second。 3. array_red函数的实现函数的实现/type array_red(node *node)归约归约node所指结点的费用矩阵, 返回值为归约常数type array_red(node *node) int i,j; type temp, temp1, sum=0; for

29、(i=0; ik; i+) /行归约 temp = row_min(node,i,temp1); /行归约常数 for (j=0; jk; j+) node-cij -= temp; sum += temp; /行归约常数累计 for (j=0;jk;j+) /列归约 temp = col_min(node, j, temp1); /列归约常数 for (i=0; ik; i+) node-cij -= temp; sum +=temp; /列归约常数累计 return sum; /返回归约常数 运行时间: o(n2) 工作单元: (1)4. edge_sel函数的实现函数的实现/函数edge

30、_sel计算dkl, 选择搜索分支的边。返回dkl的值、出边顶点序号和入边顶点序号。type edge_sel(node * node, int &vk, int &vl)int i,j; type temp, d=0; type *row_value = new typenode-k; type *col_value = new typenode-k; for (i=0; ik; i+) /每一行的次小值 row_min(node, i, row_valuei); for (i=0;ik;i+) /每列的次小值 col_min(node,i,col_valuei); for

31、(i=0; ik, i+) /对费用矩阵的所有0元素 for (j=0;jk;j+) /计算temp值 if (node-cij=0) temp=row_valuei+col_valuej; if (tempd) /求最大的temp值 d=temp; vk=i; vl=j; delete row_value; delete col_value; return d; 运行时间: o(n2); 工作单元: o(n)5. 函数函数del_rowcol的实现的实现/函数del_rowcol删除费用矩阵当前第vk行、第vl列的所有元素 void del_rowcol(node *node,int vk,

32、int vl)int i,j,vk1,vl1; for (i=vk;ik-1;i+) /元素上移 for (j=0;jcij = node-ci+1j; for (j=vl;jk-1;j+) /元素左移 for (i=0;icij = node-cij+1; for (i=vk;ik-1;i+) /元素上左移 for (j=vl;jk-1;j+) node-cij = node-ci+1j+1; vk1 = node-row_initvk;/当前行vk转换为原始行vk1 node-row_curvk1 = -1;/原始行vk1置删除标志 for (i= vk1+1;irow_cur-; vl1

33、 = node-col_initvl; /当前列vl转换为原始列vl1 node-col_curvl1 = -1; /原始列vk1置删除标志 for (i=vl1+1;icol-cur-; for (i=vk;ik-1;i+) /修改vk及 其后的当前行的对应原始行号 node-row_initi=node-row_initi+1; for (i=vl;ik-1;i+) /修改vl及 其后的当前列的对应原始列号 node-col_initi=node-col_initi+1; node-k-; /当前矩阵的阶数减1 运行时间: o(n2); 工作单元: (1)6. 函数函数edge_byp的实

34、现的实现/函数edge_byp把vk行、vl列所表示的边, 登记到回路顶点邻接表, 旁路矩阵中有关的边 void edge_byp(node *node,int vk,int vl)int i,j,k,l; vk = row_initvk;/当前行号转换为原始行号 vl=col_initvl;/当前列号转为原始列号 node-advk = vl;/登记顶点邻接表 for (i=0;iadj!=-1) /检查从顶点i开始的通路 j = node-adj; if (i!=j) /存在一起点为i终点为j的通路 l=node-row_curj; /j转为当前行号l k=node-col_curi; /

35、i转为当前列号k if (k0)&(l0) /当前行列号均处于当前矩阵中 node-clk=maxvalueoftype; 运行时间: o(n2); 工作单元: (1)7. initial函数的实现函数的实现node *initial(type c, int n)int i,j; node *node = new node;/分配结点缓冲区 for (i=0; in; i+) /拷贝费用矩阵初始数据 for (j=0;jcij = cij; for (i=0;irow_initi = i; /行列号对应关系 node-col_initi = i; node-row_curi = i; node-col_curi = i; for (i=0;iadi = -1;node-k = n;return node; 运行时间: o(n2); 工作单元: (1)算法算法8.1 tsp问题的分支限界算法输入: 邻接矩阵c, 顶点个数n输出: 最短路费用w及邻接顶点表adtemplate type tsp(type c, int n, int ad)int i, j, vk, vl, n_heap=0; type d,w; node *xnode, *ynode,