《算法设计与分析》第09章概要优秀PPT.ppt

《《算法设计与分析》第09章概要优秀PPT.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第09章概要优秀PPT.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五十一五”国家级规划教国家级规划教材材 陈慧南陈慧南陈慧南陈慧南 编著编著编著编著电子工业出版社电子工业出版社电子工业出版社电子工业出版社第第2部分部分 算法设计策略算法设计策略第第9章章 分枝限界法分枝限界法 学习要点学习要点理解分支限界法的剪枝搜寻策略。驾驭分支限界法的算法框架队列式(FIFO)分支限界法优先队列式(LC)分支限界法 通过应用实例学习分支限界法的设计策略。15谜问题0-1背包问题；旅行商问题批处理作业调度问题概念回顾概念回顾活结点搜寻过程中，一个自身已生成但其孩子结

2、点尚未生成的结点叫做活结点扩展结点：一个正在产生孩子的结点死结点一个全部孩子已经产生的结点问题状态、候选解、答案状态分支限界法一般方法分支限界法一般方法分支限界法与回溯法的区分：分支限界法=宽度优先搜寻+剪枝。在分支限界法中，从根结点起先，每一个扩展结点，一次性产生其全部孩子结点。在这些孩子结点中，导致不行行解或导致非最优解的孩子结点被舍弃，其余孩子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程始终持续到找到所需的解或活结点表为空时为止。分支限界法一般方法分支限界法一般方法设计策略（依据活结点表的类型划分）FIFO分支限界法：活结点接受一张

3、先进先出表LIFO分支限界法：活结点接受一张先进后出表LC分支限界法：活结点接受优先权队列依据优先队列中规定的优先权选取优先权最高的结点成为当前扩展结点。最大优先队列（最大堆）：体现最大效益优先最小优先队列（最小堆）：体现最小费用优先求求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 910101010111111111212121213131313141414141515151516161616171717171818181822222222262626

4、263030303031313131参考参考参考参考图图图图8-38-38-38-3图图图图8-68-68-68-6存在性问题存在性问题-分枝限界法算法框架分枝限界法算法框架树结点的数据结构/状态空间树接受树的双亲表示法，parent是指向其双亲的指针template struct Node T cost;Node*parent;活结点表的类型记为 LiveList FIFO/LIFO/优选权队列存在性问题存在性问题 分枝限界法算法框架分枝限界法算法框架template void BranchBound(Node*t)/ttemplate void BranchBound(Node*t)/t是

5、指向空间树的根结点是指向空间树的根结点 LiveListNode*lst(mSize);/lst LiveListNode*lst(mSize);/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

6、的孩子结点的孩子结点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 “没有答案结点没有答案结点”；return return；/搜寻失败终止搜寻失败终止 lst.Serve(E);lst.Serve(E);/从表中输出一个活结点为从表中输出一个活结点为E-E-结点结点 whi

7、le while（1 1）；）；LC分支限界法分支限界法在LIFO和FIFO分枝-限界法中，对下一个E-结点的选择规则死板，在某种意义上是盲目的搜寻。LC分支限界法在选择活结点时依据活结点的优先权来选择下一代活结点结点优先权定义为：“在其分支下搜寻一个答案状态须要花费在代价，代价越小，越优先”LC分支限界法分支限界法结点代价相关概念结点代价相关概念代价函数代价函数c(.)c(.)：表示从根结点搜寻到：表示从根结点搜寻到X X，以及在，以及在X X之下搜寻到一个答案状态所需的代价。如下定义之下搜寻到一个答案状态所需的代价。如下定义若若X X是答案结点，则是答案结点，则c(X)c(X)是由空间树根

