第5章(5.5分支限界算法)备课讲稿

第5章(5.5分支限界算法)根据节点的扩展方式不同，分支限界算法常分为2种支限界算法；1）FIFO（先进先出）分支限界算法

开始，根结点是唯一的活结点，根结点入队； 从活结点队中取出根结点后，作为当前扩展结点。 对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。2）优先队列式分支限界算法

开始，根结点是唯一的活结点，根结点入队； 从活结点队中取出根结点后，作为当前扩展结点。 对当前扩展结点，先从左到右地产生它的所有儿子节点；为了加速搜索的进程，应采用有效地方式选择结点进行扩展。 优先队列式搜索，对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。还有1种利用栈实现的分支限界算法！LIFO(后进先出)分支限界算法 一开始，根结点入栈。 从栈中弹出一个结点为当前扩展结点。 对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈，再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，……，直到找到一个解或栈为空为止。概括起来，分支限界算法与回溯算法异同：相同点：都属于搜索算法，需要在问题的解空间中搜索问题的解；解空间的组织一般是都是树；不同点：1）求解目标不同：

回溯法求解目标是找出解空间树中满足约束条件所有解；

分支限界法求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2）搜索方式的不同：

回溯法以深度优先的方式搜索解空间树；

分支限界法则以广度优先的方式搜索解空间树。5.5.20－1背包问题1、问题提出已知n个物体重量为：w1、w2… n个物体价值为：p1、p2… 背包载重为：M

两类背包问题： ①普通背包问题（贪心算法）

物体i可以部分的装入背包，若物体i的一部分xi装入背包，则装入的重量为wi*xi，装入的价值为pi*xi； ②0－1背包问题（回溯算法、分支限界算法）

每一件物体不能分割，要么全部放入，要么全部不放入，称为0－1背包问题；2、基本思路

①确定问题的解空间（子集树）；19310613245781112141511100000001111②以广度优先的方式搜索整个解空间；3、举例 背包载重：M＝10 物品重量：w1＝6、w2＝5、w3＝5 物品价值：p1＝42、p2＝25、p3＝30

首先，定义问题的解空间；

然后，广度优先搜索解空间；193106132457811121415111000000011111）FIFO（先进先出）分支限界法从根结点1开始；用一个队列表示活动结点；初始时活动结点队列为空，结点1为当前扩展结点；92结点1的孩子结点2、9为可行结点，故舍弃当前结点1，将2、9加入活动结点队列；1先进先出原则，2作为当前扩展结点，其孩子结点3、6；由于结点3是不可行结点舍弃；69先进先出原则，9作为当前扩展结点，其孩子结点10、13;结点10、13是可行结点；13106先进先出原则，6作为当前扩展结点，其孩子结点7、8;结点7是不可行结点舍弃；81310先进先出原则，10作为当前扩展结点，其孩子结点11、12;结点11、12是可行结点；1211813先进先出原则，13作为当前扩展结点，其孩子结点14、15;结点14、15是可行结点；151412118先进先出原则，8是可行的叶子结点，最优值为42；15141211先进先出原则，11是可行的叶子结点，最优值为55；151412先进先出原则，12是可行的叶子结点，25<最优值55；1514先进先出原则，14是可行的叶子结点，30<最优值55；15先进先出原则，15是可行的叶子结点，0<最优值55；最优值为55；2）优先队列分支限界法(当前价值最大，优先级最高)从根结点1开始；用一个最大堆表示活动结点的优先队列;初始时活动结点堆为空，结点1为当前扩展结点；结点1的孩子结点2、9为可行结点，故舍弃当前结点1，将2、9加入堆中；结点2的获得当前价值42>结点9的0；结点2作为堆中最大元素，作为当前扩展结点，其孩子结点3、6；由于结点3是不可行结点舍弃；结点6当前价值>结点9,结点6作为堆顶；12969结点6作为堆中最大元素，作为当前扩展结点，其孩子结点7、8；由于结点7是不可行结点舍弃；结点8当前价值>结点9，结点8作为堆顶；89结点8是叶子结点，是一个可行解最优值为42；9结点9作为堆中最大元素，作为当前扩展结点，其孩子结点10、13；结点10当前价值>结点13，结点10作为堆顶；1013结点10作为堆中最大元素，作为当前扩展结点，其孩子结点11、12；结点11当前价值>结点12、13，结点11作为堆顶；111312结点11作为堆中最大元素，且为叶子结点是一个可行解，最优值为55>42；1312结点12作为堆中最大元素，且为叶子结点是一个可行解，最优值为25<55；结点13作为堆中最大元素，作为当前扩展结点，其孩子结点14、15；结点14当前价值>结点15，结点14作为堆顶；131514结点14作为堆中最大元素，且为叶子结点是一个可行解，最优值为30<55；15结点15作为堆中最大元素，且为叶子结点是一个可行解，最优值为0<55；3、算法描述

