算法设计与分析概要.pptx

算法设计与分析算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五十一五”国家级规划教国家级规划教材材 陈慧南陈慧南陈慧南陈慧南 编著编著编著编著电子工业出版社电子工业出版社电子工业出版社电子工业出版社第第2部分部分 算法设计策略算法设计策略第第9章章 分枝限界法分枝限界法 学习要点学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架1.队列式队列式(FIFO)(FIFO)分支限界法分支限界法2.优先队列式优先队列式(LC)(LC)分支限界法分支限界法 通过应用实例学习分支限界法的设计策略。1.1515谜问题谜问题2.0-10-1背包问题；背包问题；3.旅行商问题旅行商问题4.批处理作业调度问题批处理作业调度问题概念回顾概念回顾活结点搜索过程中，一个自身已生成但其孩子结点尚未搜索过程中，一个自身已生成但其孩子结点尚未生成的结点叫做活结点生成的结点叫做活结点扩展结点：一个正在产生孩子的结点一个正在产生孩子的结点死结点一个所有孩子已经产生的结点一个所有孩子已经产生的结点问题状态、候选解、答案状态分支限界法一般方法分支限界法一般方法分支限界法与回溯法的区别：分支限界法分支限界法 =宽度优先搜索宽度优先搜索 +剪枝剪枝 。在分支限界法中，从根结点开始，每一个扩展结点，一次性产生其所有孩子结点。在这些孩子结点中，导致不可行解或导致非最优解的孩子结点被舍弃，其余孩子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。分支限界法一般方法分支限界法一般方法设计策略（根据活结点表的类型划分）FIFOFIFO分支限界法：活结点采用一张先进先出表分支限界法：活结点采用一张先进先出表LIFOLIFO分支限界法：活结点采用一张先进后出表分支限界法：活结点采用一张先进后出表LCLC分支限界法：活结点采用优先权队列分支限界法：活结点采用优先权队列按照优先队列中规定的优先权选取优先权最高的结点成为当前扩展结点。o最大优先队列（最大堆）：体现最大效益优先o最小优先队列（最小堆）：体现最小费用优先求求4皇后问题第一个解皇后问题第一个解FIFO分支限界法生成的状态树1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 89 9 9 910101010111111111212121213131313141414141515151516161616171717171818181822222222262626263030303031313131参考参考参考参考图图图图8-38-38-38-3图图图图8-68-68-68-6存在性问题存在性问题-分枝限界法算法框架分枝限界法算法框架树结点的数据结构/状态空间树采用树的双亲表示法，状态空间树采用树的双亲表示法，parentparent是指向其双亲的指针是指向其双亲的指针template template struct Nodestruct Node T cost;T cost;Node*parent;Node*parent;活结点表的类型记为 LiveList FIFO/LIFO/FIFO/LIFO/优选权队列优选权队列存在性问题存在性问题 分枝限界法算法框架分枝限界法算法框架template void BranchBound(Node*t)template void BranchBound(Node*t)/t/t是指向空间树的根结点是指向空间树的根结点 LiveListNode*lst(mSize);LiveListNode*lst(mSize);/lst/lst为活结点表，元素指向树结点为活结点表，元素指向树结点 Node*x,*E=t;Node*x,*E=t;/E/E为指向扩展结点的指针，初始指向为指向扩展结点的指针，初始指向t t do do /以下描述中不区分指针与其所指示的结点以下描述中不区分指针与其所指示的结点 for(for(对结点对结点E E的每个不受限的孩的每个不受限的孩子子)x=new Node;x-parent=E;x=new Node;x-parent=E;/构造构造E E的孩子结点的孩子结点x x if(x if(x是一个答案结点是一个答案结点 )输出从输出从x x到到t t的一条路径；的一条路径；return;return;/输出第一个解后算法终止输出第一个解后算法终止 lst.Append(x);lst.Append(x);/孩子结点孩子结点x x进活结点表进活结点表 if(lst.IsEmpty()if(lst.IsEmpty()cout cout “没有答案结点没有答案结点”；returnreturn；/搜索失败终止搜索失败终止 lst.Serve(E);lst.Serve(E);/从表中输出一个活结点为从表中输出一个活结点为E-E-结点结点 whilewhile（1 1）；）；LC分支限界法分支限界法在LIFO和FIFO分枝-限界法中，对下一个E-结点的选择规则死板，在某种意义上是盲目的搜索。LC分支限界法在选择活结点时根据活结点的优先权来选择下一代活结点结点优先权定义为：结点优先权定义为：“在其分支下搜索一个答案在其分支下搜索一个答案状态需要花费在代价，代价越小，越优先状态需要花费在代价，代价越小，越优先”LC分支限界法分支限界法结点代价相关概念结点代价相关概念代价函数代价函数代价函数代价函数c(.)c(.)c(.)c(.)：表示从根结点搜索到：表示从根结点搜索到X X，以及在，以及在X X之下搜之下搜索到一个答案状态所需的代价。如下定义索到一个答案状态所需的代价。如下定义1.1.若若X X是答案结点，则是答案结点，则c(X)c(X)是由空间树根到结点是由空间树根到结点X X的代价；的代价；2.2.若若X X不是答案结点且子树不是答案结点且子树X X不包含任何答案结点，则不包含任何答案结点，则c(X)=c(X)=；3.3.否则否则c(X)c(X)等于子树等于子树X X中具有最小代价的答案结点的代价。中具有最小代价的答案结点的代价。代价函数如同一个代价函数如同一个“有智力的有智力的”排序函数，基于其值排序函数，基于其值选取选取下一个下一个E-E-结点往往可以加快到达一答案结点的速度。结点往往可以加快到达一答案结点的速度。LC分支限界法分支限界法结点代价相关概念相对代价函数相对代价函数相对代价函数相对代价函数g(.)g(.)：衡量子树：衡量子树X X下搜索到一个答下搜索到一个答案状态所需的代价。案状态所需的代价。对任意结点X，可用两种标准来量度一个结点X的相对代价：1.在生成一个答案结点之前，子树X需要生成的结点数2.在子树X中离X最近的那个答案结点到X的路径长度结点代价相关概念结点代价相关概念代价函数与相对代价函数o设以下两个树A B C 均为答案结点且c(A)c(B)0,p0,pi i0,(0i0,(0in)解空间解空间解向量：解向量：(x(x0 0,x,x1 1,x,xn-1n-1)约束条件：约束条件：x xi i 0,1;w 0,1;wi ix xi i M M目标函数：目标函数：cost(X)=pcost(X)=pi ix xi i 代价函数代价函数c(X):c(X):若若X X是答案结点，是答案结点，c(X)=cost(X)c(X)=cost(X)若若X X是叶子结点，但非答案结点，是叶子结点，但非答案结点，c(X)=-c(X)=-若若X X是中间结点，则是中间结点，则 c(X)=max c(lChild(X),c(rChild(X)0/1背包问题背包问题上、下界函数UBB(X)、LBB(X)设结点设结点X X对应的部分解为对应的部分解为(x(x0 0,x,x1 1,x,xk-1k-1)设物品按单位收益由大到小设物品按单位收益由大到小编号，即编号，即p(i)/w(i)p(i+1)/w(i+1)p(i)/w(i)p(i+1)/w(i+1)到状态到状态X X时，背包剩余载重时，背包剩余载重cucu以以X X为根的子树可视为背包载为根的子树可视为背包载重为重为cucu，剩余物品组成的，剩余物品组成的0/10/1背背包问题的状态空间树。包问题的状态空间树。0/1背包问题背包问题记当背包载重为记当背包载重为cucu，剩余物品，剩余物品组成的一般背包问题的最优解为组成的一般背包问题的最优解为(z(zk k,z,zk+1k+1,z,zn-1n-1)。记当背包载重为记当背包载重为cucu，剩余物品，剩余物品组成的组成的0/10/1背包问题的最优解为背包问题的最优解为(x(xk k,x,xk+1k+1,x,xn-1n-1)记当背包载重为记当背包载重为cucu，剩余物品，剩余物品组成的组成的0/10/1背包问题的一个可行背包问题的一个可行解为解为(y(yk k,y,yk+1k+1,y,yn-1n-1)有：有：有：有：z zi ip pi i x xi ip pi i yyi ip pi i0/1背包问题背包问题定义下界函数定义下界函数 LBB(X)=LBB(X)=xxi ip pi i+y+yi ip pi i定义上界函数定义上界函数 UBB(X)=UBB(X)=xxi ip pi i+z+zi ip pi i算法实现：算法实现：算法中使用下界变量算法中使用下界变量L L，用于记录迄今为止搜索到的所有，用于记录迄今为止搜索到的所有可行解中的最小值可行解中的最小值对任一结点对任一结点X X，若，若UBB(X)LUBB(X)L，则剪去，则剪去X X子树。子树。L L的修正公式的修正公式:若X是答案结点,L=maxcost(X),L,LBB(X)-e否则 L=maxL,LBB(X)-e有：有：有：有：z zi ip pi i x xi ip pi i yyi ip pi i0/1背包问题的背包问题的LC分枝限界算法分枝限界算法树结点：struct Nodestruct Node/状态空间树结点状态空间树结点Node(Node*par,bool lft)Node(Node*par,bool lft)parent=par;left=lft;parent=par;left=lft;Node*parent;Node*parent;/指向双亲结点的指针指向双亲结点的指针bool left;bool left;/若是双亲的左孩子结点，则取真值，否则为假若是双亲的左孩子结点，则取真值，否则为假;优先权队列中的元素：pqNode0/1背包问题的背包问题的LC分枝限界算法分枝限界算法优先权队列中的元素：优先权队列中的元素：pqNodepqNodetemplate struct pqNodetemplate struct pqNode /活结点结构活结点结构operator T()const return UBB;operator T()const return UBB;/以以UBBUBB为优先权为优先权pqNode()pqNode()pqNode(float cap,T prof,T ub,int lev,Node*p)pqNode(float cap,T prof,T ub,int lev,Node*p)/构造构造cu=cap;profit=prof;cu=cap;profit=prof;UBB=ub;UBB=ub;level=lev;ptr=p;level=lev;ptr=p;float cu;float cu;/背包的剩余载重背包的剩余载重T profit,UBB;T profit,UBB;/已获收益已获收益profitprofit和上界函数值和上界函数值UBBUBB（优先权）（优先权）int level;int level;/当前结点的当前结点的levellevel，根结点为，根结点为0 0Node*ptr;Node*ptr;/指向状态空间树上相应的结点指向状态空间树上相应的结点;0/1背包问题的背包问题的LC分枝限界算法分枝限界算法背包类：背包类：template class Knapsacktemplate class Knapsackpublic:public:Knapsack(T*prof,float*wei,float mm,int len);Knapsack(T*prof,float*wei,float mm,int len);/初始化初始化 T LCBB();T LCBB();/LC/LC搜索求最优解值搜索求最优解值 void GenerateAns(int*x);void GenerateAns(int*x);/产生最优解产生最优解private:private:void LUBound(T cp,float cw,int k,T&LBB,T&UBB);void LUBound(T cp,float cw,int k,T&LBB,T&UBB);/计算计算UBBUBB和和LBBLBBT*p;T*p;/一维数组一维数组p p保存保存n n个物品收益个物品收益float*w,m;float*w,m;/一维数组一维数组w w保存保存n n个物品重量，个物品重量，m m为背为背包载重包载重int n;int n;/物品数目物品数目Node*ans,*root;Node*ans,*root;/指向状态空间树的根和最优解结点指向状态空间树的根和最优解结点;0/1背包问题的背包问题的LC分枝限界算法分枝限界算法背包类中求上下界函数背包类中求上下界函数template template void Knapsack:LUBound(T cp,float cw,int k,T&LBB,T&UBB)void Knapsack:LUBound(T cp,float cw,int k,T&LBB,T&UBB)LBB=cp;float c=cw;LBB=cp;float c=cw;/已获收益和剩余载重已获收益和剩余载重for(int i=k;in;i+)for(int i=k;in;i+)/考察剩余物品考察剩余物品 if(cwi)if(cwi)UBB=LBB+c*pi/wi;UBB=LBB+c*pi/wi;/计算计算UBBUBB：一般背包的最优解值：一般背包的最优解值 for(int j=i+1;jn;j+)for(int j=i+1;j=wj)if(c=wj)c=c-wj;LBB=LBB+pj;c=c-wj;LBB=LBB+pj;return;return;c=c-wi;LBB=LBB+pi;c=c-wi;LBB=LBB+pi;UBB=LBB;UBB=LBB;/剩余物品全部装入时，有剩余物品全部装入时，有LBB=UBBLBB=UBB 注意物品编号方式注意物品编号方式注意物品编号方式注意物品编号方式0/1背包问题的背包问题的LC分枝限界算法分枝限界算法背包类中的背包类中的LCBBLCBB方法方法template template T Knapsack:LCBB()T Knapsack:LCBB()Node*child,*E;Node*child,*E;T LBB,UBB,L;T LBB,UBB,L;ans=NULL;ans=NULL;PrioQueuepqNode pq(mSize);PrioQueuepqNode pq(mSize);/生成一个优先权队列实例生成一个优先权队列实例root=new Node(NULL,false);root=new Node(NULL,false);/构造状态空间树的根结点构造状态空间树的根结点E=root;E=root;LUBound(0,m,0,LBB,UBB);LUBound(0,m,0,LBB,UBB);/计算根结点的计算根结点的LBBLBB和和UBBUBBpqNode e(m,0,UBB,0,root);pqNode e(m,0,UBB,0,root);/根结点成为根结点成为E E结点结点L=LBB-epsilon;L=LBB-epsilon;/下界变量下界变量L L的初值为的初值为LBB-epsilonLBB-epsilondo do int k=e.level;float cap=e.cu;T prof=e.profit;E=e.ptr;int k=e.level;float cap=e.cu;T prof=e.profit;E=e.ptr;if(k=n)&(profL)if(k=n)&(profL)/记录答案结点，修正记录答案结点，修正L LL=prof;ans=E;L=prof;ans=E;else else/生成左孩子结点生成左孩子结点 （x xk k=1=1）if(cap=wk)if(cap=wk)child=new Node(E,true);child=new Node(E,true);e.ptr=child;e.level=k+1;e.ptr=child;e.level=k+1;e.cu=cap-wk;e.profit=prof+pk;e.cu=cap-wk;e.profit=prof+pk;pq.Append(e);pq.Append(e);/e.UBB/e.UBB不变不变 LBBLBB也不变也不变 /生成右孩子结点（生成右孩子结点（x xk k=0=0）LUBound(prof,cap,k+1,LBB,UBB);LUBound(prof,cap,k+1,LBB,UBB);if(UBBL)if(UBBL)child=new Node(E,false);child=new Node(E,false);e.ptr=child;e.level=k+1;e.ptr=child;e.level=k+1;e.cu=cap;e.profit=prof;e.UBB=UBB;e.cu=cap;e.profit=prof;e.UBB=UBB;pq.Append(e);pq.Append(e);/修改修改L L if(L LBB-epsilon)L=LBB-epsilon;if(L L);while(e.UBBL);return L;return L;基于剪枝的基于剪枝的LC分枝限界算法框架分枝限界算法框架程序程序9-39-3（最小值）：（最小值）：Part 1Part 1templatetemplateNode*LCBB(Node*t,T&U)Node*LCBB(Node*t,T&U)/t/t为根，为根，U U为上界变量为上界变量 LiveListNode*lst(mSize);LiveListNode*lst(mSize);/lst/lst为优先权队列为优先权队列 Node*ans=NULL,*x,E=*t;Node*ans=NULL,*x,E=*t;do do for(for(对结点对结点E E的每个孩子的每个孩子)/所有满足约束条件的孩子所有满足约束条件的孩子 x=new Node;x-parent=E;x=new Node;x-parent=E;/构造构造E E的孩子结点的孩子结点x x if(c(x)U)if(c(x)U)/若若x x子树未被限界函数剪枝子树未被限界函数剪枝程序程序9-39-3：Part 2Part 2 lst.Append(x);lst.Append(x);/以下修正以下修正U U if(x if(x是答案结点是答案结点&cost(x)U)&cost(x)U)if(u(x)+cost(x)U=u(x)+;else U=coxt(x);ans=x;U=coxt(x);ans=x;else if(u(x)+else if(u(x)+U)U=u(x)+U)U=u(x)+;if(!lst.IsEmpty()if(!lst.IsEmpty()lst.Serve(E);lst.Serve(E);/从队列中取扩展结点从队列中取扩展结点E E if(c(E)U)return ans;if(c(E)U)return ans;/若若c(E)Uc(E)U，则算法结束，则算法结束 else return ans;else return ans;/若队列为空，则算法结束若队列为空，则算法结束 whilewhile（1 1）；）；TSP(Traveling Saleman Problem)问题问题货郎担问题、旅行商问题、邮路问题问题描述：问题描述：有一个推销员，要到有一个推销员，要到n n个城市推销商品，他从个城市推销商品，他从A A城市出发，经过其他城市出发，经过其他n-n-1 1个城市，最后回到出发地个城市，最后回到出发地A A城市，找出一条包含城市，找出一条包含n n个城市的路程最短的个城市的路程最短的哈密顿回路。哈密顿回路。示例：示例：TSP问题问题 数学描述数学描述有向图有向图G=(VG=(V，E)E)：|V|=n代价矩阵 Cnn顶点编号0,1,n-1，其中起点编号为0解空间：解空间：(x(x0 0,x,x1 1,x,xn-1n-1)表示一条哈密顿回路表示一条哈密顿回路xi 0,1,n-1x0=xn,xi xi+1,(xi,xi+1)E；(xn-1,x0)E目标函数：路径长度；目标函数：路径长度；问题是求使目标函数取最小值的解问题是求使目标函数取最小值的解LC分枝限界法求解分枝限界法求解TSP问题问题解空间的树形结构解空间的树形结构排列树排列树TSPTSP问题中代价函数问题中代价函数c(X)c(X)的意义的意义经过经过X X的最短周游路径的长度的最短周游路径的长度寻找合适的上下界函数寻找合适的上下界函数u(X)u(X)和和c(X)c(X)c(X)c(X)u(X)c(X)c(X)u(X)0 0 0 0X X X X0 0 0 0=0=0=0=0回溯法回溯法?LC分枝限界法求解分枝限界法求解TSP问题问题下界函数下界函数c(X)c(X)归约矩阵归约矩阵例如矩阵约数矩阵约数L L L=11记图记图G G的代价矩阵的代价矩阵A A的归约的归约矩阵为矩阵为B B。记与图记与图G G结构相同，但以结构相同，但以B B为代价矩阵的图为为代价矩阵的图为G G r r r r1 1 1 1=1=1=1=1r r r r2 2 2 2=3=3=3=3r r r r3 3 3 3=5=5=5=5c c c c3 3 3 3=2=2=2=2图图图图G G G G 与与与与G G G G具有相同的哈密顿回路，具有相同的哈密顿回路，具有相同的哈密顿回路，具有相同的哈密顿回路，但同样的回路，但同样的回路，但同样的回路，但同样的回路，前者的长度比后者总是前者的长度比后者总是前者的长度比后者总是前者的长度比后者总是 少少少少 L L L LLC分枝限界法求解分枝限界法求解TSP问题问题图图G G图图G G 0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 40 0 0 017171717151515150 0 0 012121212101010101 1 1 111111111111111112 2 2 20 0 0 03 3 3 33 3 3 30 0 0 00 0 0 02 2 2 2121212120 0 0 00 0 0 012121212记记R R为根结点，有为根结点，有c(R)L,c(R)L,即即c(R)=Lc(R)=LL=250 0 0 01 1 1 12 2 2 23 3 3 34 4 4 40 0 0 017171717151515150 0 0 012121212101010101 1 1 111111111111111112 2 2 20 0 0 03 3 3 33 3 3 30 0 0 00 0 0 02 2 2 2121212120 0 0 00 0 0 0121212120 0 0 01 1 1 12 2 2 23 3 3 34 4 4 40 0 0 017171717151515150 0 0 012121212101010101 1 1 111111111111111112 2 2 20 0 0 03 3 3 33 3 3 30 0 0 00 0 0 02 2 2 2121212120 0 0 00 0 0 012121212LC分枝限界法求解分枝限界法求解TSP问题问题设状态空间树根结点为R（x0=0）x x1 1=1,2,3,4=1,2,3,4若若x x1 1=1=1，即选定边，即选定边,记状态结点为记状态结点为X X c(X)表示经过的最短周游路径长R R R RX X X Xx x x x1 1 1 1=1=1=1=14 4 4 43 3 3 32 2 2 2R R R R的归约的归约的归约的归约矩阵矩阵矩阵矩阵A A A Ac(X)=c(R)+A01+Lc(X)=c(R)+A01+Lc(X)=c(R)+A01+Lc(X)=c(R)+A01+Lx x x x新矩阵新矩阵新矩阵新矩阵A A A A L L L Lx x x x=0=0=0=0X X X X的归约的归约的归约的归约矩阵矩阵矩阵矩阵B B B BLC分枝限界法求解分枝限界法求解TSP问题问题一般地对任一中间结点X，不妨设其父结点为其父结点为P PP P的归约矩阵为的归约矩阵为A AP P到到X X 表示图表示图G G中边中边被选入被选入将A中第i行，第j列元素以及Aj,0变换为，得到的新矩阵记为A。对A归约得到矩阵B，B即为X的归约矩阵，设这一步的矩阵约数为r,则有：c(X)=c(P)+Aij+rP P P PX X X Xr r r r表示图表示图表示图表示图G G G GB B B B上由上由上由上由j j j j出发经过其他顶点到达出发经过其他顶点到达出发经过其他顶点到达出发经过其他顶点到达0 0 0 0的最短路径长度的下界的最短路径长度的下界的最短路径长度的下界的最短路径长度的下界LC分枝限界法求解分枝限界法求解TSP问题问题c(X)的计算方法：若若X X是根结点是根结点R R，则，则c(R)=L,Lc(R)=L,L为为G G的代价矩阵的矩的代价矩阵的矩阵约数阵约数若若X X是中间结点，则是中间结点，则c(X)=c(P)+Aij+rc(X)=c(P)+Aij+r。P是X的父结点，A是P的归约矩阵A经过变换得到Ar是A归约到B的矩阵约数。若若X X是叶子结点，则是叶子结点，则c(X)=c(X)c(X)=c(X)，是从根到，是从根到X X所确所确定的周游路径长。定的周游路径长。LC分枝限界法求解分枝限界法求解TSP问题问题剪枝处理：剪枝处理：用上界变量用上界变量U U 和和 下界值下界值初始状态，初始状态，U=U=遇到答案结点时，计算相应的周游路径长度遇到答案结点时，计算相应的周游路径长度m,m,修正修正U U的的值：值：U=minm,UU=minm,U生成的活结点生成的活结点X X的下界必须满足：的下界必须满足：c(X)=U c(X)=U，否则丢弃。，否则丢弃。搜索结束条件：搜索结束条件：扩展结点扩展结点E E的不满足：的不满足：c(E)=U c(E)=U 或队列或队列为空为空优选权定义：使用下界函数值优选权定义：使用下界函数值结点的下界函数值越小越优先。结点的下界函数值越小越优先。LC分枝限界法求解分枝限界法求解TSP问题问题0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 43 3 3 330303030191919191010101015151515202020201111111116161616161616164 4 4 42 2 2 25 5 5 56 6 6 64 4 4 42 2 2 24 4 4 4181818183 3 3 37 7 7 7161616161 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 51 1 1 1 4 4 4 4 5 5 5 5 2 2 2 2 3 3 3 3FIFOFIFOFIFOFIFOLCLCLCLC9.6 批处理作业调度问题批处理作业调度问题问题描述0,1,0,1,n-1,n-1；P1P1，P2P2；a ai i,b,bi i F Fi i(S)(S)：作业：作业i i在调度在调度S S下的最后完成时间下的最后完成时间求使求使FT(S)=FFT(S)=Fi i(S)(S)最小的调度方案最小的调度方案解空间(n个作业所有可能排列)：xx0 0,x,x1 1,x,xn-1n-1,x,xk k0,1,0,1,n-1,n-1x xi i x xj j,ij,ij是一颗排列树是一颗排列树目标函数 FT(S)=Fi(S)9.6 批处理作业调度问题批处理作业调度问题剪枝处理剪枝处理已经找到的最优解的上界值记为已经找到的最优解的上界值记为U Uo等于到目前为止已经找到的所有可行解中目标函数值最小者搜索过程中已调度作业所需完成时间不能超过U，否则丢弃搜索过程中活结点的下界函数值不能超过U，否则丢弃U的初始值为搜索结束：队列空或扩展结点下界函数值超过搜索结束：队列空或扩展结点下界函数值超过U U以下界函数值为优先权以下界函数值为优先权下界函数下界函数c(X)c(X)：反映，经过状态：反映，经过状态X X所能达到的答案结点的所能达到的答案结点的最好情况，值越小，越优先最好情况，值越小，越优先9.6 批处理作业调度问题批处理作业调度问题下界函数下界函数c(X)c(X)设设X X是状态空间树上的一个结点是状态空间树上的一个结点它确定了一个调度子集J=x0,x1,xk。X之下，每个叶子结点代表的调度S满足：o FT(S)o第一部分表示到X时已经调度的作业所需完成时间和o第二部分表示剩余作业在调度方案S下所需的完成时间和oc(X)表示X下最好的调度方案所需完成时间和c(x)=minS FT(S)f f1k1k、f f2k2k分别分别分别分别表示作业表示作业表示作业表示作业k k在在在在设备设备设备设备1 1和和和和2 2上上上上的完成时间的完成时间的完成时间的完成时间9.6 批处理作业调度问题批处理作业调度问题在在X X时对剩余作业，考虑两种特殊调度时对剩余作业，考虑两种特殊调度oS1：设备1没有空闲，设备2处理作业瞬间完成。f1i=f1k+ak+1+ak+2+.+ai，f2i=f1i+bi，i=k+1,n-1当当ajaj+1时，时，T1取最小值取最小值T1oS1：设备2没有空闲，设备1处理作业瞬间完成。f2(k+1)=max(f2k,f1k+minai)+b1(k+1)，f2i=f2(k+1)+bk+2+bi i=k+2,n-1当当bjbj+1时，时，T2取最小值取最小值T2对对X X下任一调度方案下任一调度方案S S总有总有 FT(S)iJ fi(S)+maxT1,T2=c(X)f f1k1k、f f2k2k分别分别分别分别表示作业表示作业表示作业表示作业k k在在在在设备设备设备设备1 1和和和和2 2上上上上的完成时间的完成时间的完成时间的完成时间分枝限界算法分枝限界算法 小结小结 1.1.基本要素基本要素解空间的树形表示。例如，解空间的树形表示。例如，0/10/1背包问题：子集树；背包问题：子集树；n n皇后问题：满皇后问题：满n n叉树；旅行商问题：排列树；等等。叉树；旅行商问题：排列树；等等。剪枝操作。根据约束条件、目标函数的界来设计剪枝操作。剪枝操作。根据约束条件、目标函数的界来设计剪枝操作。优先队列。设计待检测结点的优先级。优先队列。设计待检测结点的优先级。2 2分枝限界法的基本思想分枝限界法的基本思想 树的优先队列优先搜索树的优先队列优先搜索 +剪枝剪枝 3 3分枝限界算法形式及终止条件分枝限界算法形式及终止条件算法形式：一般是迭代形式。算法形式：一般是迭代形式。算法终止的条件：求存在性问题时，找到问题的一个解即可结束；在算法终止的条件：求存在性问题时，找到问题的一个解即可结束；在求优化问题时，一般要求优先队列为空时才结束，但是在满足一定条求优化问题时，一般要求优先队列为空时才结束，但是在满足一定条件时可在找到一个解即可结束（该解即为最优解）。件时可在找到一个解即可结束（该解即为最优解）。分枝限界算法分枝限界算法 小结小结4分枝限界法的特性时间性能：最坏的情况要搜索整个解空间，是复时间性能：最坏的情况要搜索整个解空间，是复杂度是指数型。但如果启发式信息强且剪枝处理得杂度是指数型。但如果启发式信息强且剪枝处理得当，平均性能往往很好。当，平均性能往往很好。空间性能：优先队列往往需要较大的空间开销。空间性能：优先队列往往需要较大的空间开销。