第6章 分支限界法

得到的解 继续搜索
13
单源最短路径问题
1. 问题描述
下面以一个例子来说明单源最短路径问题：在下 图所给的有向图G中，每一边都有一个非负边权。要 求图G的从源顶点s到目标顶点t之间的最短路径。
14
单源最短路径问题
1. 问题描述
下图是用优先队列式分支限界法解有向图G的 单源最短路径问题产生的解空间树。其中，每一个结 点旁边的数字表示该结点所对应的当前路长。
// 取下一扩展结点
i++;}
// 进入下一层
}
26
装载问题
3. 算法的改进
结点的左子树表示将此集装箱装上船，右子树 表示不将此集装箱装上船。设bestw是当前最优解； ew是当前扩展结点所相应的重量；r是剩余集装箱 的重量。则当ew+rbestw时，可将其右子树剪去， 因为此时若要船装最多集装箱，就应该把此箱装 上船。
（2）回溯求解TSP也是盲目的（虽有目标函数，也 只有找到一个可行解后才有意义）
7
解空间树的动态搜索
分支限界法首先确定一个合理的限界函数，并根据限 界函数确定目标函数的界[down, up]； 然后按照广度优先策略遍历问题的解空间树，在某一 分支上，依次搜索该结点的所有孩子结点，分别估算 这些孩子结点的目标函数的可能取值（对最小化问题， 估算结点的down，对最大化问题，估算结点的up）。 如果某孩子结点的目标函数值超出目标函数的界，则 将其丢弃（从此结点生成的解不会比目前已得的更 好），否则入待处理表。
A->E->Q->M
21
单源最短路径问题
Dijakstra算法和分支限法在解决该问题的异同：
优先队列式分支限界法的搜索方式是根据活结点的优先级确 定下一个扩展结点。结点的优先级常用一个与该结点有关的 数值p来表示。最大优先队列规定p值较大的结点点的优先级 较高。在算法实现时通常用一个最大堆来实现最大优先队列， 体现最大效益优先的原则。类似地，最小优先队列规定p值 较小的结点的优先级较高。在算法实现时，常用一个最小堆 来实现，体现最小优先的原则。采用优先队列式分支定界算 法解决具体问题时，应根据问题的特点选用最大优先或最小 优先队列，确定各个结点点的p值。

通常采用最大堆或最小堆来实现优先队列式分支限界法求解问 题。
可以用如下方法求得最优解中的分量：1）对每个扩展结点保存
该结点到根结点的路径；2）在搜索过程中构建搜索经过的树结
构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最
优202解0年中7月的19日各个分量。
21
提纲
一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题
E 使总的路程最短。
23
F GH I J K 43 42 32
L MN O P Q
2020年7月19日
17
分支限界法解旅行售货员问题
FIFO队列：
活结点队列： {{F{CED}G,{,GH,FD{,E{IH,,J{,GHIJEK{F,IJK,,}KIHG,J},KJ},}KI,K}}}}
B
2
3
4
1 30 2
2020年7月19日
24
2.2单源最短路径问题算法思想
用一最小堆来存储活结点表。其优先级是结点所对应的 当前路长。
算法从图G的源顶点s和空优先队列开始。结点s被扩展 后，它的儿子结点被依次插入堆中。此后，算法从堆中 取出具有最小当前路长的结点作为当前扩展结点，并依 次检查与当前扩展结点相邻的所有顶点。如果从当前扩 展结点i到顶点j有边可达，且从源出发，途经顶点i再到 顶点j的所相应的路径的长度小于当前最优路径长度，则 将该顶点作为活结点插入到活结点优先队列中。这个结 点的扩展过程一直继续到活结点优先队列为空时为止。
[G] N, 0 =>N(25), O(0)
不搜索以不可行结点为根的子树
优先队列式分支限法：
[A] B, C => B(45), C(0)

11
2014-8-27
西安邮电学院
12
2014-8-27
西安邮电学院
13
2014-8-27
西安邮电学院
14
2014-8-27
西安邮电学院
15
2014-8-27
西安邮电学院
16
2014-8-27
西安邮电学院
17
2014-8-27
西安邮电学院
18
2014-8-27
西安邮电学院Leabharlann 192014-8-27
两种方法的搜索方式比较：
回溯法：深度优先
分支限界法：广度优先或最小费用优先
2014-8-27
西安邮电学院
2
分支限界法的搜索策略：
在扩展节点处，先生成其所有的儿子节点（分支的过 程），在从当前的活节点表中选择下一个扩展节点。为了有 效选择下一个扩展节点，以加速搜索进程，在每一个活节点 处，计算一个函数值（限界的过程），并根据这些已计算出 的函数值，从当前活节点表中选择一个最有利的活节点作为 扩展节点，使得搜索向解空间树上有最优解的分支进行，以 尽快找出一个最优解。
第六章 分支限界法 Branch and Bound
2014-8-27
西安邮电学院
1
分支限界法也是一种在问题解空间上进行尝试搜索算法。 它类似于回溯法，但分支限界法和回溯法的求解目标不同。 回溯法的求解目标是找出满足约束条件的所有解，而分支限 界法的求解目标则是找出满足约束条件的一个解，或者是在 满足约束条件的解中找出使得某一目标函数值达到某种意义 下的最优解。
优先队列： （1）最大优先队列：数值大则优先级高 实现方式：最大堆 （2）最小优先队列：数值小则优先级高 实现方式：最小堆

Ki ≤ K2i 或 Ki ≤ K2i+1 Ki ≥ K2i+1 Ki ≥ K2i i=1,2,…,n/2
单源最短路经
• 有向图G中，每一边都有一个非负边权。求 图G的从源顶点s到目标顶点t之间的最短路 径。
2
9
12
14>8 9>8
5>3
12>4
10>7
0
3
4
7
8>7
8
4
5
6>5
6
• 剪枝：结点间的控制关系。从s出发，经过两条不同路径 到达同一顶点，这两条路径相应于解空间树的2个不同的 结点A和B，如果结点A所相应的路长小于结点B所相应的路 长，则可以将结点B为根的子树剪去，称结点A控制了结点 B。 • 优先队列中结点的优先级：结点所对应的当前路长。
• 在使用分支限界法解具体问题时，可以采 用下面两种典型方式实现活结点表
– 队列式分支限界（先进先出） – 优先队列式分支限界
1 1
2
3
4
2
3
4
队列式： 活结点表L=(2,3,4)
优先队列式： 活结点表L=(2,3,4按限界函数值确定 优先级)，即哪个分支能够花最小 代价 E.length c[E.i][j] dist[j]是否更新？
j
i
j
最大团问题
• 给定一个无向图G=(V,E)。如果U包含于V，且对任 意u,v属于U有(u,v)属于E，则称U是G的一个完全子 图。G的完全子图U是G的一个团当且仅当U不包含 在G的更大的完全子图中。G的最大团是指G中所 含顶点数最多的团。
• （当前扩展结点）顶点数上界=已确定的顶点数+未确定的顶点 数的上界