资源描述：
《第9章 分支限界法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第9章分支限界法学习要点:理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式分支限界法通过应用范例学习分支限界算法设计策略9.1.1分支限界法分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法常以广度优先或以最小耗费(LC)优先的方式搜索问题的解空间树。在遍历过程中，对已经扩展出的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。适用于求解
2、最优化问题。9.1概述9.1.2分支限界法的设计思想首先，确定一个合理的限界函数，并根据限界函数确定问题的目标函数的界[down,up]；然后，按照广度优先策略遍历问题的解空间树：当搜索到达一个扩展结点时，一次性扩展它的所有孩子，估算每一个孩子结点的目标函数的上(下)界值(又称为耗费函数值)；将那些满足约束条件且耗费函数值不超过目标函数的界的孩子，插入活动结点表PT中，再从PT表中取耗费函数值极大(小)的下一结点同样扩展；直到找到所需的解或PT表为空为止。其耗费函数值是极值(极大或极小)，则该叶子
3、结点对应的解就是问题的最优解；否则，调整问题的目标函数的界为该叶子结点的耗费函数值，然后丢弃PT表中超出目标函数界的结点，再次选取结点继续扩展。对于PT中的叶子结点例9-1：0/1背包问题。实例：假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124怎样确定“限界函数”？又如何求得目标函数的界呢？分析：问题的解可表示
4、为n元向量{x1,x2,...xn},xi{0,1}，则可用排序树表示解空间,在树中做广度优先搜索。约束条件:目标函数:下界Vdb=40(1,0,0,0)；上界Vub=0+(W-0)×(v1/w1)=0+(10-0)×10=100；上限界函数：(式9.1)目标函数的界：[40,100]11111100000001124891011121314157653分支限界法求解0/1背包问题：×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11w=4,v=40ub=70w
5、=9,v=65ub=69w=4,v=40ub=64w=12w=9,v=65ub=6523456789×1PT={2,3}无效解PT={5,3}PT={6,7,3}无效解x1=1x1=0x2=1x2=0x3=1x3=0x4=1x4=0PT={9,7,3}V=65X=(1,0,1,0)目标函数范围：[40,100]wi=(4,7,5,3)vi=(40,42,25,12)vi/wi=(10,6,5,4)分支限界法的一般过程：1．根据限界函数确定目标函数的界[down,up]；2．将待处理结点表PT初始化
6、为空；3．对根结点的每个孩子结点x执行下列操作3.1估算结点x的目标函数值value;3.2若(value>=down)，则将结点x加入表PT中；4．循环直到某个叶子结点的目标函数值在表PT中最大4.1i=表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
7、是叶子结点但结点x的value值在表PT中不是最大)，则令down=value，并且将表PT中所有小于value的结点删除；常见的两种分支限界法：从表PT中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先。最小优先队列：使用最小堆，体现最小费用优先。例如，上例0/1背包问题，采用最大优
8、先队列式分支限界法。应用分支限界法的其他关键问题：如何确定最优解中的各个分量？对每个扩展结点保存根结点到该结点的路径；例如，0/1背包问题。将部分解(x1,…,xi)和该部分解的目标函数的上界值都存储在待处理结点表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
