《分支限界法sch3》由会员分享，可在线阅读，更多相关《分支限界法sch3（25页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 Design and Analysis of Algorithms算法设计与分析算法设计与分析 Design and Analysis of AlgorithmsDesign and Analysis of Algorithms主讲人主讲人徐徐 云云FallFall 20102010, , USTCUSTC第第3 3章章( (补充补充) )分支限界法分支限界法 3.1 3.1 方法概述方法概述 3.2 3.2 8 8谜问题谜问题 3.3 3.3 装载问题装载问题2010-10-13算法设计与分析33.1 方法概述?基本思想?与回溯法的区别?求解步骤?两种常见的活结点扩充方式?示
2、例1和示例22010-10-13算法设计与分析4基本思想?在解空间树中, 以广度优先BFS或最佳优先方式 搜索最优解, 利用部分解的最优信息, 裁剪那些 不能得到最优解的子树以提高搜索效率。?搜索策略是：在扩展结点处，先生成其所有的 儿子结点（分支），然后再从当前的活结点表 中选择下一个扩展结点。为了有效地选择下一 扩展结点，以加速搜索的进程，在每一活结点 处，计算一个函数值（优先值），并根据这些 已计算出的函数值，从当前活结点表中选择一 个最有利的结点作为扩展结点，使搜索朝着解 空间树上有最优解的分支推进，以便尽快地找 出一个最优解。2010-10-13算法设计与分析5与回溯法的区别?求解目
3、标不同 ：一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所 有解，而分支限界法的求解目标则是尽快地找出满足约束条件的一 个解；?搜索方法不同：回溯算法使用深度优先方法搜索，而分支限界一般用宽度优先或最佳优先方法来搜索；?对扩展结点的扩展方式不同：分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点 一旦成为扩展结点，就一次性产生其所有儿子结点；?存储空间的要求不同：分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大；2010-10-13算法设计与分析6求解步骤定义解空间(对解编码); 确定解空间的树结构; 按BFS等方式搜索:a.每个活结点仅有一次
4、机会变成扩展结点； b.由扩展结点生成一步可达的新结点； c.在新结点中, 删除不可能导出最优解的结点；/限界策略 d.将余下的新结点加入活动表(队列)中； e.从活动表中选择结点再扩展；/分支策略 f.直至活动表为空；2010-10-13算法设计与分析7两种常见的活结点扩充方式?先进先出队列（F I F O） : 从活结点表中取出 结点的顺序与加入结点的顺序相同，因此活结 点表的性质与队列相同；?优先队列（耗费用小根堆,受益用大根堆）: 每 个结点都有一个对应的耗费或收益。 -如果查找一个具有最小耗费的解，则活结点表可用小 根堆来建立，下一个扩展结点就是具有最小耗费的活 结点； -如果希望搜
5、索一个具有最大收益的解，则可用大根堆 来构造活结点表，下一个扩展结点是具有最大收益的 活结点。2010-10-13算法设计与分析8示例1（1）?示例1（FIFO队列分支限界法）?问题：0-1背包问题:物品数n=3, 重量w=(20,15,15), 价值v=(40,25,25),背包容量c=30, 试装入价值和最 大的物品?求解：解空间:(0,0,0), (0,0,1), , (1,1,1) 解空间树:DBHAIEJKFCLMGNO111111100000002010-10-13算法设计与分析9示例1（2）BFS搜索（FIFO队列）扩展结点活结点队列(可行结点) 可行解(叶结点) 解值 A B,
6、C BC B D,E(D死结点) CE C F,G EFG E J,K(J死结点) FG K 40 F L,M G L,M 50,25 G N,O N,O 25,0 最优解为L, 即(0,1,1); 解值为50 DBHAIEJKFCLMGN O111111100000002010-10-13算法设计与分析10示例2（1）?示例2（优先队列分支限界法）?问题：0-1背包问题:物品数n=3, 重量w=(20,15,15), 价值v=(40,25,25),背包容量c=30, 试装入价值和最 大的物品?求解：解空间:(0,0,0), (0,0,1), , (1,1,1) 解空间树:DBHAIEJKFC
7、LMGNO111111100000002010-10-13算法设计与分析11示例2（2）?BFS搜索（优先队列：按价值率优先） 扩展结点活结点队列(可行结点) 可行解(叶结点) 解值 A B,C B D,E(D死结点)E J,K(J死结点) K 40 C F,GF L,M L 50(最优) G N,O BC ECFGCGDBHAIEJKFCLMGN O11111110000000第第3 3章章( (补充补充) )分枝限界法分枝限界法 3.1 3.1 方法概述方法概述 3.2 3.2 8 8谜问题谜问题 3.3 3.3 装载问题装载问题2010-10-13算法设计与分析133.2 8谜问题?问题
8、定义?代价函数?代价最小优先搜索2010-10-13算法设计与分析14问题定义和代价函数1.问题定义2.代价函数f(x) 设f(x)为经x到解的代价， x是当前结点: (1)如果x是死结点或x的子树不含解，使 f(x)= (2)如果x是活结点: f(x)=g(x)+h(x) g(x):从根到x的代价, h(x): 由x产生解的代价估计 这里我们取： h(x)=i=18(|xi1-xi0|+|yi1-yi0|)1 5 2 4 763 81 2 3 46 75 82010-10-13算法设计与分析15代价最小优先搜索3.代价最小优先搜索：结点旁的圆圈内的数字为f(x)1 5 24763851 5
9、24376851 5 24763871 5 24376871 2 34765851 2 34675851 5 24763851 542763871 5 24763871 5 24763871 5 24376871 5 23764871243765851 243765851 24376587124376587第第3 3章章( (补充补充) )分枝限界法分枝限界法 3.1 3.1 方法概述方法概述 3.2 3.2 8 8谜问题谜问题 3.3 3.3 装载问题装载问题2010-10-13算法设计与分析173.3 装载问题?问题定义?解空间树?FIFO队列分支限界2010-10-13算法设计与分析18
10、问题定义（1）?有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮 船，其中集装箱i的重量为wi，且?装载问题要求确定是否有一个合理的装载方案可将这n 个集装箱装上这2艘轮船。?可以证明：如果一个给定的装载问题有解，则采用下面 的策略可得到最优装载方案：首先，将第1艘轮船尽可能装满；将剩余的集装箱装上第2艘轮船。21 1ccwnii+ =2010-10-13算法设计与分析19问题定义（1）=nixwcxtsxwniciiiii,.,2 , 11 , 00w. .max,.,2 , 1w,1n1iin1ii问题的形式化定义：上轮船。尽可能重的集装箱装况下，装载体积不受限制的情在）（集装箱重量
11、为轮船载重为义为：艘轮船的装载问题可定第因此，2010-10-13算法设计与分析20解空间树?解表示和解空间: (x1,x2,xn)| xi0,1, i=1n?解空间：123101010i层次12n+1x1x22010-10-13算法设计与分析21FIFO分支限界（1）?全局变量的设计x1.n保存搜索到的解； bestw保存当前最优解值；?结点变量的设计Typedef struct Treenode float wt; /搜索到该结点时的载重量 int level; /结点所处的层次 struct Treenode *parent; /指向父结点的指针 *qnode;2010-10-13算法设
12、计与分析22FIFO分支限界（2）?算法MaxLoading(w, c, n) /返回最优值bestw和解向量x1.n iniqueue(Q); /建立空队列Q，Q中元素为qnode类型 p=new qnode; /生成一个qnode结点，装入结点 p-wt=0; p-level=1; p-parent=NIL; enqueue(Q, p); /入队 float bestw=0; qnode bestp=p;2010-10-13算法设计与分析23FIFO分支限界（3）while( !empty(Q) ) do /BFS遍历 p=dequeue(Q); /出队，p结点成为扩展结点 /扩展左孩子结
13、点 if p-wt+wp-levelwt=p-wt+wp-level; q-level=p-level+1; q-parent=p; enqueue(Q, q); if( bestwwt ) bestw=q-wt; bestp=q; /扩展右孩子结点 q=new qnode; q-wt=p-wt; q-level=p-level+1; q-parent=p; enqueue(Q, q); 2010-10-13算法设计与分析24FIFO分支限界（4）/构造解 for i=1 to n do xi=0; p=bestp; while( p!=NIL ) do tempw=p-wt; p=p-parent; if p-wt != tempw then xp-level=1; /endEnd of SCh3End of SCh3End of SCh3
