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

第8章 分支与限界,考： 1、分支限界的基本思想 2、分支限界的方法 3、算法流程 4、具体实例，画图 5、时间，空间复杂性,第8章 分支与限界,用回溯法求解问题时, 寻找第一个可行解是盲目搜索, 只有在找到一个可行解之后目标函数的界才有意义。这种搜索是盲目进行的。 但从某个e_结点进行搜索时, 先估算目标函数的界, 再确定是否向下搜索的方法启发人们去寻求另一种搜索模式, 这就是分支与限界法。,在分支结点即e_结点上, 估算沿着其各个子结点搜索时, 目标函数可能取得的界; 把子结点和目标函数可能取得的界保存在一张结点表中(优先队列或堆);/费用矩阵 从优先队列或堆中选取界最大(小)的e_结点向下搜索, 直到叶结点;,8.1 分支与限界法的基本思想,考简答： 基本思想（4） 分支限界是先估算目标函数的界，再确定是否继续向下搜索的方法。,4) 若叶结点的目标函数值是结点表中的最大(小)值, 则该值为问题的最优解值, 沿该叶结点到根结点的路径所确定的解是问题的最优解; 若叶结点的目标函数值不是结点表中的最大(小)值, 则继续搜索。,这样, 从根结点开始, 每遇到一个e_结点, 就对其各个子结点进行估算, 以此更新结点表: 丢弃不需要的结点, 加入新结点。再选取界为极值的结点, 重复上述过程。,随着搜索过程的不断深入, 结点表中目标函数的值越来越接近问题的解。 可见, 分支限界法不像回溯法那样盲目地向前搜索, 也不是遇到死结点才往回走, 而是根据结点表中不断更新的信息来调整自己的搜索方向, 有选择、有目标地向前搜索; 也不像回溯法那样单纯地沿着父结点一层层地向上回溯, 而是依据结点表中的信息进行回溯。,2. 目标函数界的特性 部分解:(x1,xk); 界: bound(x1,xk) 对最小值问题, 称为下界, 意思是向下搜索取得的值不会小于这些下界, 即 bound(x1) bound(x1,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。 使用分支与限界法求解具体问题时, 可采用下述两种典型方式:,从根结点向下搜索时, 分别估算n1个子结点的目标函数的值bound(x1), 把它们保存在结点表中, 并删除根结点在结点表中的登记项。 再从结点表中选取下界最小(大)的结点, 作为下一次搜索的起点。 该过程一直持续到叶结点, 得到一个可行解X=(x1,x2,xn)。 若结点表中某结点的下界大于bound(x1,x2,xn), 则删除之。,(2)从根结点向下搜索时, 预先通过某种方式处理, 从所有子结点中挑选一个作为一个分支结点, 目标函数值为bound(x1); 其余子结点的集合作为另一分支, 目标函数值为bound(x1)。 再选取界最小(大)的分支结点, 继续上述处理, 直到得到界最小(大)的叶结点为止。该结点对应的解为问题的最优解, 相应的解值为最优解值。,选择方式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)是一个有向赋权图, l是图G的一条Hamilton回路, c是图G的费用矩阵, 则回路上的边对应于费用矩阵中每行每列各一个元素。,8.2 TSP问题,例如, 5顶点TSP问题的费用矩阵如下图所示, l=v0v3v1v4v2v0是Hamilton回路, 回路上的边对应于费用矩阵中元素c03,c31,c14,c42,c20。每行每列各1元素,定义8.1 费用矩阵c的第i行中每个元素减去一个正常数lhi, 得到一个新费用矩阵, 使得新矩阵中第i行的最小元素为0, 该过程称为费用矩阵的行归约。lhi称为行归约常数。 费用矩阵c的第j列中每个元素减去一个正常数chj, 得到一个新费用矩阵, 使得新矩阵中第j列的最小元素为0, 该过程称为费用矩阵的列归约。chj称为列归约常数。,先做行归约，再做列归约,ch3=4,定义8.2 对费用矩阵c的每一行和每一列进行行归约和列归约, 得到一个新费用矩阵, 使得新费用矩阵中每一行和每一列至少有一个元素为0, 该过程称为费用矩阵的归约。所得新费用矩阵称为费用矩阵c的归约矩阵。,称为矩阵c的归约常数（行归约，列归约的和）。,归约常数h = (25+5+1+6+7)+4 = 48,定理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的一条最短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; 不沿该边出发的所有其它路径的集合, 作为另一分支结点, 称为结点Y。 下面以5顶点TSP问题的费用矩阵及其归约矩阵为例, 说明结点Y及结点Y的下界的确定方法。,若选取从v1出发, 沿边(v1,v0)前进, 则该回路的边包含费用c10。由于回路中包含c的每行每列元素各一个, 故c中第1行和第0列的所有元素在后面计算中将不起作用, 可删去。,由于回路中肯定不包含边(v0,v1), 否则会构成一个小回路, 故可把边(v0,v1)断开, 即置c01=。得如下44矩阵:,继续对降阶后的44矩阵进行归约:,归约常数为: 3+2=5 初始费用矩阵的归约常数为48 这表明从v1出发, 经边(v1,v0)的回路费用不会小于48+5 = 53,结点Y下界的确定方法: 当搜索深度为m, 并选取(vi,vj) 作为一个分支结点时, 可按下法确定其下界:,删去费用矩阵第i行及第j列所有元素, 把n-m阶费用矩阵降阶为n-m-1阶矩阵c; 把此后不可能经过的有向边的权值置为。这需要和已选择的有向边一起考虑, 有以下几种情况:,vivj不与已选边相连, 置cji为; vivj与已选边连成vivjvkvl, 置cli为; vivj与已选边连成vkvivjvl, 置clk为; vivj与已选边连成vkvlvivj, 置cjk为;,对降阶后的矩阵c进行归约, 得归约常数h。 令X表示Y的父结点, 则结点Y的下界w(Y)可由下式确定: w(Y) = w(X)+h,结点Y下界的确定方法: 不降阶 因Y是沿其它边(非vivj边)向下搜索的分支结点, 该分支对应的回路中不包含边vivj, 故可以把Y结点相应的费用矩阵中的cij置为。 该分支对应的回路中必包含第i行的某个元素及第j列的某个元素。令dij表示第i行中除cij外的最小元素与第j列中除cij外的最小元素之和, 即,结点Y的下界: w(Y) = w(X)+dij,考虑上述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元素。于是, 选择分支的基本方法:,令S是归约矩阵中cij=0的元素集合, dkl是S中使dij最大的元素, 即 dkl=maxSdij 则边(vk,vl)为所选择的分支方向。 注: dij为第i行除cij外的最小元素与第j列除cij外的最小元素之和。,考虑上述5顶点TSP问题, 其归约矩阵如右所示:,dij最大的元素为d10=17, 由此确定所选择的方向为v1v0, 建立分支结点Y和Y: w(Y)= w(X)+dkl= 48+17= 65,c01=c10=c24=c34=c42 =c43=0 d01=3+2=5, d10=13+4=17 d24=2+0=2, d34=4+0=4 d42=0+13=13, d43=0+2=2,使用分支限界法的求解过程中, 将动态生成很多结点, 用结点表存放动态生成的结点信息。 由于必须按费用的下界来确定搜索方向, 故可用优先队列或堆来维护结点表。在此使用最小堆维护结点表。,8.2.3 TSP问题的求解过程,分支限界法求解TSP的求解过程: 分配堆缓冲区, 初始化为空堆; 建立父结点X。X的费用矩阵X.c初始化为费用矩阵c, X的费用矩阵的阶X.k初始化为n; 归约X.c得归约常数h, 令结点X的下界X.w=h; 初始化回路的顶点邻接表X.ad; 由归约后的X.c中所有cij=0的元素计算dij:,(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, 把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 求解下图所示的5顶点TSP问题。,解: 用分支限界法求解5顶点TSP问题 的过程如下:,h=48 下界48,A,d10=17 h=3+2 下界53,下界 48+17 =65,B,C,(1,0),(1,0),h=3+2=5 下界53,B,(3,4),4,2,0,3,2,1,h=19 下界72,d34=19 h=2 下界55,D,E,(3,4),4,2,2,1,d03=13 h=11 下界66,F,4,2,0,3,2,1,h=13 下界68,G,(0,3),(0,3),下界 48+17 =65,C,(3,0),(3,0),h=12 下界77,I,2,1,0,4,4,3,2,1,d30=12 h=0 下界65,H,h=0 下界65,H,(1,2),4,2,0,4,3,1,h=8 下界73,d12=8 h=0 下界65,J,K,(1,2),4,2,4,3,d01=5 h=0 下界65,L,4,2,0,4,3,1,h=5 下界70,M,(0,1),(0,1),2,1,0,4,4,3,2,1,非(1,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;,NODE *xnode; /父亲结点指针 NODE *ynode; /儿子结点指针 NODE *znode; /儿子结点指针 int n_heap; /堆元素个数 typedef struct /堆结构数据 NODE *p; /指向结点元素的指针 Type w; /所指结点的下界, 堆元素的关键字 HEAP;,算法中使用的几个函数: Type row_min(NODE *node, int row, Type /计算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 row,Type ,for (i=2; ik; i+) if (node-crowicrowi; else if (node-crowicrowi; 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 (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_sel计算dkl, 选择搜索分支的边。返回dkl的值、出边顶点序号和入边顶点序号。 Type edge_sel(NODE * node, int ,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; 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,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 = 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的实现 /函数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; /i转为当前列号k if (k0) 工作单元: (1),7. Initial函数的实现 NODE *initial(Type c, int n) int i,j; NODE *node = new NODE; /分配结点缓冲区 for (i=0; icij = 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及邻接顶点表ad template Type TSP(Type c, int n, int ad) int i, j, vk, vl, n_heap=0; Type d,w; NODE *xnode, *ynode, *znode; HEAP *heap = new HEAPn*n; HEAP x,y,z; /x,y,z结点的堆元素 xnode = initial(c,n); /初始化父结点x,8.2.5 TSP问题分支限界算法的实现,xnode-w = array_red(xnode); /归约 while (xnode-k!=0) d = edge_sel(xnode,vk,vl); /选择分支方向并计算 znode = new NODE; /建分支点z *znode = *xnode; /x结点数据拷到z znode-cv