设计郑宗汉郑晓明分支与限界.pptx

《设计郑宗汉郑晓明分支与限界.pptx》由会员分享，可在线阅读，更多相关《设计郑宗汉郑晓明分支与限界.pptx（65页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第8章 分支与限界 用回溯法求解问题时,寻找第一个可行解是盲目搜索,只有在找到一个可行解之后目标函数的界才有意义。这种搜索是盲目进行的。但从某个e_结点进行搜索时,先估算目标函数的界,再确定是否向下搜索的方法启发人们去寻求另一种搜索模式,这就是分支与限界法。第1页/共65页1)在分支结点即e_结点上,估算沿着其各个子结点搜索时,目标函数可能取得的界;2)把子结点和目标函数可能取得的界保存在一张结点表中(优先队列或堆);/费用矩阵3)从优先队列或堆中选取界最大(小)的e_结点向下搜索,直到叶结点;8.1 分支与限界法的基本思想考简答：1.1.基本思想（4 4）分支限界是先估算目标函数的界，再确定

2、是否继续向下搜索的分支限界是先估算目标函数的界，再确定是否继续向下搜索的方法。方法。第2页/共65页4)若叶叶结结点点的目目标标函函数数值值是结结点点表表中的最最大大(小小)值值,则该值为问题的最最优优解解值值,沿该叶结点到根结点的路径所确定的解解是问题的最优解最优解;若叶结点的目标函数值不是结点表中的最大(小)值,则继续搜索。这样,从根结点开始,每遇到一个e_结点,就对其各个子结点进行估算,以此更新结点表:丢弃不需要的结点,加入新结点。再选取界为极值的结点,重复上述过程。第3页/共65页随着搜索过程的不断深入,结点表中目标函数的值越来越接近问题的解。可见,分支限界法不像回溯法那样盲目地向前搜

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

4、1)bound(x1,x2,xk)第5页/共65页3.分支与限界法的两种典型方式设解向量X=(x1,x2,xn),其中xi的取 值 范 围 为 有 穷 集 Si,|Si|=ni,1in。使用分支与限界法求解具体问题时,可采用下述两种典型方式:第6页/共65页(1)从根结点向下搜索时,分别估算n1个子结点的目标函数的值bound(x1),把它们保存在结点表中,并删除根结点在结点表中的登记项。再从结点表中选取下界最小(大)的结点,作为下一次搜索的起点。该过程一直持续到叶结点,得到一个可行解X=(x1,x2,xn)。若结点表中某结点的下界大于bound(x1,x2,xn),则删除之。第7页/共65页

5、(2)从根结点向下搜索时,预先通过某种方式处理,从所有子结点中挑选一个作为一个分支结点,目标函数值为bound(x1);其余子结点的集合作为另一分支,目标函数值为bound(x1)。再选取界最小(大)的分支结点,继续上述处理,直到得到界最小(大)的叶结点为止。该结点对应的解为问题的最优解,相应的解值为最优解值。选择方式2时需先解决下述问题:如何选择分支?如何计算目标函数的界？第8页/共65页4.复杂性分析方式1:每棵子树ni个分支。最坏情况下,结点表空间为O(n1n2nn-1)。若为完全n叉树,则T(n)=O(nn);若为完全二叉树,则T(n)=O(2n)方式2:每棵子树2个分支。T(n)=O

6、(2n)第9页/共65页8.2.1 费用矩阵的特性及归约引理8.1令G=(V,E)是一个有向赋权图,l是图G的一条Hamilton回路,c是图G的费用矩阵,则回路上的边对应于费用矩阵中每行每列各一个元素。8.2 TSP问题 第10页/共65页例如,5顶点TSP问题的费用矩阵如下图所示,l=v0v3v1v4v2v0是Hamilton回路,回路上的边对应于费用矩阵中元素c03,c31,c14,c42,c20。每行每列各1元素25413228518312620167110512562397114321021043第11页/共65页定义8.1费用矩阵c的第i行中每个元素减去一个正常数lhi,得到一个新

7、费用矩阵,使得新矩阵中第i行的最小元素为0,该过程称为费用矩阵的行归约。lhi称为行归约常数。费用矩阵c的第j列中每个元素减去一个正常数chj,得到一个新费用矩阵,使得新矩阵中第j列的最小元素为0,该过程称为费用矩阵的列归约。chj称为列归约常数。第12页/共65页 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先做行归约，再做列归约第13页/共65页ch3=

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

