算法分支限界法教学教案

《算法分支限界法教学教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章分支限界法1学习要点1.1学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（4）0-1背包问题；（8）批处理作业调度问题2分支限界法的基本思想2.1分支限界法描述采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜

2、索效率。原理按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。1.1分支限界法与回溯法求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先的方式搜索解空间树。

3、分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。1.1常见的两种分支限界法队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。搜索策略：一开始，根结点是唯一的活结点，根结点入队。从活

4、结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为相似，唯一的不同之处是队列式分支限界法不搜索以不可行结点为根的子树。优先队列式分支限界法基本思想：为了加速搜索的进程，应采用有效的方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。搜索策略：对每一活结点计算一个

5、优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，……，直到找到一个解或活结点队列为空为止。10-1背包问题1.1算法思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。templateTypepKna

6、p::Bound(inti){//计算节点所相应价值的上界Typewcleft=c-cw;//剩余容量高Typepb=cp;//价值上界//以物品单位重量价值递减序装填剩余容量while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装填剩余容量装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中，判断方法同回溯法。当前扩展结点的右儿子结点一定是可行结

7、点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列，判断方法同回溯法。当扩展到叶节点时为问题的最优值。例如：0-1背包问题，当n=3时，w={16,15,15},p={45,25,25},c=30。优先队列式分支限界法处理法则：价值大者优先。取结点的当前价值排序（按照书本P162逻辑）。{}—>{A}—>{B,C}【—>{C，D（舍去），E}】—>{E，C}【—>{C，J（舍去），K}】—>{K，C}—>{F，G}—>{G，L，M}【—>{G，M}（L，M已是叶节点）】—>{G}—>{N，O}—>{O}—>{}1.1队列式(FIFO)算法示例解

8、空间树如下图所示，1代表选择，0代表不选。分支限界法