第9章-分支限界法PPT学习课件.ppt

《第9章-分支限界法PPT学习课件.ppt》由会员分享，可在线阅读，更多相关《第9章-分支限界法PPT学习课件.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9 9章章 分支限界法分支限界法1n学习要点学习要点:理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架掌握分支限界法的算法框架n队列式队列式(FIFO)分支限界法分支限界法n优先队列式优先队列式分支限界法分支限界法通过应用范例学习分支限界算法设计策略通过应用范例学习分支限界算法设计策略9.1.1 分支限界法分支限界法n分支限界法类似于回溯法，也是一种在问题的解分支限界法类似于回溯法，也是一种在问题的解空间树空间树T中中搜索搜索问题解的算法。问题解的算法。n分支限界法常以分支限界法常以广度优先广度优先或以或以最小耗费最小耗费(LC)优先优先的方式搜索问题的解空

2、间树。的方式搜索问题的解空间树。在遍历过程中，对已经扩展出的每一个结点根据在遍历过程中，对已经扩展出的每一个结点根据限限界函数界函数估算估算目标函数目标函数的可能取值，从中选取使目标的可能取值，从中选取使目标函数取得极值的结点函数取得极值的结点优先进行优先进行广度优先搜索，从而广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。不断调整搜索方向，尽快找到问题的解。n适用于求解适用于求解最优化最优化问题。问题。9.1 概述概述9.1.2 分支限界法的设计思想分支限界法的设计思想n首先，确定一个合理的首先，确定一个合理的限界函数限界函数，并根据限界函数确，并根据限界函数确定问题的目标函数的界定问

3、题的目标函数的界down,up(具体问题可以只有具体问题可以只有下界下界down，或上界，或上界up)；n然后，按照广度优先策略遍历问题的解空间树：然后，按照广度优先策略遍历问题的解空间树：当搜索到达一个扩展结点时，一次性扩展它的所有孩子，当搜索到达一个扩展结点时，一次性扩展它的所有孩子，估算估算每一个每一个孩子结点的孩子结点的目标函数的可能取值目标函数的可能取值(又称为又称为耗费耗费函数值函数值)；将那些满足约束条件且将那些满足约束条件且耗费函数值耗费函数值不超过不超过目标函数的界目标函数的界的孩子，插入的孩子，插入活动结点表活动结点表PT中，再从中，再从PT表中取耗费函表中取耗费函数值极大

4、数值极大(小小)的下一结点同样扩展；的下一结点同样扩展；直到找到所需的解或直到找到所需的解或PT表为空为止。表为空为止。怎样确定怎样确定“限界函数限界函数”？又如何求得目标函数的界呢？又如何求得目标函数的界呢？n对于对于PT中的中的叶子结点叶子结点：其其耗费函数值是极值耗费函数值是极值(极大或极小极大或极小)，则该叶子结点，则该叶子结点对应的解就是问题的最优解；对应的解就是问题的最优解；否则否则，将问题，将问题目标函数的界目标函数的界(down,up)调整为调整为该该叶子结点的叶子结点的耗费函数值耗费函数值，然后丢弃，然后丢弃PT表中超出目表中超出目标函数界的结点，再次选取结点继续扩展。标函数

5、界的结点，再次选取结点继续扩展。n例例9-1：0/1背包问题。背包问题。实例：实例：假设有假设有4个物品，其重量分别为个物品，其重量分别为(4,7,5,3)，价值分别，价值分别为为(40,42,25,12)，背包容量，背包容量W=10。将给定物品。将给定物品按单位重按单位重量价值从大到小排序量价值从大到小排序，结果如下：，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124n分析：分析：问题的解可表示为问题的解可表示为n元向量元向量x1,x2,.xn,xi 0,1，则可用子集树表示解空间则可用子集树表示解空间,在树中做广在树中做广

6、度优先搜索。度优先搜索。约束条件约束条件:目标函数目标函数:n下界下界Vdb=40(1,0,0,0)贪心思想贪心思想；n上界上界Vub=0+(W-0)(v1/w1)=0+(10-0)10=100；上限界函数：上限界函数：(式式9.1)目标函数的界：目标函数的界：40,10011111100000001124891011121314157653前前i个物品获得的价值个物品获得的价值剩余容量全部装入物品剩余容量全部装入物品i+1，最多能够获得的价值最多能够获得的价值n分支限界法求解分支限界法求解0/1背包问题：背包问题：w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w

