文档介绍：该【分支限界法公开课获奖课件赛课一等奖课件 】是由【业精于勤】上传分享，文档一共【37】页，该文档可以免费在线阅读，需要了解更多关于【分支限界法公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第九章 分支限界法
1
2
3
4
概述
图问题中的分支限界法
组合问题中的分支限界法
小结
概述
分枝限界法的设计思想
分枝限界法的时间性能
一种简单例子
---圆排列问题
分支限界法按广度优先方略搜索问题的解空间树，在搜索过程中，看待处理的结点根据限界函数估算目的函数的也许取值，从中选用使目的函数获得极值（极大或极小）的结点优先进行广度优先搜索，从而不停调整搜索方向，尽快找到问题的解。
分支限界法合用于求解最优化问题。
确定一种合理的限界函数，并根据限界函数确定目的函数的界[down, up]。
按照广度优先方略搜索问题的解空间树，在分支结点上，依次扩展该结点的所有孩子结点，分别估算这些孩子结点的目的函数的也许取值，某孩子结点的目的函数的也许取值超过目的函数的界，则将其丢弃；否则，将其加入待处理结点表（如下简称表PT）中。
依次从表PT中选用使目的函数获得极值的结点成为目前扩展结点，反复上述过程，直至找到最优解。
分支限界法的设计思想
分支限界法需要处理的关键问题
怎样确定合适的限界函数。（提醒：计算简单，减少搜索空间，不丢解）
怎样组织待处理结点表。（提醒：表PT可以采用堆的形式，也可以采用优先队列的形式存储。各有什么特点？）
怎样确定最优解的各个分量。（提醒：跳跃式处理解空树结点，必须保留搜索过程中通过的途径信息。）
回溯法从根结点出发，按照深度优先方略遍历问题的解空间树。
分支限界法按广度优先方略搜索问题的解空间树。
两者与蛮力法区别？
回溯法与分支限界法区别？
一般状况下，在问题的解向量X=(x1, x2, …, xn)中，分量xi (1≤i≤n)的取值范围为某个有限集合Si={ai1, ai2, …, airi}，因此，问题的解空间由笛卡儿积A=S1×S2×…×Sn构成，并且第1层的根结点有|S1|棵子树，则第2层共有|S1|个结点，第2层的每个结点有|S2|棵子树，则第3层共有|S1|×|S2|个结点，依此类推，第n+1层共有|S1|×|S2|×…×|Sn|个结点，他们都是叶子结点，代表问题的所有也许解。
分支限界法的时间性能
类比回溯法分析分支限界法的时间性能
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0/1背包问题的解空间树
对物品1的选择
对物品3的选择
对物品2的选择
1
2
3
4
5
7
8
11
12
14
15
3
10
6
9
例如：对于n=3的0/1背包问题解空间树
分支限界法和回溯法实际上都属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏状况下，时间复杂性肯定为指数阶。
与回溯法不一样的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，有助于实行大范围剪枝，同步，根据限界函数不停调整搜索方向，选择最有也许获得最优解的子树优先进行搜索。因此，假如选择了结点的合理扩展次序以及设计了一种好的限界函数，分支界线法可以迅速得到问题的解。
分支限界法的较高效率是以付出一定代价为基础的，其工作方式也导致了算法设计的复杂性。首先，一种更好的限界函数一般需要花费更多的时间计算对应的目的函数值，并且对于详细的问题实例，一般需要进行大量试验，才能确定一种好的限界函数；另一方面，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保留该结点到根结点的途径，或者在搜索过程中构建搜索通过的树构造，这使得算法的设计较为复杂；再次，算法要维护一种待处理结点表PT，并且需要在表PT中迅速查找获得极值的结点，等等。这都需要较大的存储空间，在最坏状况下，分支限界法需要的空间复杂性是指数阶。