文档介绍：第六章分支限界法算法设计与分析 puterAlgorithm信息工程学院张永梅学时分配章节内容讲授课时上机课时考试第一章绪论4第二章分治与递归42第三章贪心算法42第四章动态规划42第五章回溯法42第六章分支限界法2合计2282本课程成绩由平时作业、上机实验和期末考试进行评定:考核方法及成绩评定标准平时作业:10%上机实验:30%期末考试:60%,考试形式为开卷第六章分支限界法(Branch-and-Bound)1、基本要求要求掌握分治限界法的基本思想,算法设计步骤,及常见问题的算法。要求理解分支限界法的剪枝搜索策略。2、教学内容基本思想0-1背包问题第六章分支限界法(Branch-and-Bound) 分支限界法的基本思想分支限界法与回溯法(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。回溯与分支限界是对穷举法的改进。它们每次只构造候选解的一个分量,然后评估这个部分解:如果加上剩下的分量也不可能求得一个解,就不再生成剩下的分量。回溯法和分支限界都是以构造一棵状态空间树为基础,树的节点反映了对一个部分解所做的特定的选择。 分支限界法的基本思想分支限界法与回溯法有两种生成问题状态的基本方法。它们都是从根结点开始然后生成状态空间树上的其它结点。 分支限界法的基本思想如果已生成一个结点而它的所有儿子结点还没有全部生成,则这个结点叫做活结点(Livenode)。当前正在生成其儿子结点的活结点叫E-结点(正在扩展的结点,Expandednode)。不再进一步扩展或者其儿子结点已全部生成的结点就是死结点(Deadnode)。在生成问题状态的两种方法中,都要有一张活结点表。问题状态的生成可以采用两种不同的方法:如果对一个E-结点R一旦生成了它的一个新的儿子C,就把C当作新的扩展结点,在完成对子树C(以C为根的子树)的穷尽搜索之后。将R结点重新变成E-结点,继续生成R的下一个儿子(如果存在)。这称做深度优先的问题状态生成法。在另一种状态生成方法中,一个E-结点一直保持到变成死结点为止。即在一个E-结点变成死结点之前,它一直是扩展结点。这实际上是一种宽度优先的问题状态生成法。 分支限界法的基本思想广度优先遍历(BFS)方法:从图的某一顶点V0出发,访问此顶点后,依次访问V0的各个未曾访问过的邻接点;然后分别从这些邻接点出发,广度优先遍历图,直至图中所有已被访问的顶点的邻接点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8例广度遍历:V1V2V3V4V5V6V7 分支限界法的基本思想