7、=11w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12w=9,v=65ub=65234567891PT=2,3无效解无效解PT=5,3PT=6,7,3无效解无效解x1=1x1=0 x2=1x2=0 x3=1x3=0 x4=1x4=0PT=9,7,3V=65X=(1,0,1,0)目标函数范围：目标函数范围：40,100wi=(4,7,5,3)vi=(40,42,25,12)vi/wi=(10,6,5,4)n分支限界法的一般过程：分支限界法的一般过程：1根据限界函数确定目标函数的界根据限界函数确定目标函数的界down,up；2将待处理结点表将待处理结点表PT初

8、始化为空；初始化为空；3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的目标函数值value;3.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大 4.1 i=表表PT中值最大的结点；中值最大的结点；4.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作 4.2.1 估算结点估算结点x的目标函数值的目标函数值value;4.2.2 若若(value=down)，则将结点，则将结点x加入表加入

9、表PT中；中；4.2.3 若若(结点结点x是叶子结点且结点是叶子结点且结点x的的value值在表值在表PT中最大中最大)，则将结点则将结点x对应的解输出，算法结束；对应的解输出，算法结束；4.2.4 若若(结结点点x是是叶叶子子结结点点但但结结点点x的的value值值在在表表PT中中不不是是最最大大)，则令，则令down=value，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除；n常见的两种分支限界法：常见的两种分支限界法：从表从表PT中选择下一扩展结点的不同方式导致不中选择下一扩展结点的不同方式导致不同的分支限界法：同的分支限界法：队列式队列式(FIFO)分支限

10、界法：分支限界法：从左往右从左往右依次插入结点依次插入结点到队尾，按照队列先进先出（到队尾，按照队列先进先出（FIFO）原则选取下）原则选取下一个节点为扩展节点。一个节点为扩展节点。优先队列式优先队列式分支限界法：按照优先队列中规定的优分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。先级选取优先级最高的节点成为当前扩展节点。n最大最大优先队列：使用最大堆，体现最大效益优先。优先队列：使用最大堆，体现最大效益优先。n最小最小优先队列：使用最小堆，体现最小费用优先。优先队列：使用最小堆，体现最小费用优先。例如，上例例如，上例0/1背包问题，采用最大优先队列式分支限背包问

11、题，采用最大优先队列式分支限界法。界法。n应用分支限界法的其他关键问题：应用分支限界法的其他关键问题：如何确定最优解中的各个分量？如何确定最优解中的各个分量？n对每个扩展结点对每个扩展结点保存根结点到该结点的路径保存根结点到该结点的路径；例如，例如，0/1背包问题。将背包问题。将部分解部分解(x1,xi)和该部分解和该部分解的的目标函数的上界值目标函数的上界值都存储在待处理结点表都存储在待处理结点表PT中，中，在搜索过程中表在搜索过程中表PT的状态如下：的状态如下：(0)60 (1,0,0)64 (1,0,1,0)65(a)扩展根结点后表扩展根结点后表PT状态状态 (b)扩展结点扩展结点2后表