2）优先队列分支限界法doubleknaspack(doublep[],doublew[],doublec){doublecw=0;//当前重量doublecp=0;//当前价值doublebestp=0;//当前最优装载价值

backtrack(1);

//回溯搜索解空间returnbestp;}doublebacktrack(inti){while(i<n)

{//非叶结点,检查当前扩展结点的左儿子结点if(cw+w[i]<=c)//左儿子结点为可行结点if(cp+p[i]>bestp){bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}//左儿子结点加入活动结点堆中up=Bound(i+1);

//上界函数，检查当前扩展结点的右儿子结点if(up>=bestp)

//右子树可能含最优解AddLiveNode(up,cp,cw,false,i+1);//右儿子结点加入活动结点堆中heapnodenode=heap.removemax();//从堆中取下一个扩展结点cw＝node.weght;cp=fit;up=node.upperprofit;

}for(intj=n;j>0;j--)//到达叶子结点，构造当前最优解{bestp[j]=node->Lchild;node=node->parent；returncp;}}doublebound(inti)

//计算上界函数{//计算当前价值与剩余价值和doublecleft=c-cw;//剩余容量doubleb=cp;//当前物品价值

//剩余物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft=cleft-w[i];b=b+p[i];i++;}//w[i]>cleft跳出循环，物品部分装入背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;

//当前物品价值与剩余物品价值之和}补充：例：有两艘船，n个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi是货箱i的重量,且w1+w2+……+wn≤c1+c2。我们希望确定是否有一种可将所有n个货箱全部装船的方法。若有的话，找出该方法。问题分析：

虽然是关于两艘船的问题，其实只讨论一艘船的最大装载问题即可。 因为当第一艘船的最大转载为bestw时，若w1+w2+……+wn-bestw<=c2,则可以确定是一种解，否则问题无解。这样问题就转化为第一艘船的最大转载问题。1）假设n＝3，其解空间如下：2）按广度优先方式搜索其解空间（同：0－1背包）5.5.3哈密顿回路（旅行售货员问题）1、问题提出 旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。例：下图的一条哈密顿回路16345278213456782、分支限界法解哈密顿回路思路 ①定义问题的解空间 有n个顶点，所以他的解空间树是一颗高为n的排列树；简单例子：13452②以广度优先的方式搜索整个解空间；253467231345278910111213151418191716X[1]=1234X[2]=23454X[3]=35X[4]=45543……6520X[5]=52143222353242543……x[1]表示哈密顿回路的第1个顶点1）队列式(FIFO)分支限界法从根结点1开始；用一个队列表示活动结点；初始时活动结点队列为空，结点1为当前扩展结点；65432结点1的孩子结点2、3、4、5、6是可行结点,加入队列；1先进先出原则，2作为当前扩展结点，其孩子结点7、8、9、10是可行结点,加入队列；109876543…………2）优先队列分支限界法从根结点1开始；用一个最小堆表示活动结点的优先队列;初始时活动结点堆为空，结点1为当前扩展结点；结点1的孩子结点2、3、4、5、6为可行结点，当前费用均为0；选结点2作为堆中最大元素，作为当前扩展结点，其孩子7、8、9、10；当前费用最小的为结点7142563485637109……