9、5125 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第16页/共65页定理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第17页/共65页定理8.2 令G=(V,E)是一个有向赋权图,l是图G的一条

10、最短Hamilton回路,c是图G的费用矩阵,c是c的归约矩阵,令c是图G的费矩阵用,则l是图G 的一条最短Hamilton回路。第18页/共65页先求图G的费用矩阵c的归约矩阵,得到归约常数h,再求与归约矩阵对应的图G的最短Hamilton回路,则w(l)=w(l)+h可见,图G的最短Hamilton回路的费用最少不会少于h。因此,h是TSP问题中根结点X的下界。8.2.2 界限的确定和分支的选择 第19页/共65页1.界限的确定 方式2选取沿某一边出发的路径,作为搜索的一个分支结点,称为结点Y;不沿该边出发的所有其它路径的集合,作为另一分支结点,称为结点Y。下面以5顶点TSP问题的费用矩阵

11、及其归约矩阵为例,说明结点Y及结点Y 的下界的确定方法。第20页/共65页 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列的所有元素在后面计算中将不起作用,可删去。第21页/共65页由于回路中肯定不包含边(v0,v1),否则会构成一个小回路,故可把边(v0,v1)断开,即置c01=。得如下

12、44矩阵:0 16 3 315 2 04519 02 0 0 32044321 16 3 315 2 04519 02 0 0 32044321第22页/共65页继续对降阶后的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)的回路费用不会小于48+5=53第23页/共65页结点Y下界的确定方法:当搜索深度为m,并选取(vi,vj)作为一个分支结点时,可按下法确定其下界:(1)删去费用矩阵第i行及第j列所有元素,

13、把n-m阶费用矩阵降阶为n-m-1阶矩阵c;(2)把此后不可能经过的有向边的权值置为。这需要和已选择的有向边一起考虑,有以下几种情况:第24页/共65页1)vivj不与已选边相连,置cji为;2)vivj与已选边连成vivjvkvl,置cli为;3)vivj与已选边连成vkvivjvl,置clk为;4)vivj与已选边连成vkvlvivj,置cjk为;第25页/共65页(3)对降阶后的矩阵c进行归约,得归约常数h。(4)令X表示Y的父结点,则结点Y的下界w(Y)可由下式确定:w(Y)=w(X)+h 第26页/共65页结点Y 下界的确定方法:不降阶(1)因Y是沿其它边(非vivj边)向下搜索的分

14、支结点,该分支对应的回路中不包含边vivj,故可以把Y结点相应的费用矩阵中的cij置为。(2)该分支对应的回路中必包含第i行的某个元素及第j列的某个元素。令dij表示第i行中除cij外的最小元素与第j列中除cij外的最小元素之和,即(3)结点Y的下界:w(Y)=w(X)+dij第27页/共65页 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出发

15、,选择非(v1,v0)边向下搜索,则Y 的下界:w(Y)=w(X)+dij=65第28页/共65页(1)沿cij=0的方向选择,使所选择的路线尽可能短;(2)沿dij最大的方向选择,使w(Y)尽可能大。2.分支的选择归约矩阵c中每行每列至少包含一个0元素。于是,选择分支的基本方法:第29页/共65页令S是归约矩阵中cij=0的元素集合,dkl是S中使dij最大的元素,即dkl=maxSdij则边(vk,vl)为所选择的分支方向。注:dij为第i行除cij外的最小元素与第j列除cij外的最小元素之和。第30页/共65页考虑上述5顶点TSP问题,其归约矩阵如右所示:0 16 3 30 13 22

16、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=0d01=3+2=5,d10=13+4=17d24=2+0=2,d34=4+0=4d42=0+13=13,d43=0+2=2第31页/共65页使用分支限界法的求解过程中,将动态生成很多结点,用结点表存放动态生成的结点信息。由于必须按费用的下界来确定搜索方向,故可用优先队列或堆来维护结点表。在此使用最小堆维护结点表。8.2.3 TSP问题的求解过