12、后表PT状态状态(c)扩展结点扩展结点5后表后表PT状态状态 (d)扩展结点扩展结点6后表后表PT状态，最优解为状态，最优解为(1,0,1,0)65(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 结点结点2结点结点3结点结点3结点结点5结点结点3结点结点6结点结点7结点结点3结点结点7结点结点9n在搜索的过程中在搜索的过程中构建搜索经过的树结构构建搜索经过的树结构，在求得最，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。优解中的各个分量。例如，例如，0/1背包问题。设一个表背

13、包问题。设一个表ST，在表，在表PT中取出最中取出最大值结点进行扩充时，将最大值结点存储到表大值结点进行扩充时，将最大值结点存储到表ST中，中，表表PT和表和表ST的数据结构为的数据结构为(物品物品i-1的选择结果，的选择结果，ub)，在搜索过程中表，在搜索过程中表PT和表和表ST的状态如下：的状态如下：(a)扩展根结点后扩展根结点后 (b)扩展结点扩展结点2后后(c)扩展结点扩展结点5后后 (d)扩展结点扩展结点6后，最优解为后，最优解为(1,0,1,0)65(0,76)(0,60)PTST(0,60)(1,70)PTST(0,76)(0,60)(0,69)(0,64)PTST(0,76)(

14、1,70)(0,60)(0,64)(1,65)PTST(0,76)(1,70)(0,69)说明：说明：ST中记录的就是得到最优解的搜索路径上的各个结点！中记录的就是得到最优解的搜索路径上的各个结点！n分支限界法与回溯法的分支限界法与回溯法的区别区别：求解目标不同求解目标不同：n回溯法回溯法找出满足约束条件的所有解找出满足约束条件的所有解n分支限界法分支限界法找出满足条件的一个解，或某种意找出满足条件的一个解，或某种意义下的最优解义下的最优解搜索方式不同搜索方式不同：n回溯法回溯法深度优先深度优先n分支限界法分支限界法广度优先或最小耗费优先广度优先或最小耗费优先此外，在分支限界法中，每一个活结点

15、此外，在分支限界法中，每一个活结点只有一次只有一次机机会成为扩展结点。会成为扩展结点。9.2.1 TSP问题问题例例9-2：TSP问题。问题。n问题描述：略。问题描述：略。各个城市间的距离用代价矩阵来表示各个城市间的距离用代价矩阵来表示,如果如果(i,j)E，则则cij=。n分析：设城市按自然数分析：设城市按自然数1,2,.,n编号编号解向量：解向量：(x1,x2,.,xn)约束条件：约束条件：n显式约束：显式约束：xi=1,2,.,n (i=1,2,.,n)n隐式约束：隐式约束：(xixj)(cij)9.2 广度优先分支限界法应用举例广度优先分支限界法应用举例目标函数：目标函数：(kV)n下

16、界：下界：ddb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14n上界：上界：dub=16(135421)下限界函数：设已确定的顶点集合下限界函数：设已确定的顶点集合U=(r1,r2,.,rk)(式式9.2)目标函数的界：目标函数的界：14,16271563134253984C=3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a)一个无向图一个无向图 (b)无向图的代价矩阵无向图的代价矩阵从集合从集合U中出来的边中出来的边一条进边，一条出边一条进边，一条出边n优先队列式分支限界法求解优先队列式分支限界法求解TSP问题问题:目标函数范围：目

17、标函数范围：14,16412db=142356781startdb=1413db=1414db=1615db=1923db=1624db=1625db=1932db=1634db=1535db=149101152db=1954db=14121342db=161442db=1845db=15151652db=2017db=19PT=2,3,4db=19PT=6,7,9,10,11,4db=18db=19PT=6,7,9,16,14,4db=20PT=6,7,9,14,4PT=6,7,9,10,13,4PT=6,7,3,4PT=6,7,9,10,14,4d=16135421C=3 1 5 8 3

18、6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 n对每个扩展结点保存根结点到该结点的路径：对每个扩展结点保存根结点到该结点的路径：(g)扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421(1,2)14 (1,3)14 (1,4)16(a)扩展根结点后的状态扩展根结点后的状态 (b)扩展结点扩展结点2后的状态后的状态(c)扩展结点扩展结点3后的状态后的状态(d)扩展结点扩展结点11后的状态后的状态(e)扩展结点扩展结点13后的状态后的状态(1,3)14 (1,4)16 (1,2,3)16 (1,2,4)16(1,4)16 (1,2,3)16 (1,2,4)16 (1

19、,3,2)16 (1,3,4)15 (1,3,5)14(1,4)16 (1,2,3)16 (1,2,4)16 (1,3,2)16 (1,3,4)15 (1,3,5,4)14(1,4)16 (1,2,3)16 (1,2,4)16 (1,3,2)16 (1,3,4)15 (1,3,5,4,2)16(1,4)16 (1,2,3)16 (1,2,4)16 (1,3,2)16 (1,3,5,4,2)16 (1,3,4,5)15(1,4)16 (1,2,3)16 (1,2,4)16 (1,3,2)16 (1,3,5,4,2)16 (1,3,4,5)15(f)扩展结点扩展结点10后的状态后的状态nTSP问题

