资源描述：
《13 分支限界.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、分支限界(Branchandbound)基于广度优先搜索的一种穷举算法尽可能的利用剪支技术引言(Introduction)与回溯法一样，分支限界是搜索一个解空间，而这个解空间通常组织成一棵树。常见的树结构为子集树和排列树。回溯以深度优先搜索一棵树，而分支限界常常以广度优先或最小耗费优先的方法搜索这棵树。解空间树.分支限界法常用于解最优化问题.确定所求问题的上下界在每个节点使用限界函数来屏蔽节点或是扩展节点.然后,使用目前为止最好的解来帮助剪枝,直到所有顶点被遍历或是被剪掉.2Ideas分支限界法也可以说是对回溯法的一个改进.假如我们在考虑一
2、个最小化问题时.我们的想法是使所有的可能目标函数值必须维持在上界(目前为止最好的解的目标函数值)与下界之间.如果在某一数量的决策之后（转移操作），我们到达一个节点，在这个节点上我们得到的下界大于或等于上界，那么就没有必要在扩展这个节点既不需在延伸这个分支。对于最大化问题规则正好相反：一旦上界小于或等于先前确定的下界，那么就剪掉这个枝。3首先，分支限界是对最优化问题可行解进行剪枝的一个方法。将搜索集中在有希望得到解的分支上。也就是说，在基于上下界和可以得到最优解的基础上,扩展分支,理由是发展这样的分支可以得到更好的上下界，从而可以剪去更多的分
3、支总之，不要单纯以DFS或BFS来进行搜索，而要结合起来进行搜索.4分之限界需要的步骤如下:1.对所求的问题定义一个解空间。这个解空间至少包含这个问题的最优解。2.对解空间进行组织，以便能更好的搜索。比较常见组织方式有图或是一棵树。3.以广度优先搜索的方式搜索解空间，使用限界函数来避免那些不能得到解的子空间5分支限界是有系统的搜索一个解空间的另一个方法。首先在扩展节点的扩展方法上，它不同于回溯。每个活节点变成扩展节点只有一次。当一个节点变成扩展节点时，我们展开从它可到达的所有节点。其中那些不能得到可行解的节点去掉（成为死节点）,把剩下来的节
4、点加到活节点的表中，然后，从这个表中选一个节点作为下一个扩展节点。6从活节点的表中选一个节点并扩展它。这个扩展操作持续到找到解或这个表为空为止。有两种常用的方法来选择下一个扩展节点：1)先进先出(FIFO)这个方法是按节点放进表中的次序从活节点表中选择节点。这个活节点表可被看作一个队列。使用广度优先来搜索这个棵树7注意分支限界的FIFO不同于广度优先的FIFO在于它不搜索那些不可行的节点。2)最小花费,最大收益用一个优先队列代替一个FIFO队列。这个方法与每个节点的花费或收益相关。如果我们搜索最小花费的解时，那么活节点表就用一个最小堆来表示
5、。下一个活节点是花费最少的节点。如果我们要得到最大收益的解时，活节点表可用一个最大堆来表示。下一个扩展节点为最大收益的节点。8解空间树(Solutionspacetree)x2x1x3Success扩展节点死节点活节点使用分支限界至少需要注意以下4点:怎么样计算上界(极大值问题)怎样计算下界(极小值问题)怎样为下一个分支操作选择一个节点.怎样扩展一棵搜索树(BFS,DFS,...)充分利用限界函数和约束函数来剪去无效的枝并把搜索集中在可以得到解的分支上.10通常,对极大值问题,我们对扩展节点i计算上界B(i).如果目前保存的最大目标值不比B
6、(i)小,那么进行剪枝，否则继续.iB(i)从根节点R通过i到叶子L的任一决策序列的目标函数值不能比B(i)大,所以如果B(i)≤bestc,那么它表明搜索扩展节点i不会成功,因此对扩展节点i进行剪枝..RL11通常,极小值问题,我们对扩展节点i计算下界B(i).如果目前保存的最大目标函数值不比B(i)大,那么进行剪枝，否则继续.iB(i)从根节点R到叶子L通过i的任一决策序列的目标函数值不能比B(i)小,所以如果B(i)≥bestc,那么它表明搜索扩展节点i不会成功,因此对扩展节点i进行剪枝.RL12子集树(Subtree)13排列树(P
7、ermutationtree)142.装载问题(ContainerLoadingproblem)问题描述有n个集装箱要装上船，集装箱i的重量为wi。船的最大负载为W。装载问题是在保证不沉船的条件下,在船上装尽可能多的集装箱。解空间假设用向量(x1,x2,…,xn)表示解,这里xi∈{0,1},xi=1表示集装箱i被装到船上,xi=0表示集装箱i没有被装到船上.15装载问题通常可以如下描述:解空间树子树有个2n叶子在第j层,解空间的成员由xj划分.16约束函数用cw(i)当前扩展节点的重量,即那么约束函数为:剪枝如果那么第i-1层扩展节点的1
8、分支节点不放入活节点表。17基于约束函数的FIFO(FIFOusingconstraintfunction)FIFOMaxLoading(w,W,n)1i←12Enqueue(Q
