w=[16, 15, 15]，p=[45, 25, 25]，c=30
1
A E
0
1
1
B
0 1
0
0 1
1
C
0 1
0
D
F
G
0
H
I
J
K
L
M
N
O
当前活结点队列的队首结点F成为下一个扩展结点。它的2个儿子结点L和M均为叶结点。 L表示获得价值为50的可行解；M表示获得价值为25的可行解。 G是最后的一个扩展结点，其儿子结点N和O均为可行叶结点。最后，活结点队列已空， 算法终止。
算法搜索得到最优值为50。
w=[16, 15, 15]，p=[45, 25, 25]，c=30
1 1 1
A
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
I
J
K
L
M
N
O
优先队列式分支限界法也是从根结点A开始搜索解空间树的。
用一个极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结
点所拥有的价值。
1 1 1
A
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
I
J
K
L
M
N
O
此时，堆中仅剩下一个活结点C，它成为当前扩展结点。它的2个儿子结点F和 G均为可行结点，因此被插入到当前堆中。 结点F的价值为25，是堆中最大元素，成为下一个扩展结点。
w=[16, 15, 15]，p=[45, 25, 25]，c=30
w=[16, 15, 15]，p=[45, 25, 25]，c=30
1 1 1
A
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
I
J
K
L
M
N
O
由于结点B的价值大于结点C的价值，所以结点B是堆中最大元素，从而成为
下一个扩展结点。
扩展结点B得到结点D和E。D不是可行结点，被舍去。E是可行结点被加入到 堆中。E的价值为45，成为当前堆中最大元素，从而成为下一个扩展结点。
用队列式分支限界法解此问题时，用一个队列来存储活结点表。 算法从根结点A开始。初始时活结点队列为空，结点A是当前扩展结点。结
点A的2个儿子结点B和C均为可行结点，所以将这2个儿子结点按从左到右
的顺序加入活结点队列，并且舍弃当前扩展结点A。
w=[16, 15, 15]，p=[45, 25, 25]，c=30
关联的(a1,a11),(a1,a12),…,(a1,a1m),(a2,a21),(a2,a22),…,
(a2,a2m)，……，(ak,ak1),(ak,ak2),…,(ak,akm)。依次类推，直到所有的边
被检查，即所有顶点均被访问为止。
图的广度优先遍历
广度优先搜索过程
广度优先生成树
广度优先遍历序列：ABCDEFGHI
w=[16, 15, 15]，p=[45, 25, 25]，c=30
1 1 1
A
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
I
J
K
L
M
N
O
扩展结点E得到2个叶结点J和K。J是不可行结点，被舍弃。K是一个可行叶
结点，表示所求问题的一个可行解，其价值为45。
此时，堆中仅剩下一个活结点C。
w=[16, 15, 15]，p=[45, 25, 25]，c=30
两个重要机制：产生分支（解空间树）
产生一个界限，能够终止许多分支（剪枝）
分支限界法的基本思想
分支限界法的适用范围：
分支限界法类似于回溯法，有一些问题其实无论用回溯法还是分支限界法都 可以得到很好的解决，但是另外一些则不然。 下表列出了回溯法和分支限界法的一些区别：
方法 对解空间树的 存储结点的常用 搜索方式 数据结构 结点存储特性 常用应用
w=[16, 15, 15]，p=[45, 25, 25]，c=30
1 1 1
A
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
N
O
初始时堆为空，扩展结点A得到它的2个儿子结点B和C。 这2个结点均为可行结点，因此被加入到堆中，结点A被舍弃。结点B获得的当
前价值是45，而结点C的当前价值为0。
1 1 1
A
E
0
1
B
0 1
0 0 1
C
0 1
0
D
F
G
0
H
I
B
J
C E
K
L
M
N
O
活结点队列：
依先进先出原则，下一个扩展结点是活结点队列的队首结点B。扩展结点 B得到其儿子结点D和E。 由于D是不可行结点，被舍去。
E是可行结点，被加入活结点队列。
w=[16, 15, 15]，p=[45, 25, 25]，c=30
分支限界法的基本思想
算法实现时，通常用极大（小）堆来实现最大（小）优先队列，提取堆中下一
个结点为当前扩展结点，体现最大（小）费用优先的原则。
极大堆满足一个节点必定不小于其子节点，极小堆正好相反。
极大堆中最大的元素必定是其根节点，堆排序算法正是根据这个特性而产生
的：对一个序列，将其构造为极大堆，然后将根节点（数组首元素）和数组 的尾元素交换，之后对除了尾元素之外的序列继续以上过程，直到排序完成。
1 1 1
A
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
I
J
K
L
M
N
O
结点F的2个儿子结点L和M均为叶结点。叶结点L相应于价值为50的可行解。 叶结点M相应于价值为25的可行解。叶结点L所相应的解成为当前最优解。
w=[16, 15, 15]，p=[45, 25, 25]，c=30
1 1 1
A
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点 中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入 活结点表中。 从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程 这个过程一直持续到找到所求的解或活结点表为空时为止。 活结点表：具有先进先出的性质，是队列。
回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以
最小耗费优先的方式搜索解空间树。
分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分
支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择
下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值 （限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最 有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进， 以便尽快地找出一个最优解。
0 1
B
0 1
0
C
0 1
0
D
E
0
1
F
G
0
H
I
J
K
L
M
N
O
最后，结点G成为扩展结点，其儿子结点N和O均为叶结点，它们的价值分别 为25和0。 接下来，存储活结点的堆已空，算法终止。算法搜索得到最优值为50。相应
的最优解是从根结点A到结点L的路径(0,1,1)。
分析
当要寻求问题的一个最优解时，与回溯法时类似地可以用剪枝函数来加速搜
回溯法 深度优先搜索
栈
活结点的所有可行子 找出满足约束条件的所 结点被遍历后才被从 有解 栈中弹出
分支限 广度优先或最 界法 小消耗优先搜 索
队列、优先队列 每个结点只有一次成 找出满足约束条件的一 为扩展结点的机会 个解或特定意义下的最 优解
分支限界法的基本思想
适合采用回溯法解决的问题 — n后问题
分支限界法的基本思想
分支限界法通常以广度优先或以最小耗费（最大效益）优先的方式搜索问 题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列
树。
分支限界法的基本思想
两种典型的解空间树：
子集树（Subset Trees）：当所给问题是从n个元素的集合中找出满足某种性 质的子集时，相应的解空间树称为子集树。在子集树中，|S0|=|S1|=…=|Sn1|=c，即每个结点有相同数目的子树，通常情况下c=2，所以，子集树中共有 2n个叶子结点，因此，遍历子集树需要O(2n)时间。
分支限界法引言
分支限界法与回溯法的不同求解目标：
回溯法的求解目标：找出解空间树中满足约束条件的所有解；
分支限界法的求解目标：找出满足约束条件的一个解，或是在满足约束条
件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下
的最优解。
分支限界法引言
分支限界法与回溯法的不同搜索方式：
分支限界法两种方式：
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。
最常见的有以下两种方式： 队列式（FIFO）分支限界法：队列式分支限界法将活结点表组织成一个 队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。 优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个 优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结 点成为当前扩展结点。常用堆来实现优先队列