8、到结点是由空间树根到结点X X的的代价；代价；若若X X不是答案结点且子树不是答案结点且子树X X不包含任何答案结点，不包含任何答案结点，则则c(X)=c(X)=；否则否则c(X)c(X)等于子树等于子树X X中具有最小代价的答案结点中具有最小代价的答案结点的代价。的代价。代价函数犹如一个代价函数犹如一个“有智力的有智力的”排序函数，基于排序函数，基于其值选取下一个其值选取下一个E-E-结点往往可以加快到达一答案结点往往可以加快到达一答案结点的速度。结点的速度。LC分支限界法分支限界法结点代价相关概念相对代价函数g(.)：衡量子树X下搜寻到一个答案状态所需的代价。对随意结点X，可用两种标准来量

9、度一个结点X的相对代价：在生成一个答案结点之前，子树X须要生成的结点数在子树X中离X最近的那个答案结点到X的路径长度结点代价相关概念结点代价相关概念代价函数与相对代价函数o o设以下两个树设以下两个树A B C A B C 均为答案结点且均为答案结点且c(A)c(B)c(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(

10、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)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

11、+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+

12、1k+1,x,xn-1n-1)记当背包载重为记当背包载重为cucu，剩余物品，剩余物品组成的组成的0/10/1背包问题的一个可行背包问题的一个可行解为解为(y(yk k,y,yk+1k+1,y,yn-1n-1)有：有：有：有：zzi ip pi i x xi ip pi i yyi ip pi i0/1背包问题背包问题定义下界函数定义下界函数 LBB(X)=LBB(X)=xipi+yipixipi+yipi定义上界函数定义上界函数 UBB(X)=UBB(X)=xipi+zipixipi+zipi算法实现：算法实现：算法中运用下界变量算法中运用下界变量L L，用于记录迄今为止搜寻到，用于记录迄今

13、为止搜寻到的全部可行解中的最小值的全部可行解中的最小值对任一结点对任一结点X X，若，若UBB(X)LUBB(X)L，则剪去，则剪去X X子树。子树。L L的修正公式的修正公式:若若X X是答案结点是答案结点,L=maxcost(X),L,LBB(X)-e,L=maxcost(X),L,LBB(X)-e否则否则 L=maxL,LBB(X)-e L=maxL,LBB(X)-e有：有：有：有：zzi ip pi i x xi ip pi i yyi ip pi i0/1背包问题的背包问题的LC分枝限界算法分枝限界算法树结点：struct Nodestruct Node/状态空间树结点状态空间树结点

14、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 str

15、uct 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;f

16、loat 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:Knapsac

17、k(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&void LUBound(T cp,float cw,int k,T&LBB,T&UBB);/UBB);/计算计

18、算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,

19、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=

20、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

21、,*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,

22、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=

23、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不变不变 LBB LBB也不变也不变 /生成右孩子结点（生成右孩子结点（x xk k

24、=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

25、-epsilon;if(L L);while(e.UBBL);return L;return L;基于剪枝的基于剪枝的LC分枝限界算法框架分枝限界算法框架程序程序9-39-3（最小值）：（最小值）：Part 1Part 1templatetemplateNode*LCBB(Node*t,T&U)/tNode*LCBB(Node*t,T&U)/t为根，为根，U U为上界变为上界变量量 LiveListNode*lst(mSize);/lst LiveListNode*lst(mSize);/lst为优先权为优先权队列队列 Node*ans=NULL,*x,E=*t;Node*ans=NULL,*

26、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)+if(u(x)+cos

27、t(x)U=u(x)+cost(x)U=u(x)+;elseelse 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;/若队列为空，

28、则算法结束若队列为空，则算法结束 while while（1 1）；）；TSP(Traveling Saleman Problem)问题问题货郎担问题、旅行商问题、邮路问题货郎担问题、旅行商问题、邮路问题问题描述：问题描述：有一个推销员，要到有一个推销员，要到n n个城市推销商品，他从个城市推销商品，他从A A城市城市动身，经过其他动身，经过其他n-1n-1个城市，最终回到动身地个城市，最终回到动身地A A城市，城市，找出一条包含找出一条包含n n个城市的路程最短的哈密顿回路。个城市的路程最短的哈密顿回路。示例：示例：TSP问题问题 数学描述数学描述有向图有向图G=(VG=(V，E)E)：|V

29、|=n|V|=n代价矩阵代价矩阵 Cnn Cnn顶点编号顶点编号0,1,n-10,1,n-1，其中起点编号为，其中起点编号为0 0解空间：解空间：(x(x0 0,x,x1 1,x,xn-1n-1)表示一条哈密顿回路表示一条哈密顿回路x xi i 0,1,n-10,1,n-1x x0 0=x=xn n,x,xi i x xi+1i+1,(x(xi i,x,xi+1i+1)E E；(x(xn-1n-1,x,x0 0)E E目标函数：路径长度；目标函数：路径长度；问题是求使目标函数取最小值的解问题是求使目标函数取最小值的解LC分枝限界法求解分枝限界法求解TSP问题问题解空间的树形结构解空间的树形结构

30、排列树排列树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问题问题l l下界函数下界函数c(X)c(X)归约矩阵归约矩阵 例如例如矩阵约数矩阵约数L L L=11 L=11记图记图G G的代价矩阵的代价矩阵A A的归约的归约矩阵为矩阵为B B。记与图记与图G G结构相同，但以结构相同，但以

31、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图图图图GGGG与与与与G G G G具有相同的哈密顿回路，具有相同的哈密顿回路，具有相同的哈密顿回路，具有相同的哈密顿回路，但同样的回路，但同样的回路，但同样的回路，但同样的回路，前者的长度比后者总是前者的长度比后者总是前者的长度比后者总是前者的长度比后者总是 少少少少 L L L LLC分枝限界法求解分枝限界法求解TSP问题问题l l图图G Gl l图图GG0 0 0 0

32、1 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 0121212121010

33、10101 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分枝限界法求解分枝

34、限界法求解TSP问题问题设状态空间树根结点为R（x0=0）x x1 1=1,2,3,4=1,2,3,4若若x x1 1=1=1，即选定边，即选定边,记状态结点为记状态结点为X X c(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新矩阵新矩阵新矩阵新矩阵AAAAL L

35、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+rc(X)=c(P)+Aij+rP P P PX X X Xr r r r表示图表示图表示图表示图GBGBGBGB上由上由上由上由j j j

36、 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 P是是X X的父结点，的父结点，A A是是P P的归约矩阵的归约矩阵A A经过变换得到经过变换得到AAr r是是AA归约到归约到B

37、 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，否，否则丢弃。则丢弃。搜寻结束条件：扩展结点搜寻结束条件：扩

38、展结点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 7161616

39、161 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,n-1；P1，P2；ai,bi Fi(S)：作业i在调度S下的最终完成时间求使FT(S)=Fi(S)最小的调度方案解空间(n个作业全部可能排列)：x0,x1,xn-1,xk0,1,n-1xi xj,ij是一颗排列树目标函数 FT(S)=Fi(S)9.6 批处理作业调度问题批处理作业调度问题剪枝处理剪枝处理已经找到的最优解的上界值记

40、为已经找到的最优解的上界值记为U U等于到目前为止已经找到的全部可行解中目标函等于到目前为止已经找到的全部可行解中目标函数值最小者数值最小者搜寻过程中已调度作业所需完成时间不能超过搜寻过程中已调度作业所需完成时间不能超过U U，否则丢弃否则丢弃搜寻过程中活结点的下界函数值不能超过搜寻过程中活结点的下界函数值不能超过U U，否则，否则丢弃丢弃U U的初始值为的初始值为搜寻结束：队列空或扩展结点下界函数值超过搜寻结束：队列空或扩展结点下界函数值超过U U以下界函数值为优先权以下界函数值为优先权下界函数下界函数c(X)c(X)：反映，经过状态：反映，经过状态X X所能达到的答所能达到的答案结点的最好

41、状况，值越小，越优先案结点的最好状况，值越小，越优先9.6 批处理作业调度问题批处理作业调度问题l l下界函数下界函数c(X)c(X)l l设设X X是状态空间树上的一个结点是状态空间树上的一个结点l l它确定了一个调度子集它确定了一个调度子集J=x0,x1,xkJ=x0,x1,xk。l lX X之下，每个叶子结点代表的调度之下，每个叶子结点代表的调度S S满足：满足：l l FT(S)FT(S)l l第一部分表示到第一部分表示到X X时已经调度的作业所需完成时间时已经调度的作业所需完成时间和和l l其次部分表示剩余作业在调度方案其次部分表示剩余作业在调度方案S S下所需的完成下所需的完成时间

42、和时间和l lc(X)c(X)表示表示X X下最好的调度方案所需完成时间和下最好的调度方案所需完成时间和l lc(x)=minS FT(S)c(x)=minS FT(S)f f1k1k、f f2k2k分别分别分别分别表示作业表示作业表示作业表示作业k k在在在在设备设备设备设备1 1和和和和2 2上上上上的完成时间的完成时间的完成时间的完成时间9.6 批处理作业调度问题批处理作业调度问题在在X X时对剩余作业，考虑两种特殊调度时对剩余作业，考虑两种特殊调度S1S1：设备：设备1 1没有空闲，设备没有空闲，设备2 2处理作业瞬间完成。处理作业瞬间完成。f1i=f1k+ak+1+ak+2+.+ai

43、f1i=f1k+ak+1+ak+2+.+ai，f2i=f1i+bi f2i=f1i+bi，i=k+1,n-1i=k+1,n-1当当ajaj+1ajaj+1时，时，T1T1取最小值取最小值T1T1S1S1：设备：设备2 2没有空闲，设备没有空闲，设备1 1处理作业瞬间完成。处理作业瞬间完成。f2(k+1)=max(f2k,f1k+minai)+b1(k+1)f2(k+1)=max(f2k,f1k+minai)+b1(k+1)，f2i=f2(k+1)+bk+2+bi i=k+2,n-1f2i=f2(k+1)+bk+2+bi i=k+2,n-1当当bjbj+1bjbj+1时，时，T2T2取最小值取最

44、小值T2T2对对X X下任一调度方案下任一调度方案S S总有总有 FT(S)iJ fi(S)+maxT1,T2=FT(S)iJ fi(S)+maxT1,T2=c(X)c(X)f f1k1k、f f2k2k分别分别分别分别表示作业表示作业表示作业表示作业k k在在在在设备设备设备设备1 1和和和和2 2上上上上的完成时间的完成时间的完成时间的完成时间分枝限界算法分枝限界算法 小结小结 1.1.基本要素基本要素解空间的树形表示。例如，解空间的树形表示。例如，0/10/1背包问题：子集树；背包问题：子集树；n n皇后问皇后问题：满题：满n n叉树；旅行商问题：排列树；等等。叉树；旅行商问题：排列树；

45、等等。剪枝操作。依据约束条件、目标函数的界来设计剪枝操作。剪枝操作。依据约束条件、目标函数的界来设计剪枝操作。优先队列。设计待检测结点的优先级。优先队列。设计待检测结点的优先级。2 2分枝限界法的基本思想分枝限界法的基本思想 树的优先队列优先搜寻树的优先队列优先搜寻 +剪枝剪枝 3 3分枝限界算法形式及终止条件分枝限界算法形式及终止条件算法形式：一般是迭代形式。算法形式：一般是迭代形式。算法终止的条件：求存在性问题时，找到问题的一个解即可算法终止的条件：求存在性问题时，找到问题的一个解即可结束；在求优化问题时，一般要求优先队列为空时才结束，结束；在求优化问题时，一般要求优先队列为空时才结束，但是在满足确定条件时可在找到一个解即可结束（该解即为但是在满足确定条件时可在找到一个解即可结束（该解即为最优解）。最优解）。分枝限界算法分枝限界算法 小结小结4分枝限界法的特性时间性能：最坏的状况要搜寻整个解空间，是困难度是指数型。但假如启发式信息强且剪枝处理得当，平均性能往往很好。空间性能：优先队列往往须要较大的空间开销。