《算法设计与分析》第9章概要

算法设计与分析DeSignandAnalysisofAlgorithmsInC++“十一五”国家级规划教材陈慧南编著电子工业出版社第2局部算法设计策略第9章分枝限界法学习要点理解分支限界法的剪枝搜寻策略。把握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式(LC)分支限界法通过应用实例学习分支限界法的设计策略。15谜问题0-1背包问题；旅行商问题批处理作业调度问题概念回忆活结点搜寻过程中，一个自身已生成但其孩子结点尚未生成的结点叫做活结点扩展结点：一个正在产生孩子的结点死结点一个全部孩子已经产生的结点问题状态、候选解、答案状态分支限界法一般方法分支限界法与回溯法的区分：分支限界法=宽度优先搜寻+剪枝。在分支限界法中，从根结点开头，每一个扩展结点，一次性产生其全部孩子结点。在这些孩子结点中，导致不行行解或导致非最优解的孩子结点被舍弃，其余孩子结点被参加活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程始终持续到找到所需的解或活结点表为空时为止。分支限界法一般方法设计策略〔依据活结点表的类型划分〕FIFO分支限界法：活结点承受一张先进先出表LIFO分支限界法：活结点承受一张先进后出表LC分支限界法：活结点承受优先权队列依据优先队列中规定的优先权选取优先权最高的结点成为当前扩展结点。最大优先队列〔最大堆〕：表达最大效益优先最小优先队列〔最小堆〕：表达最小费用优先求4皇后问题第一个解FIFO分支限界法生成的状态树12345678910111213141516171822263031参考图8-3图8-6存在性问题-分枝限界法算法框架树结点的数据构造//状态空间树承受树的双亲表示法，parent是指向其双亲的指针template<classT>structNode{Tcost;Node*parent; };活结点表的类型记为LiveListFIFO/LIFO/优选权队列存在性问题分枝限界法算法框架template<classT>voidBranchBound(Node<T>*t)//t是指向空间树的根结点{LiveList<Node<T>*>lst(mSize);//lst为活结点表，元素指向树结点Node<T>*x,*E=t; //E为指向扩展结点的指针，初始指向tdo{//以下描述中不区分指针与其所指示的结点for(对结点E的每个不受限的孩子){x=newNode;x->parent=E; //构造E的孩子结点xif(x是一个答案结点){ 输出从x到t的一条路径； return; //输出第一个解后算法终止}lst.Append(x); //孩子结点x进活结点表}if(lst.IsEmpty){ cout<<“没有答案结点”； return； //搜寻失败终止}lst.Serve(E); //从表中输出一个活结点为E-结点}while〔1〕；}LC分支限界法在LIFO和FIFO分枝-限界法中，对下一个E-结点的选择规章死板，在某种意义上是盲目的搜寻。LC分支限界法在选择活结点时依据活结点的优先权来选择下一代活结点结点优先权定义为：“在其分支下搜寻一个答案状态需要花费在代价，代价越小，越优先”LC分支限界法结点代价相关概念代价函数c(.)：表示从根结点搜寻到X，以及在X之下搜寻到一个答案状态所需的代价。如下定义假设X是答案结点，则c(X)是由空间树根到结点X的代价；假设X不是答案结点且子树X不包含任何答案结点，则c(X)=∞；否则c(X)等于子树X中具有最小代价的答案结点的代价。代价函数犹如一个“有智力的”排序函数，基于其值选取下一个E-结点往往可以加快到达一答案结点的速度。LC分支限界法结点代价相关概念相对代价函数g(.)：衡量子树X下搜寻到一个答案状态所需的代价。对任意结点X，可用两种标准来量度一个结点X的相对代价：在生成一个答案结点之前，子树X需要生成的结点数在子树X中离X最近的那个答案结点到X的路径长度结点代价相关概念代价函数与相对代价函数设以下两个树ABC均为答案结点且c(A)<c(B)<c(C)c(T)?c(U)?c(X)?c(Z)?g(X)?g(Y)?g(Z)?由定义知，直接求c(.)和g(.)是特别困难LC分支限界法结点代价相关概念相对代价的估量函数^g(.)：用于估量在X下搜寻到一个答案状态所需的代价。^g(.)需要视具体问题而定！一般地，假设Y是X的孩子则有 ^g(Y)≤^g(x)LC分支限界法结点代价相关概念结点代价的估量函数^c(.)：^c(X)=f(X)+^g(X)一般地，f(X)=X在树中的层次一般地，^g(X)依据问题确定LC检索(即最小本钱检索)：总是选取^c(.)值最小的活结点为下一个E结点。假设令f(X)≡0时，LC检索退化为DFS搜寻假设令^g(X)≡0时，LC检索退化为BFS搜寻15谜问题15谜问题在一个分成16格的方形棋盘上，放有15块编了号码(1,2,…,15)的牌〔见以下图〕。对这些牌给定一种初始排列如图(a)，要求通过一系列的合法移动将这一初始排列转换成图(b)所示的那样的目标排列。合法移动：空格四周的牌子可以移入空格位置初始排列为初始状态；目标排列称为目标状态假设由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达。目标状态图b为可到达状态的条件是初始状态必需满足定理9-1。13415251276111489101312345678910111213141512345678910111213141516abcLC分支限界法用于求15谜问题15谜问题的解空间树：初始状态为根结点。其余结点由全部可从初始状态到达的状态构成。在这棵树中，每一个结点X的孩子表示由状态X通过一次合法的移动可到达的状态。不难看出，移动牌与移动空格实质上是等效的，而且在作实际移动时，因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。解空间例如LC分支限界法用于求15谜问题123456891071113141512解空间例如，与祖先重复的结点已剪LC分支限界法用于求15谜问题分析结点X的代价代价函数：该例中c(X)衡量由根结点搜寻到X下一个答案结点的代价，可以用路径长度来表示。代价估量函数^c(X):^c(X)=f(X)+^g(X)f(X)=根到X的路径长^g(X)表示以X为根的子树中由X到目标状态的一条最短路径长度的估量值。这里选择：^g(X)=X时不在其目标位置的非空白牌数目LC分支限界法用于求15谜问题123456891071113141512求最优解的分枝限界法一般思想：除了约束函数之外，要求为状态空间树的每个结点定义上界或下界函数，并记录迄今为止求得的最优解，以有效削减搜寻到最优答案结点的时间。主要使用LC分枝限界法重新界定结点代价的含义：选择与目标函数有关的度量值假设X是答案结点，则c(X)即是这个解的目标函数值；假设X是叶子结点且非解，则c(X)=∞或-∞；假设X是是中间结点，则c(X)等于子树X中结点的最优目标值不直接求c(X)求最优解的分枝限界法限界函数：上界函数u(.)和下界函数^c(.)对任一结点X，总有^c(X)≤c(X)≤u(X)限界函数的意义对最优解状态的目标函数值的范围进展界定，实现剪枝。例：求使目标函数取最小值的最优解。设置上界变量U，初始值可以置为∞或用某种启发式方法得到。每当找到一个新的答案结点就修正U的值，使U记录迄今为止已经得到的最小解。假设^c(X)≥U,则X子树可以剪枝。下界函数值越小的越优先假设求使目标函数取最大值的最优解，则使用下界变量L。0/1背包问题M,n,wi>0,pi>0,(0≤i<n)解空间解向量：(x0,x1,…,xn-1)约束条件：xi∈{0,1};∑wixi≤M目标函数：cost(X)=∑pixi代价函数c(X):假设X是答案结点，c(X)=cost(X)假设X是叶子结点，但非答案结点，c(X)=-∞假设X是中间结点，则c(X)=max{c(lChild(X)),c(rChild(X))}0/1背包问题上、下界函数UBB(X)、LBB(X)设结点X对应的局部解为(x0,x1,…,xk-1)设物品按单位收益由大到我号，即p(i)/w(i)≥p(i+1)/w(i+1)到状态X时，背包剩余载重cu以X为根的子树可视为背包载重为cu，剩余物品组成的0/1背包问题的状态空间树。0/1背包问题记当背包载重为cu，剩余物品组成的一般背包问题的最优解为(zk,zk+1,…,zn-1)。记当背包载重为cu，剩余物品组成的0/1背包问题的最优解为(xk,xk+1,…,xn-1)记当背包载重为cu，剩余物品组成的0/1背包问题的一个可行解为(yk,yk+1,…,yn-1)有：∑zipi≥∑xipi≥