17、程 第32页/共65页分支限界法求解TSP的求解过程:(1)分配堆缓冲区,初始化为空堆;(2)建立父结点X。X的费用矩阵X.c初始化为费用矩阵c,X的费用矩阵的阶X.k初始化为n;归约X.c得归约常数h,令结点X的下界X.w=h;初始化回路的顶点邻接表X.ad;(3)由归约后的X.c中所有cij=0的元素计算dij:(4)选取dij最大的元素dkl,边vkvl为分支方向;第33页/共65页(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;把结

18、点Y 按Y.w插入最小堆;(6)建立子结点Y。把X的费用矩阵X.c复制到Y.c,把X的回路顶点邻接表X.ad复制到Y.ad,X.k复制到Y.k;按回路顶点邻接表Y.ad把费用矩阵Y.c的有关元素置为;第34页/共65页(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

19、。第35页/共65页例8.1求解下图所示的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问题的过程如下:第36页/共65页 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

20、81515 2 00 4519 012 2 0 0 2104343210下界48+17=65BC(1,0)(1,0)第37页/共65页 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)第38页/共65页 0 16 3 3 0 9 81515 2 00 4519 012 2 0

21、 0 2104343210下界48+17=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下界65H第39页/共65页h=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

22、 21044321 0 2 00 0 非非(1,0)(1,0),(3,0),(1,2),(0,1),得:(3,0)(0,1)(1,2)(2,4)(4,3)第40页/共65页8.2.4 几个辅助函数的实现 结点数据结构:typedefstructnode_dataTypecnn;/*费用矩阵introw_initn;/*矩阵当前行映射为原始行intcol_initn;/*矩阵当前列映射为原始列introw_curn;/*矩阵原始行映射为当前行intcol_curn;/*矩阵原始列映射为当前列intadn;/*回路顶点邻接表intk;/*当前费用矩阵的阶Typew;/*结点的下界Node;第41页

23、/共65页NODE*xnode;/父亲结点指针NODE*ynode;/儿子结点指针NODE*znode;/儿子结点指针intn_heap;/堆元素个数typedef struct/堆结构数据NODE*p;/指向结点元素的指针Typew;/所指结点的下界,堆元素的关键字HEAP;第42页/共65页算法中使用的几个函数:Typerow_min(NODE*node,introw,Type&second);/计算矩阵行的最小值Type col_min(NODE*node,int col,Type&second);/计算矩阵列的最小值Typearray_red(NODE*node);/归约所指结点的费用

24、矩阵Typeedge_sel(NODE*node,int&vk,int&vl);/计算dkl,选择搜索分支的边第43页/共65页voiddel_rowcol(NODE*node,intvk,intvl);/删除费用矩阵第vk行、vl列void edge_byp(NODE*node,int vk,intvl);/登记回路顶点邻接表,旁路有关边NODE*initial(Typec,intn);/初始化第44页/共65页1.row_min函数的实现/row_min(NODE*node,int row,Type&second)函数返回node所指向结点的费用矩阵中第row行的最小值,次小值回送于引用变

25、量second。Typerow_min(NODE*node,introw,Type&second)Typetemp;inti;if(node-crow0crow1)temp=node-crow0;second=node-crow1;elsetemp=node-crow1;second=node-crow0;第45页/共65页for(i=2;ik;i+)if(node-crowicrowi;elseif(node-crowicrowi;returntemp;运行时间:O(n)工作单元个数:(1)第46页/共65页2.col_min函数的实现Type col_min(NODE*node,int c

26、ol,Type&second)返回node所指结点的费用矩阵中第col列的最小值,次小值回送于引用变量second。第47页/共65页3.array_red函数的实现/Typearray_red(NODE*node)归约node所指结点的费用矩阵,返回值为归约常数Typearray_red(NODE*node)inti,j;Typetemp,temp1,sum=0;for(i=0;ik;i+)/行归约temp=row_min(node,i,temp1);/行归约常数for(j=0;jk;j+)node-cij-=temp;sum+=temp;/行归约常数累计第48页/共65页for(j=0;j

27、k;j+)/列归约temp=col_min(node,j,temp1);/列归约常数for(i=0;ik;i+)node-cij-=temp;sum+=temp;/列归约常数累计returnsum;/返回归约常数运行时间:O(n2)工作单元:(1)第49页/共65页4.edge_sel函数的实现/函数edge_sel计算dkl,选择搜索分支的边。返回dkl的值、出边顶点序号和入边顶点序号。Typeedge_sel(NODE*node,int&vk,int&vl)inti,j;Typetemp,d=0;Type*row_value=new Typenode-k;Type*col_value=ne

28、w Typenode-k;for(i=0;ik;i+)/每一行的次小值row_min(node,i,row_valuei);第50页/共65页for(i=0;ik;i+)/每列的次小值col_min(node,i,col_valuei);for(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;deleterow_value;deletecol_value;returnd;运行时间:O(n2);工作单元:

29、O(n)第51页/共65页5.函数del_rowcol的实现/函数del_rowcol删除费用矩阵当前第vk行、第vl列的所有元素voiddel_rowcol(NODE*node,intvk,intvl)inti,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;第52页/共65页for(i=vk;ik-1;i+)/元素上左移for(j=vl;jk-1;j+)node-cij=node-ci+1j+1;vk1=node-row_initvk;

30、/当前行vk转换为原始行vk1node-row_curvk1=-1;/原始行vk1置删除标志for(i=vk1+1;irow_cur-;vl1=node-col_initvl;/当前列vl转换为原始列vl1第53页/共65页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

31、;node-k-;/当前矩阵的阶数减1运行时间:O(n2);工作单元:(1)第54页/共65页6.函数edge_byp的实现/函数edge_byp把vk行、vl列所表示的边,登记到回路顶点邻接表,旁路矩阵中有关的边voidedge_byp(NODE*node,intvk,intvl)inti,j,k,l;vk=row_initvk;/当前行号转换为原始行号vl=col_initvl;/当前列号转为原始列号node-advk=vl;/登记顶点邻接表第55页/共65页for(i=0;iadj!=-1)/检查从顶点i开始的通路j=node-adj;if(i!=j)/存在一起点为i终点为j的通路l=n

32、ode-row_curj;/j转为当前行号lk=node-col_curi;/i转为当前列号kif(k0)&(l0)/当前行列号均处于当前矩阵中node-clk=MaxValueOfType;运行时间:O(n2);工作单元:(1)第56页/共65页7.Initial函数的实现NODE*initial(Typec,intn)inti,j;NODE*node=newNODE;/分配结点缓冲区for(i=0;in;i+)/拷贝费用矩阵初始数据for(j=0;jcij=cij;for(i=0;irow_initi=i;/行列号对应关系node-col_initi=i;node-row_curi=i;n

33、ode-col_curi=i;第57页/共65页for(i=0;iadi=-1;node-k=n;returnnode;运行时间:O(n2);工作单元:(1)第58页/共65页算法8.1TSP问题的分支限界算法输入:邻接矩阵c,顶点个数n输出:最短路费用w及邻接顶点表adtemplateTypeTSP(Typec,intn,intad)inti,j,vk,vl,n_heap=0;Typed,w;NODE*xnode,*ynode,*znode;HEAP*heap=newHEAPn*n;HEAPx,y,z;/x,y,z结点的堆元素xnode=initial(c,n);/初始化父结点x8.2.5

34、TSP问题分支限界算法的实现 第59页/共65页xnode-w=array_red(xnode);/归约while(xnode-k!=0)d=edge_sel(xnode,vk,vl);/选择分支方向并计算znode=newNODE;/建分支点z*znode=*xnode;/x结点数据拷到zznode-cvkvl=MaxValueOfType;array_red(znode);/归约z费用矩阵znode-w=xnode-w+d;/计算z结点的下界z.w=znode-w;/构造z的堆元素z.p=znode;insert(heap,n_heap,z);/z插 入堆中第60页/共65页ynode=n

35、ewNODE;/建分支点y*ynode=*xnode;/x数据拷到yedge_byp(ynode,vk,vl);/登记回路邻接表,旁路有关的边del_rowcol(ynode,vk,vl);/删除y结点费用矩阵当前vk行vl列ynode-w=array_red(xnode);/归约y结点费用矩阵 ynode-w+=xnode-w;/计算y结点的下界y.w=ynode-w;/构造y的堆元素y.p=ynode;第61页/共65页if(ynode-k=2)/矩阵只剩2阶if(ynode-c00=0)/登记最后两边ynode-adynode-row_init0=ynode-col_init0;ynod

36、e-adynode-row_init1=ynode-col_init1;elseynode-adynode-row_init0=ynode-col_init1;ynode-adynode-row_init1=ynode-col_init0;ynode-k=0;第62页/共65页insert(heap,n_heap,y);/y插 入堆中deletexnode;/释放没用的x缓冲区x=delete_min(heap,n_heap);xnode=x.p;w=xnode-w/保存最短路费用for(i=0;iadi;deletexnode;/释放x结点缓冲区for(i=1;i=n_heap;i+)/释放堆缓deleteheapi.p;deleteheap;returnw;第63页/共65页算法的复杂性分析:算法的时间复杂度:O(n22n)算法所需存储空间:每个结点需O(n2)存放费用矩阵,共2n个结点,算法的空间复杂度:O(n22n)第64页/共65页感谢您的观看！第65页/共65页