20、算法的伪代码描述：问题算法的伪代码描述：1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3for(i=1;i=1)5.1 i=k+1;5.2 xi=1;5.3 while(xi=n)5.3.1 如果路径上顶点不重复，则如果路径上顶点不重复，则 5.3.1.1 根据式根据式7.2计算目标函数值计算目标函数值db；5.3.1.2 if(db=+=+kijpiEvrijjjjvrcrrcdbpi21,11min1段的最短边段的最短边第第与顶点与顶点ri+1相连的边中相连的边中

21、,代价最小的边代价最小的边(剩余顶点能够达到剩余顶点能够达到的最小代价的最小代价)n优先队列式分支限界法求解：优先队列式分支限界法求解：64sAdb=20231startdb=14sBdb=16sCdb=157BDdb=188BEdb=189BFdb=185CEdb=16CFdb=181110EGdb=22EHdb=16目标函数范围：目标函数范围：14,18ABsCDEFGHt492386884756866537PT=3,4PT=3,5,6PT=7,8,9,5,6PT=7,8,9,11,6c=16sCEHt(4+8+(5+3)n搜索算法描述：搜索算法描述：while(true)for(int

22、j=1;j=n;j+)if(cE.ijinf)&(E.length+cE.ijdistj)/顶点顶点i到顶点到顶点j可达，且满足控制约束可达，且满足控制约束 distj=E.length+cE.ij;prevj=E.i;/加入活结点优先队列加入活结点优先队列 MinHeapNode N;N.i=j;N.length=distj;H.Insert(N);try H.DeleteMin(E);/取下一扩展结点取下一扩展结点 catch(OutOfBounds)break;/优先队列空优先队列空 顶点顶点i和和j间有边，且此路间有边，且此路径长小于原先从原点到径长小于原先从原点到j的路径长的路径长

23、9.2.3 装载问题装载问题n问题描述：略。问题描述：略。n分析：分析：解空间：解空间：X=(x1,x2,xn)，xiSi=0,1，i=1,2,n约束函数：约束函数：目标函数：目标函数：n下界：下界：n上界：上界：上限界函数：上限界函数：左孩子：左孩子：Ew+wi+1 bestw改进改进n搜索算法设计：搜索算法设计：队列式队列式分支限界：分支限界：while(true)/检查左儿子结点检查左儿子结点 Type wt=Ew+wi;/左儿子结点的重量左儿子结点的重量 if(wt bestw)bestw=wt;/加入活结点队列加入活结点队列 if(i bestw&i n)Q.Add(Ew);/可能含

24、最优解可能含最优解 Q.Delete(Ew);/取下一扩展结点取下一扩展结点if(Ew=-1)/同层结点尾部同层结点尾部 if(Q.IsEmpty()return bestw;Q.Add(-1);/同层结点尾部标志同层结点尾部标志 Q.Delete(Ew);/取下一扩展结点取下一扩展结点 i+;r-=wi;/进入下一层进入下一层 提前更新提前更新bestw 右儿子剪枝右儿子剪枝 优先队列式优先队列式分支限界：分支限界：采用最大优先队列存储活结点表。活结点采用最大优先队列存储活结点表。活结点x在优先队在优先队列中的列中的优先级定义为优先级定义为：从根结点到结点：从根结点到结点x的路径所相应的路径

25、所相应的载重量的载重量Ew+剩余集装箱的重量剩余集装箱的重量r。子集树中叶结点所相应的载重量与其优先级相同，子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。叶结点所相应的解即为最优解。此时可终止算法。n 实现方法实现方法：(PT表结点的结构表结点的结构)在活结点中保存从解空间树的根结点到该活结点的在活结点中保存从解空间树的根结点到该活结点的路径；路径；搜索进程中保存当前已构造出的部分解空间树；搜索进程中保存当前已构造出的部分解空间树；n算算法描述（采用第二种方式实

26、现法描述（采用第二种方式实现PT表）：表）：template class HeapNode;class bbnode friend void AddLiveNode(MaxHeapHeapNode&,bbbnode*,int,bool,int);friend int MaxLoading(int*,int,int,int*);friend class AdjacencyGraph;private:bbnode*parent;/指向父结点的指针指向父结点的指针 bool LChild;/左孩子结点标志左孩子结点标志;templateclass HeapNode friend void AddLi

27、veNode(MaxHeapHeapNode&,bbnode*,Type,bool,int);friend Type MaxLoading(Type*,Type,int,int*);public:operator Type()const return uweight;private:bbnode*ptr;/指向活结点在子集树中相应结点的指针指向活结点在子集树中相应结点的指针 Type uweight;/活结点优先级活结点优先级(上界上界)int level;/活结点在子集树中所处的层序号活结点在子集树中所处的层序号;templatevoid AddLiveNode(MaxHeapHeapNod

28、e&H,bbnode*E,Type wt,bool ch,int lev)/将活结点加入到表示活结点优先队列的最大堆将活结点加入到表示活结点优先队列的最大堆H中中 bbnode*b=new bbnode;b-parent=E;b-Lchild=ch;HeapNode N;N.uweight=wt;N.level=lev;N.ptr=b;H.Inset(N);templateType MaxLoading(Type w,Type c,int n,int bestx)/优先队列式优先队列式分支限界法分支限界法,返回最优装载重量，返回最优装载重量，bestx返回最优解返回最优解 /定义最大堆的容量为

29、定义最大堆的容量为1000 MaxHeapHeapNode H(1000);/定义剩余重量数组定义剩余重量数组r Type*r=new Typen+1;rn=0;for(int j=n-1;j0;j-)rj=rj+1+wj+1;/初始化初始化 int i=1;/当前扩展结点所处的层当前扩展结点所处的层 bbnode*E=0;/当前扩展结点当前扩展结点 Type Ew=0;/扩展结点所相应的载重量扩展结点所相应的载重量 /搜索子集空间树搜索子集空间树 while(i!=n+1)/非叶子结点非叶子结点 /检查当前扩展结点的孩子结点检查当前扩展结点的孩子结点 if(Ew+wi=c)/左孩子结点为可行

30、结点左孩子结点为可行结点 AddLiveNode(H,E,Ew+wi+ri,true,i+1);/右孩子结点右孩子结点 AddLiveNode(H,E,Ew+ri,false,i+1);/取下一扩展结点取下一扩展结点 HeapNode N;H.DeleteMax(N);/非空非空 i=N.level;E=N.prt;Ew=N.uweight ri-1;/构造当前最优解构造当前最优解 for(int j=n;j0;j-)bestxj=E-Lchild;E=E-parent;return Ew;9.2.4 批处理作业调度问题批处理作业调度问题例例9-4：批处理作业调度问题。：批处理作业调度问题。n

31、问题描述：问题描述：给定给定n个作业的集合个作业的集合J=J1,J2,Jn，每个作业都有每个作业都有3项任务分别在项任务分别在3台机器上完成，作台机器上完成，作业业Ji需要机器需要机器j的处理时间为的处理时间为tij(1in,1j3)，每个，每个作业必须先由机器作业必须先由机器1处理，再由机器处理，再由机器2处理，最后处理，最后由机器由机器3处理。处理。批处理作业调度问题要求确定这批处理作业调度问题要求确定这n个作业的最优处个作业的最优处理顺序，使得从第理顺序，使得从第1个作业在机器个作业在机器1上处理开始，到上处理开始，到最后一个作业在机器最后一个作业在机器3上处理结束所需的时间最少。上处理

32、结束所需的时间最少。实例：实例：设设J=J1,J2,J3,J4是是4个待处理的作业，需要个待处理的作业，需要的处理时间如下所示。的处理时间如下所示。若处理顺序为若处理顺序为(J2,J3,J1,J4)，则从作业，则从作业2在机器在机器1处理处理开始到作业开始到作业4在机器在机器3处理完成的调度方案如下：处理完成的调度方案如下：T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4机器1 机器2 机器3J2:10 J3:9 J1:5 J4:7机器机器1机器机器2机器机器3(表示空闲，最后完成处理时间为表示空闲，最后完成处理时间为54)空闲空闲:10 J2:5 空闲空闲:4 J3:9

33、J1:7 J4:8空闲空闲:15 J2:2 空闲空闲:11 J3:5 空闲空闲:2 J1:9 J4:10等待时间等待时间+处理时间处理时间n分析：分析：解向量：解向量：X=(x1,x2,.,xn)排列树排列树约束条件：约束条件：n显式：显式：xi=J1,J2,.,Jn目标函数目标函数:sum3=下限界函数：下限界函数：机器机器3有空闲有空闲机器机器3有积压有积压，极小化，极小化其中其中，sum2n=maxsum1n,sum2n-1+tn2；sum1n=sum1n-1+tn1设设M是已安排好的作业集合，是已安排好的作业集合，M 1,2,.,n,|M|=k。现在要处理作业现在要处理作业k+1，有：

34、，有：sum1k+1=sum1k+tk+1,1sum2k+1=maxsum1k+1,sum2k+tk+1,2maxsum2n,sum3n-1+tn3 n目标函数的下界目标函数的下界:sum3db=说明说明：最理想的情况下，机器：最理想的情况下，机器1和机器和机器2均无空闲，均无空闲，最后处理的作业恰好是在机器最后处理的作业恰好是在机器3上处理时间最短的作上处理时间最短的作业。业。如上实例，如上实例，sum3db=36遍历并估算解空间树上各结点的目标函数的下界值：遍历并估算解空间树上各结点的目标函数的下界值：根结点：根结点：sum1=0,sum2=0,M=k=0T 5 7 910 5 2 9 9

35、 5 7 8 10J1J2J3J4机器1 机器2 机器3n优先队列式分支限界法求解过程：优先队列式分支限界法求解过程：J4,sum1=0+7db=38sum2=152 M=k=1J1,sum1=0+5db=36sum2=5+7=121 M=k=0startsum1=0,sum2=03 M=k=1J2,sum1=0+10db=44sum2=124 M=k=1J3,sum1=0+9db=40sum2=185 M=k=16 M=1 k=2J1J2,sum1=15db=42sum2=207 M=1 k=2J1J3,sum1=14db=38sum2=228 M=1 k=2J1J4,sum1=12db=3

36、6sum2=209 M=1,4 k=3J1J4J2,sum1=22db=41sum2=2710 M=1,4 k=3J1J4J3,sum1=21db=37sum2=3011 M=1,4,3 k=4J1J4J3J2,sum1=31db=36sum24=36PT=2,3,4,5PT=6,7,8,3,4,5PT=6,7,9,10,3,4,5PT=6,7,9,11,3,4,5X=(J1,J4,J3,J2)sum3=sum24+t23=38sum1k=sum1k-1+tk,1sum2k=maxsum1k,sum2k-1+tk,2T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4机器机器1

37、 机器机器2 机器机器3下界下界sum3db=36n从上例可知：优先队列式分支限界法中，从上例可知：优先队列式分支限界法中，扩展结点表扩展结点表PT取得极值的叶子结点就对应的是问取得极值的叶子结点就对应的是问题的最优解；题的最优解；扩展结点的过程，一开始实际类似扩展结点的过程，一开始实际类似“深度优先深度优先”。n思考：思考：将例将例9-2和例和例9-4改成改成FIFO式分支限界法，搜索过程式分支限界法，搜索过程有何不同？有何不同？在算法的实现上，在算法的实现上，FIFO式分支限界法和优先队列式分支限界法和优先队列式分支限界法的式分支限界法的PT表数据结构一样吗？表数据结构一样吗？课后作业课后

38、作业n采用分支限界法求解下列作业调度问题，采用分支限界法求解下列作业调度问题，4个作业个作业J1,J2,J3,J4在机器在机器M1,M2上处理的时间矩阵如图上处理的时间矩阵如图所示。求最佳的处理顺序，使得所示。求最佳的处理顺序，使得4个作业从开始到个作业从开始到结束处理的时间最短。结束处理的时间最短。(要求：画出解空间的展开要求：画出解空间的展开)M1M2J1J2J3J49.3 最小消耗最小消耗(LC)搜索法搜索法9.3.1 LC检索检索n在在FIFO分枝限界法中，对下一个分枝限界法中，对下一个E-结点的选择规结点的选择规则相当死板，在某种意义上是盲目的。则相当死板，在某种意义上是盲目的。n对

39、活结点使用一个对活结点使用一个“有智力有智力”的排序函数的排序函数 c(.)来来选取下一个选取下一个E-结点往往可以加快到达一答案结点结点往往可以加快到达一答案结点的速度。的速度。n对任意结点对任意结点x，可用两种标准来量度：，可用两种标准来量度：在生成一个答案结点之前，子树在生成一个答案结点之前，子树x需要生成的需要生成的结点结点个数个数；在子树在子树x中离中离x最近的那个答案结点到最近的那个答案结点到x的的路径长度路径长度。n使用第一种度量：使用第一种度量：图中树的根结点付出的代价是图中树的根结点付出的代价是4。结点。结点(18和和34)，(29和和35)以以及及(30和和38)的代价分别

40、是的代价分别是3,2和和1。所有在所有在2,3和和4级上剩余结点的代价应分别大于级上剩余结点的代价应分别大于3,2和和1。以这。以这些代价作为选择下一个些代价作为选择下一个E-结点的依据，则结点的依据，则E-结点依次为结点依次为1,18,29和和30。另外，不得已生成的结点为。另外，不得已生成的结点为2,34,50,19,24,32。n使用第二种度量，则使用第二种度量，则E-结点只是由根到最近的那个答案结结点只是由根到最近的那个答案结点路径上的那些结点。点路径上的那些结点。图图9.1 4-皇后问题皇后问题总是生成最小数目的结点总是生成最小数目的结点9.3.2 LC方法要点方法要点n对状态空间树

41、上的一个对状态空间树上的一个答案结点答案结点x,定义定义实际代价实际代价函数函数cost(x)。cost(x)的内涵：从状态空间树根结点出发，到达一的内涵：从状态空间树根结点出发，到达一个答案结点个答案结点x，实际需要付出的，实际需要付出的“代价代价”。cost(x)的定义：原则上应根据具体问题加以定义。的定义：原则上应根据具体问题加以定义。n对状态空间树对状态空间树上任一结点上任一结点x，定义，定义代价函数代价函数c(x)。c(x)的内涵：从状态空间树根结点出发，经过的内涵：从状态空间树根结点出发，经过x结点，结点，在在以结点以结点x为根的子树上为根的子树上，搜索到一个答案结点，搜索到一个答

42、案结点，所需要付出的代价。所需要付出的代价。定义定义c(x)的一般原则：的一般原则：n若若x是答案结点，则：是答案结点，则：c(x)=cost(x)；n若若x不是答案结点，但以不是答案结点，但以x为根的子树上为根的子树上至少有一个至少有一个答案结点，则：答案结点，则：c(x)=minc(answer)|answer:x上所有答案结点上所有答案结点n若若x不是答案结点，且以不是答案结点，且以x为根的子树上也没有答案为根的子树上也没有答案结点，则：结点，则：c(x)=+n对状态空间树上结点对状态空间树上结点x,定义定义估算函数估算函数 ，且使满，且使满足：足：c(x)。注：与注：与c(x)相比，相

43、比，应是当前应是当前“可计算可计算”的。的。n设计一个活结点表设计一个活结点表L，用于存放搜索过程的，用于存放搜索过程的“活结活结点点”。该表的数据结构可选择。该表的数据结构可选择有序表有序表或或堆堆。即要求：活结点表上的所有结点，按照它们即要求：活结点表上的所有结点，按照它们估算函估算函数取值数取值，构成一个有序表或堆。，构成一个有序表或堆。=h(x)+g(x)nLC法搜索过程：法搜索过程：初始：把状态空间树的根结点，做为活结点表初始：把状态空间树的根结点，做为活结点表L的的第一个结点；第一个结点；重复以下两步，直到找到一个解，或重复以下两步，直到找到一个解，或L为空：为空：n从从L上选出具

44、有最小上选出具有最小 的结点，作为当前的结点，作为当前E-结点。结点。n依次搜索当前依次搜索当前E-结点的所有子结点。若子结点是答结点的所有子结点。若子结点是答案结点，则结束；否则，把子结点加入有序表案结点，则结束；否则，把子结点加入有序表L。9.3.3 LC方法应用举例方法应用举例n15迷问题。迷问题。n问题描述：把编号为问题描述：把编号为115的棋子，随意放在的棋子，随意放在44格的格的棋盘上棋盘上(空出一个格空出一个格)。要求：经过有限步的移动，把。要求：经过有限步的移动，把棋盘上棋子的棋盘上棋子的“初态初态”，变成棋子号与棋盘号一致的，变成棋子号与棋盘号一致的目标状态。目标状态。(注：

45、注：“移动移动”仅限于仅限于空格周围空格周围棋子棋子)实例：实例：初态初态 目标状态目标状态124563791012813141115123456789101112131415n分析：分析：实际代价函数实际代价函数cost(x):若若x是目标状态，则：是目标状态，则：cost(x)等于从棋盘初态，等于从棋盘初态，经逐步移动棋子而到达目标状态经逐步移动棋子而到达目标状态x，实际需要移动实际需要移动棋子总步数棋子总步数。代价函数代价函数c(x):n若若x是目标状态，则：是目标状态，则：c(x)=cost(x)n若若x不是目标状态，但不是目标状态，但x所在子树上存在目标状态结所在子树上存在目标状态结

46、点，点，则：则：c(x)=min c(x)|x：x子树上所有目标状子树上所有目标状态结点态结点n若若x不是目标状态，且不是目标状态，且x所在子树上也不存在任何目所在子树上也不存在任何目标状态结点，则标状态结点，则c(x)=+定义估算函数：定义估算函数：=h(x)+g(x)n其中，其中，h(x):从状态空间树的根结点到从状态空间树的根结点到x结点结点路径长度路径长度；g(x)：x状态下，状态下，没有没有达到达到“目标状态目标状态”的的棋子数量棋子数量。1245637910128131411151245637910128131411151234567910128131411151245637910

47、12813141115g1=6h1=01g2=7g3=5g4=7234左左下下右右1123456791012813141115g3=531123456791012813141115123456791012813141115123456127910813141115123567491012813141115123456789101213141115g5=6657左左右右下下g6=4g7=52g9=3g8=5下下上上983123456789101213141115g9=39312345678910121314111512345678910121513141112345678910111213141

48、51234568910712131411151234567891012131411151011左左下下g10=2g11=3g12=3g13=1g14=3131214左左下下上上45123456789101112131415g13=1135123456789101112131415g14=214123456789101112131415g15=0156目标状态！目标状态！左左右右15移动棋子步数：移动棋子步数：6移动顺序：移动顺序：378121115nLC方法的算法之一：搜索到方法的算法之一：搜索到一个答案结点一个答案结点void LC(struct Node*root)struct Node*

49、x,*E,*L;/L:活结点表。活结点表。Lroot;/root:状态空间树根结点。状态空间树根结点。finished=0;E;/E:扩展结点扩展结点 while(!finishied)&(“L非空非空”)ELEAST(L);/选出并删去有最小选出并删去有最小 for(E的每一个子结点的每一个子结点x)if(“x是解是解”)输出解；输出解；finishied=1;else ADD(x,L);x-parent=E)nLC方法的算法之二：搜索方法的算法之二：搜索最优解最优解void LC_option(struct Node*root)struct Node*x,*E,*L;/L:活结点表。活结点

50、表。Lroot;/root:状态空间树根结点。状态空间树根结点。finished=0;E ;/E:扩展结点扩展结点 while(!finishied)&(“L非空非空”)E LEAST(L);/选出并删去有最小选出并删去有最小 结点结点 if(“E是解是解”)输出解；输出解；finishied=1;else for(E的每一个子结点的每一个子结点x)ADD(x,L);x-parent=E;本章小结本章小结n分支限界法常以分支限界法常以广度优先广度优先或以或以最小耗费最小耗费(LC)优先的方式搜优先的方式搜索问题的解空间树。索问题的解空间树。n在遍历过程中，对已经扩展出的每一个结点根据在遍历过程