第9章-分支限界法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,9,章 分支限界法,*,学习要点,:,理解分支限界法的剪枝搜索策略,掌握分支限界法的算法框架,队列式,(FIFO),分支限界法,优先队列式,分支限界法,通过应用范例学习分支限界算法设计策略,*,9.1.1,分支限界法,分支限界法类似于回溯法，也是一种在问题的解空间树,T,中,搜索,问题解的算法。,分支限界法常以,广度优先,或以,最小耗费,(,LC,),优先的方式搜索问题的解空间树。,在遍历过程中，对已经扩展出的每一个结点根据,限界函数,估算,目标函数,的可能取值，从中选取使目标函数取得极值的结点,优先进行,广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。,适用于求解,最优化,问题。,9.1,概述,*,9.1.2,分支限界法的设计思想,首先，确定一个合理的,限界函数,，并根据限界函数确定问题的目标函数的界,down, up(,具体问题可以只有下界,down,，或上界,up),；,然后，按照广度优先策略遍历问题的解空间树：,当搜索到达一个扩展结点时，一次性扩展它的所有孩子，估算,每一个,孩子结点的,目标函数的可能取值,(,又称为,耗费函数值,),；,将那些满足约束条件且,耗费函数值,不超过,目标函数的界,的孩子，插入,活动结点表,PT,中，再从,PT,表中取耗费函数值极大,(,小,),的下一结点同样扩展；,直到找到所需的解或,PT,表为空为止。,怎样确定“限界函数”？又如何求得目标函数的界呢？,*,对于,PT,中的,叶子结点,：,其,耗费函数值是极值,(,极大或极小,),，则该叶子结点对应的解就是问题的最优解；,否则,，将问题,目标函数的界,(down, up),调整为,该叶子结点的,耗费函数值,，然后丢弃,PT,表中超出目标函数界的结点，再次选取结点继续扩展。,*,例,9-1,：,0/1,背包问题。,实例：,假设有,4,个物品，其重量分别为,(4, 7, 5, 3),，价值分别为,(40, 42, 25, 12),，背包容量,W,=10,。将给定物品,按单位重量价值从大到小排序,，结果如下：,物品,重量,(,w,),价值,(,v,),价值,/,重量,(,v,/,w,),1,4,40,10,2,7,42,6,3,5,25,5,4,3,12,4,*,分析：,问题的解可表示为,n,元向量,x,1,x,2, .,x,n,x,i,0,1,，,则可用子集树表示解空间,在树中做广度优先搜索。,约束条件,:,目标函数,:,下界,V,db,=40 (1, 0, 0, 0),贪心思想,；,上界,V,ub,=0+(,W,-0)(,v,1,/,w,1,),=0+(10-0)10=100,；,上限界函数：,(,式,9.1),目标函数的界：,40, 100,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,2,4,8,9,10,11,12,13,14,15,7,6,5,3,前,i,个物品获得的价值,剩余容量全部装入物品,i,+1,，,最多能够获得的价值,*,分支限界法求解,0/1,背包问题：,w,=0,v,=0,ub,=100,w,=4,v,=40,ub,=76,w,=0,v,=0,ub,=60,w,=11,w,=4,v,=40,ub,=70,w,=9,v,=65,ub,=69,w,=4,v,=40,ub,=64,w,=12,w,=9,v,=65,ub,=65,2,3,4,5,6,7,8,9,1,PT=2, 3,无效解,PT=5, 3,PT=6, 7, 3,无效解,x,1,=1,x,1,=0,x,2,=1,x,2,=0,x,3,=1,x,3,=0,x,4,=1,x,4,=0,PT=9, 7, 3,V=65,X=(1, 0, 1, 0),目标函数范围：,40, 100,w,i,=(4, 7, 5, 3),v,i,= (40, 42, 25, 12),v,i,/,w,i,=(10, 6, 5, 4),*,分支限界法的一般过程：,1,根据限界函数确定目标函数的界,down, up,；,2,将待处理结点表,PT,初始化为空；,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,加入表,PT,中；,4.2.3,若,(,结点,x,是叶子结点且结点,x,的,value,值在表,PT,中最大,),，,则将结点,x,对应的解输出，算法结束；,4.2.4,若,(,结点,x,是叶子结点但结点,x,的,value,值在表,PT,中不是最大,),，则令,down=value,，并且将表,PT,中所有小于,value,的结点删除；,*,常见的两种分支限界法：,从表,PT,中选择下一扩展结点的不同方式导致不同的分支限界法：,队列式,(FIFO),分支限界法：,从左往右,依次插入结点到队尾，按照队列先进先出（,FIFO,）原则选取下一个节点为扩展节点。,优先队列式,分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,最大,优先队列：使用最大堆，体现最大效益优先。,最小,优先队列：使用最小堆，体现最小费用优先。,例如，上例,0/1,背包问题，采用最大优先队列式分支限界法。,*,应用分支限界法的其他关键问题：,如何确定最优解中的各个分量？,对每个扩展结点,保存根结点到该结点的路径,；,例如，,0/1,背包问题。将,部分解,(,x,1, ,x,i,),和该部分解的,目标函数的上界值,都存储在待处理结点表,PT,中，在搜索过程中表,PT,的状态如下：,(0)60 (1,0,0)64,(1,0,1,0)65,(a),扩展根结点后表,PT,状态,(b),扩展结点,2,后表,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,结点,9,*,在搜索的过程中,构建搜索经过的树结构,，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。,例如，,0/1,背包问题。设一个表,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),PT,ST,(0,60) (1,70),PT,ST,(0,76),(0,60) (0,69) (0,64),PT,ST,(0,76) (1,70),(0,60) (0,64),(1,65),PT,ST,(0,76) (1,70) (0,69),说明：,ST,中记录的就是得到最优解的搜索路径上的各个结点！,*,分支限界法与回溯法的,区别,：,求解目标不同,：,回溯法,找出满足约束条件的所有解,分支限界法,找出满足条件的一个解，或某种意义下的最优解,搜索方式不同,：,回溯法,深度优先,分支限界法,广度优先或最小耗费优先,此外，在分支限界法中，每一个活结点,只有一次,机会成为扩展结点。,*,9.2.1 TSP,问题,例,9-2,：,TSP,问题。,问题描述：略。,各个城市间的距离用代价矩阵来表示,如果,(,i,j,),E,，则,c,ij,=,。,分析：设城市按自然数,1, 2, .,n,编号,解向量：,(,x,1,x,2, .,x,n,),约束条件：,显式约束：,x,i,=1, 2, .,n,(,i,=1, 2, .,n,),隐式约束：,(,x,i,x,j,) (,c,ij,),9.2,广度优先分支限界法应用举例,*,目标函数：,(,k,V,),下界：,d,db,=,(1+3)+(3+6)+(1+2)+,(3+4)+(2+3)/2=14,上界：,d,ub,=16(135421),下限界函数：设已确定的顶点集合,U=(,r,1,r,2, .,r,k,),(,式,9.2),目标函数的界：,14,16,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,C,=, 3 1 5 8,3 6 7 9,1 6 4 2,5 7 4 3,8 9 2 3 ,(a),一个无向图,(b),无向图的代价矩阵,从集合,U,中出来的边,一条进边，一条出边,*,优先队列式分支限界法求解,TSP,问题,:,目标函数范围：,14, 16,4,12,db,=14,2,3,5,6,7,8,1,start,db,=14,13,db,=14,14,db,=16,15,db,=19,23,db,=16,24,db,=16,25,db,=19,32,db,=16,34,db,=15,35,db,=14,9,10,11,52,db,=19,54,db,=14,12,13,42,db,=16,14,42,db,=18,45,db,=15,15,16,52,db,=20,17,db,=19,PT=2, 3, 4,db,=19,PT=6, 7 , 9, 10,11, 4,db,=18,db,=19,PT=6, 7, 9, 16, 14, 4,db,=20,PT=6, 7, 9, 14, 4,PT=6, 7, 9,10, 13, 4,PT=6, 7, 3, 4,PT=6, 7, 9,10, 14, 4,d,=16,135421,C,=, 3 1 5 8,3 6 7 9,1 6 4 2,5 7 4 3,8 9 2 3 ,*,对每个扩展结点保存根结点到该结点的路径：,(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, 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,后的状态,*,TSP,问题算法的伪代码描述：,1,根据限界函数计算目标函数的下界,down,；采用贪心法得到上界,up,；,2,将待处理结点表,PT,初始化为空；,3,for (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,=,+,+,=,+,k,i,j,p,i,E,v,r,i,j,j,j,j,v,r,c,r,r,c,db,p,i,2,1,1,1,min,1,段的最短边,第,与顶点,r,i,+1,相连的边中,代价最小的边,(,剩余顶点能够达到,的最小代价,),*,优先队列式分支限界法求解：,6,4,sA,db,=20,2,3,1,start,db,=14,sB,db,=16,sC,db,=15,7,BD,db,=18,8,BE,db,=18,9,BF,db,=18,5,CE,db,=16,CF,db,=18,11,10,EG,db,=22,EH,db,=16,目标函数范围：,14, 18,A,B,s,C,D,E,F,G,H,t,4,9,2,3,8,6,8,8,4,7,5,6,8,6,6,5,3,7,PT=3, 4,PT=3, 5, 6,PT=7, 8, 9, 5, 6,PT=7, 8, 9, 11, 6,c,=16,sCEHt,(4+8+(5+3),*,搜索算法描述：,while (true) ,for (int 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,的路径长,*,9.2.3,装载问题,问题描述：略。,分析：,解空间：,X,=(,x,1,x,2,x,n,),，,x,i,S,i,=0, 1,，,i,=1,2,n,约束函数：,目标函数：,下界：,上界：,上限界函数：,左孩子：,Ew,+,w,i,+1 ,bestw,改进,*,搜索算法设计：,队列式,分支限界：,while (true) ,/ 检查左儿子结点,Type wt = Ew + wi; / 左儿子结点的重量,if (,wt bestw),bestw = wt,;,/ 加入活结点队列,if (i bestw & i &,bbbnode *, int, bool, int);,friend int MaxLoading(int *, int, int, int *);,friend class AdjacencyGraph;,private:,bbnode * parent; /,指向父结点的指针,bool LChild; /,左孩子结点标志,;,template,class HeapNode ,friend void AddLiveNode(MaxHeap &,bbnode *, Type, bool, int);,*,friend Type MaxLoading(Type *, Type, int, int *);,public:,operator Type() const return uweight;,private:,bbnode *ptr; /,指向活结点在子集树中相应结点的指针,Type uweight; /,活结点优先级,(,上界,),int level; /,活结点在子集树中所处的层序号,;,template,void AddLiveNode(MaxHeap &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);,template,Type MaxLoading(Type w, Type c, int n, int bestx),/,优先队列式,分支限界法,返回最优装载重量，,bestx,返回最优解,/,定义最大堆的容量为,1000,MaxHeap 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 0; j-) ,bestxj = E-Lchild;,E = E-parent;,return Ew;,*,9.2.4,批处理作业调度问题,例,9-4,：批处理作业调度问题。,问题描述：,给定,n,个作业的集合,J,=,J,1,J,2, ,J,n,，每个作业都有,3,项任务分别在,3,台机器上完成，作业,J,i,需要机器,j,的处理时间为,t,ij,(1,i,n, 1,j,3),，每个作业必须先由机器,1,处理，再由机器,2,处理，最后由机器,3,处理。,批处理作业调度问题要求确定这,n,个作业的最优处理顺序，使得从第,1,个作业在机器,1,上处理开始，到最后一个作业在机器,3,上处理结束所需的时间最少。,*,实例：,设,J,=,J,1,J,2,J,3,J,4,是,4,个待处理的作业，需要的处理时间如下所示。,若处理顺序为,(,J,2,J,3,J,1,J,4,),，则从作业,2,在机器,1,处理开始到作业,4,在机器,3,处理完成的调度方案如下：,T,5 7 9,10 5 2,9 9 5,7 8 10,J,1,J,2,J,3,J,4,机器,1,机器,2,机器,3,J,2,:10,J,3,:9,J,1,:5,J,4,:7,机器,1,机器,2,机器,3,(,表示空闲，最后完成处理时间为,54),空闲,:10,J,2,:5,空闲,:4,J,3,:9,J,1,:7,J,4,:8,空闲,:15,J,2,:2,空闲,:11,J,3,:5,空闲,:2,J,1,:9,J,4,:10,等待时间,+,处理时间,*,分析：,解向量：,X,=(,x,1,x,2, .,x,n,),排列树,约束条件：,显式：,x,i,=,J,1,J,2, .,J,n,目标函数,:,sum,3,=,下限界函数：,机器,3,有空闲,机器,3,有积压,，极小化,其中,，,sum,2,n,=,max,sum,1,n,sum,2,n,-1 +,t,n,2,；,sum,1,n,=,sum,1,n,-1+,t,n,1,设,M,是已安排好的作业集合，,M,1, 2, .,n,|M|=,k,。,现在要处理作业,k,+1,，有：,sum,1,k,+1=,sum,1,k,+,t,k+,1,1,sum,2,k,+1=,max,sum,1,k,+1,sum,2,k, +,t,k+,1,2,max,sum,2,n,sum,3,n,-1+,t,n,3,*,目标函数的下界,:,sum,3,db,=,说明,：最理想的情况下，机器,1,和机器,2,均无空闲，最后处理的作业恰好是在机器,3,上处理时间最短的作业。,如上实例，,sum,3,db,= =36,遍历并估算解空间树上各结点的目标函数的下界值：,根结点：,sum,1=0,sum,2=0, M=,k,=0,T,5 7 9,10 5 2,9 9 5,7 8 10,J,1,J,2,J,3,J,4,机器,1,机器,2,机器,3,*,优先队列式分支限界法求解过程：,J,4, sum1=0+7,db,=38,sum2=15,2,M= k=1,J,1, sum1=0+5,db,=36,sum2=5+7=12,1,M= k=0,start,sum1=0, sum2=0,3,M= k=1,J,2, sum1=0+10,db,=44,sum2=12,4,M= k=1,J,3, sum1=0+9,db,=40,sum2=18,5,M= k=1,6,M=1 k=2,J,1,J,2, sum1=15,db,=42,sum2=20,7,M=1 k=2,J,1,J,3, sum1=14,db,=38,sum2=22,8,M=1 k=2,J,1,J,4, sum1=12,db,=36,sum2=20,9,M=1, 4 k=3,J,1,J,4,J,2, sum1=22,db,=41,sum2=27,10,M=1, 4 k=3,J,1,J,4,J,3, sum1=21,db,=37,sum2=30,11,M=1, 4, 3 k=4,J,1,J,4,J,3,J,2, sum1=31,db,=36,sum24=36,PT=2, 3, 4, 5,PT=6, 7, 8, 3, 4, 5,PT=6, 7, 9, 10, 3, 4, 5,PT=6, 7, 9,11, 3, 4, 5,X=(,J,1,J,4,J,3,J,2,),sum3=sum24+t,23,=38,sum1k=sum1k-1+,t,k,1,sum2k=maxsum1k, sum2k-1 +,t,k,2,T,5 7 9,10 5 2,9 9 5,7 8 10,J,1,J,2,J,3,J,4,机器,1,机器,2,机器,3,下界,sum,3,db,=36,*,从上例可知：优先队列式分支限界法中，,扩展结点表,PT,取得极值的叶子结点就对应的是问题的最优解；,扩展结点的过程，一开始实际类似“深度优先”。,思考：,将例,9-2,和例,9-4,改成,FIFO,式分支限界法，搜索过程有何不同？,在算法的实现上，,FIFO,式分支限界法和优先队列式分支限界法的,PT,表数据结构一样吗？,*,课后作业,采用分支限界法求解下列作业调度问题，,4,个作业,J,1,J,2,J,3,J,4,在机器,M,1,M,2,上处理的时间矩阵如图所示。求最佳的处理顺序，使得,4,个作业从开始到结束处理的时间最短。,(,要求：画出解空间的展开,),M,1,M,2,J,1,J,2,J,3,J,4,*,9.3,最小消耗,(LC),搜索法,9.3.1 LC,检索,在,FIFO,分枝限界法中，对下一个,E-,结点的选择规则相当死板，在某种意义上是盲目的。,对活结点使用一个“,有智力,”的排序函数,c,(.),来选取下一个,E-,结点往往可以加快到达一答案结点的速度。,对任意结点,x,，可用两种标准来量度：,在生成一个答案结点之前，子树,x,需要生成的,结点个数,；,在子树,x,中离,x,最近的那个答案结点到,x,的,路径长度,。,*,使用第一种度量：,图中树的根结点付出的代价是,4,。结点,(18,和,34),，,(29,和,35),以及,(30,和,38),的代价分别是,3,2,和,1,。,所有在,2,3,和,4,级上剩余结点的代价应分别大于,3,2,和,1,。以这些代价作为选择下一个,E-,结点的依据，则,E-,结点依次为,1,18,29,和,30,。另外，不得已生成的结点为,2,34,50,19,24,32,。,使用第二种度量，则,E-,结点只是由根到最近的那个答案结点路径上的那些结点。,图,9.1 4-,皇后问题,总是生成最小数目的结点,*,9.3.2 LC,方法要点,对状态空间树上的一个,答案结点,x,定义,实际代价函数,cost(,x,),。,cost(,x,),的内涵：从状态空间树根结点出发，到达一个答案结点,x,，实际需要付出的“代价”。,cost(,x,),的定义：原则上应根据具体问题加以定义。,对状态空间树,上任一结点,x,，定义,代价函数,c,(,x,),。,c,(,x,),的内涵：从状态空间树根结点出发，经过,x,结点，在,以结点,x,为根的子树上,，搜索到一个答案结点，所需要付出的代价。,定义,c,(,x,),的一般原则：,若,x,是答案结点，则：,c,(,x,) = cost(,x,),；,*,若,x,不是答案结点，但以,x,为根的子树上,至少有一个,答案结点，则：,c,(,x,) =,min,c,(,answer,) |,answer,:,x,上所有答案结点,若,x,不是答案结点，且以,x,为根的子树上也没有答案结点，则：,c,(,x,) = +,对状态空间树上结点,x,定义,估算函数,，且使满足： ,c,(,x,),。,注：与,c,(,x,),相比， 应是当前“可计算”的。,设计一个活结点表,L,，用于存放搜索过程的“活结点”。该表的数据结构可选择,有序表,或,堆,。,即要求：活结点表上的所有结点，按照它们,估算函数取值,，构成一个有序表或堆。,=h,(,x,)+,g,(,x,),*,LC,法搜索过程：,初始：把状态空间树的根结点，做为活结点表,L,的第一个结点；,重复以下两步，直到找到一个解，或,L,为空：,从,L,上选出具有最小 的结点，作为当前,E-,结点。,依次搜索当前,E-,结点的所有子结点。若子结点是答案结点，则结束；否则，把子结点加入有序表,L,。,*,9.3.3 LC,方法应用举例,15,迷问题。,问题描述：把编号为,115,的棋子，随意放在,44,格的棋盘上,(,空出一个格,),。要求：经过有限步的移动，把棋盘上棋子的“初态”，变成棋子号与棋盘号一致的目标状态。,(,注：“移动”仅限于,空格周围,棋子,),实例： 初态 目标状态,1,2,4,5,6,3,7,9,10,12,8,13,14,11,15,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,*,分析：,实际代价函数,cost(,x,):,若,x,是目标状态，则：,cost(,x,),等于从棋盘初态，经逐步移动棋子而到达目标状态,x,，,实际需要移动棋子总步数,。,代价函数,c,(,x,):,若,x,是目标状态，则：,c,(,x,) = cost(,x,),若,x,不是目标状态，但,x,所在子树上存在目标状态结点， 则：,c,(,x,) =,min,c,(,x,) |,x,：,x,子树上所有目标状态结点,若,x,不是目标状态，且,x,所在子树上也不存在任何目标状态结点，则,c,(,x,) = +,*,定义估算函数：,=,h,(,x,) +,g,(,x,),其中，,h,(,x,):,从状态空间树的根结点到,x,结点,路径长度,；,g,(,x,),：,x,状态下，,没有,达到“目标状态”的,棋子数量,。,1,2,4,5,6,3,7,9,10,12,8,13,14,11,15,1,2,4,5,6,3,7,9,10,12,8,13,14,11,15,1,2,3,4,5,6,7,9,10,12,8,13,14,11,15,1,2,4,5,6,3,7,9,10,12,8,13,14,11,15,g,1,=6,h,1,=0,1,g,2,=7,g,3,=5,g,4,=7,2,3,4,左,下,右,1,*,1,2,3,4,5,6,7,9,10,12,8,13,14,11,15,g,3,=5,3,1,1,2,3,4,5,6,7,9,10,12,8,13,14,11,15,1,2,3,4,5,6,7,9,10,12,8,13,14,11,15,1,2,3,4,5,6,12,7,9,10,8,13,14,11,15,1,2,3,5,6,7,4,9,10,12,8,13,14,11,15,1,2,3,4,5,6,7,8,9,10,12,13,14,11,15,g,5,=6,6,5,7,左,右,下,g,6,=4,g,7,=5,2,g,9,=3,g,8,=5,下,上,9,8,3,*,1,2,3,4,5,6,7,8,9,10,12,13,14,11,15,g,9,=3,9,3,1,2,3,4,5,6,7,8,9,10,12,13,14,11,15,1,2,3,4,5,6,7,8,9,10,12,15,13,14,11,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,2,3,4,5,6,8,9,10,7,12,13,14,11,15,1,2,3,4,5,6,7,8,9,10,12,13,14,11,15,10,11,左,下,g,10,=2,g,11,=3,g,12,=3,g,13,=1,g,14,=3,13,12,14,左,下,上,4,5,*,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,g,13,=1,13,5,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,g,14,=2,14,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,g,15,=0,15,6,目标状态！,左,右,15,移动棋子步数：,6,移动顺序：,3,78121115,*,LC,方法的算法之一：搜索到,一个答案结点,void LC(struct Node *root), struct Node *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) ,*,LC,方法的算法之二：搜索,最优解,void LC_option(struct Node * root), struct Node *x, *E, *L ; /L:,活结点表。,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; ,*,本章小结,分支限界法常以,广度优先,或以,最小耗费,(,LC,),优先的方式搜索问题的解空间树。,在遍历过程中，对已经扩展出的每一个结点根据,限界函数,估算,目标函数,的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。,从表,PT,中选择下一扩展结点的不同方式导致不同的分支限界法：,队列式,(FIFO),分支限界法,优先队列式,分支限界法,确定最优解中的各个分量,保存根结点到该结点的路径,构建搜索经过的树结构,*,分支限界法与回溯法的,区别,：,求解目标不同,：,回溯法,找出满足约束条件的所有解,分支限界法,找出满足条件的一个解，或某种意义下的最有解,搜索方式不同,：,回溯法,深度优先,分支限界法,广度优先或最小耗费优先,此外，在分支限界法中，每一个活结点,只有一次,机会成为扩展结点。,最小消耗,(LC),搜索法,*,