2021年六章分支限界法.ppt

学时分配
章 节
内　容
讲授课时
上机课时
考试
第一章
绪论
4
第二章
分治与递归
4
2
第三章
贪心算法
4
2
第四章
动态规划
4
2
第五章
回溯法
4
2
第六章
分支限界法
2
合　计
22
8
2
六章分支限界法
2021/1/16
1
本课程成绩由平时作业、上机实验和期末考试进行评定：
考核方法及成绩评定标准
平时作业：10%
上机实验：30%
期末考试：60%，考试形式为开卷
六章分支限界法
2021/1/16
2
第六章 分支限界法（Branch-and-Bound）
1、基本要求
要求掌握分治限界法的基本思想，算法设计步骤，及常见问题的算法。
要求理解分支限界法的剪枝搜索策略。
六章分支限界法
2021/1/16
3
2、教学内容
基本思想
0-1背包问题
第六章 分支限界法（Branch-and-Bound）
六章分支限界法
2021/1/16
4
分支限界法的基本思想
分支限界法与回溯法
（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
六章分支限界法
2021/1/16
5
回溯与分支限界是对穷举法的改进。
它们每次只构造候选解的一个分量，然后评估这个部分解：
如果加上剩下的分量也不可能求得一个解，就不再生成剩下的分量。
回溯法和分支限界都是以构造一棵状态空间树为基础，树的节点反映了对一个部分解所做的特定的选择。
分支限界法的基本思想
分支限界法与回溯法
六章分支限界法
2021/1/16
6
有两种生成问题状态的基本方法。它们都是从根结点开始然后生成状态空间树上的其它结点。
分支限界法的基本思想
如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点（Live node）。当前正在生成其儿子结点的活结点叫E-结点（正在扩展的结点,Expanded node）。不再进一步扩展或者其儿子结点已全部生成的结点就是死结点（Dead node）。
六章分支限界法
2021/1/16
7
在生成问题状态的两种方法中，都要有一张活结点表。问题状态的生成可以采用两种不同的方法：
如果对一个E-结点R一旦生成了它的一个新的儿子C，就把C当作新的扩展结点，在完成对子树C（以C为根的子树）的穷尽搜索之后。将R结点重新变成 E-结点，继续生成R的下一个儿子（如果存在）。这称做深度优先的问题状态生成法。
在另一种状态生成方法中，一个E-结点一直保持到变成死结点为止。即在一个E-结点变成死结点之前，它一直是扩展结点。这实际上是一种宽度优先的问题状态生成法。
分支限界法的基本思想
六章分支限界法
2021/1/16
8
广度优先遍历(BFS)
方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。
V1
V2
V4
V5
V3
V7
V6
V8
例
广度遍历：V1 V2 V3  V4 V5 V6 V7 V8
分支限界法的基本思想
六章分支限界法
2021/1/16
9
在这两种方法中，为了避免生成那些不可能产生最佳解（或所需解）的问题状态，将用限界函数去杀死那些实际上不可能产生所需解的活结点，以减少问题的计算工作量。
这样做要非常小心，以使得在处理结束时至少能生成一个答案结点；如果这个问题要求找出全部解，则要能生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法（backtracking）。
E-结点一直保持到死为止的状态生成方法导致分枝-限界方法（branch-and-bound）。
分支限界法的基本思想
六章分支限界法
2021/1/16
10