∑yipi0/1背包问题定义下界函数LBB(X)=∑xipi+∑yipi定义上界函数UBB(X)=∑xipi+∑zipi算法实现：算法中使用下界变量L，用于记录迄今为止搜寻到的全部可行解中的最小值对任一结点X，假设UBB(X)<L，则剪去X子树。L的修正公式:假设X是答案结点,L=max{cost(X),L,LBB(X)-e}否则L=max{L,LBB(X)-e}有：∑zipi≥∑xipi≥

∑yipi0/1背包问题的LC分枝限界算法树结点：structNode{//状态空间树结点 Node(Node*par,boollft) { parent=par;left=lft; } Node*parent; //指向双亲结点的指针 boolleft; //假设是双亲的左孩子结点，则取真值，否则为假};优先权队列中的元素：pqNode0/1背包问题的LC分枝限界算法优先权队列中的元素：pqNodetemplate<classT>structpqNode{ //活结点构造 operatorTconst{returnUBB;}//以UBB为优先权 pqNode{} pqNode(floatcap,Tprof,Tub,intlev,Node*p) {//构造 cu=cap;profit=prof; UBB=ub; level=lev;ptr=p; } floatcu; //背包的剩余载重 Tprofit,UBB; //已获收益profit和上界函数值UBB〔优先权〕 intlevel; //当前结点的level，根结点为0 Node*ptr; //指向状态空间树上相应的结点};0/1背包问题的LC分枝限界算法背包类：template<classT>classKnapsack{public:Knapsack(T*prof,float*wei,floatmm,intlen);//初始化TLCBB; //LC搜寻求最优解值voidGenerateAns(int*x); //产生最优解private: voidLUBound(Tcp,floatcw,intk,T&LBB,T&UBB);//计算UBB和LBB T*p; //一维数组p保存n个物品收益 float*w,m; //一维数组w保存n个物品重量，m为背包载重 intn; //物品数目 Node*ans,*root; //指向状态空间树的根和最优解结点};0/1背包问题的LC分枝限界算法背包类中求上下界函数template<classT>voidKnapsack<T>::LUBound(Tcp,floatcw,intk,T&LBB,T&UBB){ LBB=cp;floatc=cw; //已获收益和剩余载重 for(inti=k;i<n;i++){ //考察剩余物品 if(c<w[i]){ UBB=LBB+c*p[i]/w[i];//计算UBB：一般背包的最优解值 for(intj=i+1;j<n;j++) //计算LBB：任意一个可行解值 if(c>=w[j]){ c=c-w[j];LBB=LBB+p[j]; } return; } c=c-w[i];LBB=LBB+p[i]; } UBB=LBB; //剩余物品全部装入时，有LBB=UBB}留意物品编号方式0/1背包问题的LC分枝限界算法背包类中的LCBB方法template<classT>TKnapsack<T>::LCBB{ Node*child,*E; TLBB,UBB,L; ans=NULL; PrioQueue<pqNode<T>>pq(mSize);//生成一个优先权队列实例 root=newNode(NULL,false); //构造状态空间树的根结点 E=root; LUBound(0,m,0,LBB,UBB); //计算根结点的LBB和UBB pqNode<T>e(m,0,UBB,0,root); //根结点成为E结点 L=LBB-epsilon; //下界变量L的初值为LBB-epsilon do{ intk=e.level;floatcap=e.cu;Tprof=fit;E=e.ptr; if((k==n)&&(prof>L)){//记录答案结点，修正L L=prof;ans=E; } else{ //生成左孩子结点〔xk=1〕 if(cap>=w[k]){ child=newNode(E,true); e.ptr=child;e.level=k+1; e.cu=cap-w[k];fit=prof+p[k]; pq.Append(e);//e.UBB不变LBB也不变 } //生成右孩子结点〔xk=0〕 LUBound(prof,cap,k+1,LBB,UBB); if(UBB>L){ child=newNode(E,false); e.ptr=child;e.level=k+1; e.cu=cap;fit=prof;e.UBB=UBB; pq.Append(e); //修改L if(L<LBB-epsilon)L=LBB-epsilon; } } if(pq.IsEmpty)returnZero; //Zero为零收益常量 pq.Serve(e); //取下一个扩展结点 }while(e.UBB>L); returnL;}基于剪枝的LC分枝限界算法框架程序9-3〔最小值〕：Part1template<classT>Node<T>*LCBB(Node<T>*t,T&U)//t为根，U为上界变量{LiveList<Node<T>*>lst(mSize);//lst为优先权队列Node<T>*ans=NULL,*x,E=*t;do{for(对结点E的每个孩子){//全部满足约束条件的孩子x=newNode;x->parent=E; //构造E的孩子结点xif(^c(x)<U){ //假设x子树未被限界函数剪枝程序9-3：Part2 lst.Append(x); //以下修正Uif(x是答案结点&&cost(x)<U)if(u(x)+<cost(x))U=u(x)+;else{U=coxt(x);ans=x;}elseif(u(x)+<U)U=u(x)+; }}if(!lst.IsEmpty){lst.Serve(E); //从队列中取扩展结点Eif(^c(E)≥U)returnans; //假设^c(E)≥U，则算法完毕}elsereturnans; //假设队列为空，则算法完毕 }while〔1〕；}TSP(TravelingSalemanProblem)问题货郎担问题、旅行商问题、邮路问题问题描述：有一个推销员，要到n个城市推销商品，他从A城市动身，经过其他n-1个城市，最终回到动身地A城市，找出一条包含n个城市的路程最短的哈密顿回路。例如：TSP问题数学描述有向图G=(V，E)：|V|=n代价矩阵C[n][n]顶点编号0,1,…,n-1，其中起点编号为0解空间：(x0,x1,…,xn-1)表示一条哈密顿回路xi

∈{0,1,…,n-1}x0=xn,xi

≠xi+1,(xi,xi+1)∈E；(xn-1,x0)∈E目标函数：路径长度；问题是求使目标函数取最小值的解LC分枝限界法求解TSP问题解空间的树形构造排列树TSP问题中代价函数c(X)的意义经过X的最短周游路径的长度查找适宜的上下界函数u(X)和^c(X)^c(X)≤c(X)≤u(X)0X0=0回溯法?LC分枝限界法求解TSP问题下界函数^c(X)归约矩阵例如矩阵约数LL=11记图G的代价矩阵A的归约矩阵为B。记与图G构造一样，但以B为代价矩阵的图为G’r1=1r2=3r3=5c3=2图G’与G具有一样的哈密顿回路，但同样的回路，前者的长度比后者总是少LLC分枝限界法求解TSP问题图G图G’012340171501210111112033002120012记R为根结点，有c(R)≥L,即^c(R)=LL=25012340171501210111112033002120012012340171501210111112033002120012LC分枝限界法求解TSP问题设状态空间树根结点为R〔x0=0〕x1=1,2,3,4假设x1=1，即选定边<0,1>,记状态结点为Xc(X)—表示经过<0,1>的最短周游路径长RXx1=1…432R的归约矩阵A^c(X)=^c(R)+A[0][1]+Lx新矩阵A’Lx=0X的归约矩阵BLC分枝限界法求解TSP问题一般地对任一中间结点X，不妨设其父结点为PP的归约矩阵为AP到X表示图G中边<i,j>被选入将A中第i行，第j列元素以及A[j,0]变换为∞，得到的新矩阵记为A’。对A’归约得到矩阵B，B即为X的归约矩阵，设这一步的矩阵约数为r,则有：c^(X)=c^(P)+A[i][j]+rPX…r表示图GB上由j动身经过其他顶点到达0的最短路径长度的下界LC分枝限界法求解TSP问题^c(X)的计算方法：假设X是根结点R，则^c(R)=L,L为G的代价矩阵的矩阵约数假设X是中间结点，则^c(X)=^c(P)+A[i][j]+r。P是X的父结点，A是P的归约矩阵A经过变换得到A’r是A’归约到B的矩阵约数。假设X是叶子结点，则^c(X)=c(X)，是从根到X所确定的周游路径长。LC分枝限界法求解TSP问题剪枝处理：用上界变量U和下界值初始状态，U=∞遇到答案结点时，计算相应的周游路径长度m,修正U的值：U=min{m,U}生成的活结点X的下界必需满足：^c(X)<=U，否则丢弃。搜寻完毕条件：扩展结点E的不满足：^c(E)<=U或队列为空优选权定义：使用下界函数值结点的下界函数值越小越优先。LC分枝限界法求解TSP问题012343301910152011161642564241837161234514523……FIFOLC9.6批处理作业调度问题问题描述{0,1,…,n-1}；P1，P2；ai,biFi(S)：作业i在调度S下的最终完成时间求使FT(S)=∑Fi(S)最小的调度方案解空间(n个作业全部可能排列)：{x0,x1,…,xn-1},xk∈{0,1,…,n-1}xi≠xj,i≠j是一颗排列树目标函数FT(S)=∑Fi(S)9.6批处理作业调度问题剪枝处理已经找到的最优解的上界值记为U等于到目前为止已经找到的全部可行解中目