当前位置：文档之家 › 第6章 分支限界法

第6章 分支限界法

  • 格式：ppt
  • 大小：712.50 KB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

第6章 分支限界法(1-例子)

第6章 分支限界法(1-例子)
5
6.3 装载问题
3. 算法的改进
// 检查右儿子结点 // 检查左儿子结点 Type wt = Ew + w[i]; if (wt <= c) { // 可行结点 右儿子剪枝
if (Ew + r > bestw && i < n) Q.Add(Ew); // 可能含最优解 Q.Delete(Ew);// 取下一扩展结点 提前更新 bestw
5. 优先队列式分支限界法
解装载问题的优先队列式分支限界法用最大优先队列存 储活结点表。 活结点x在优先队列中的优先级定义为从根结点到结点x的 路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。 在优先队列式分支限界法中，一旦有一个叶结点成为当 前扩展结点，则可以断言该叶结点所相应的解即为最优解。 此时可终止算法。
while6.3 (true)装载问题 { // 检查左儿子结点 2. 队列式分支限界法 if (Ew + w[i] <= c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n); // 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++; // 进入下一层 } }
if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) Q.Add(wt); }

第六章 分支限界法.ppt

第六章 分支限界法.ppt
得到的解 继续搜索
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值。

第6章 分支限界法

第6章 分支限界法

通常采用最大堆或最小堆来实现优先队列式分支限界法求解问 题。
可以用如下方法求得最优解中的分量：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)

算法设计与分析(第6章 分支限界法)

算法设计与分析(第6章 分支限界法)

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中所 含顶点数最多的团。
• （当前扩展结点）顶点数上界=已确定的顶点数+未确定的顶点 数的上界

分支限界算法

分支限界算法

分支限界算法
通俗来讲，分支限界法是一种将一个具有相互冲突和复杂约束的大型优化问题划分成一系列规模较小的子问题的方法，并以此最终获得给定问题的最优解。

它把原问题分割成几个小子问题，每个子问题都有一个限制条件，分支限界法从一个子集中选择，分支出若干解法，并把选出的最优解作为下一次算法迭代的初始解，继续作为一个新的子集挑选优解，以此迭代直至找到了全局最优解。

分支限界法的运行流程主要包括以下几个步骤：
1.初始化：确定问题的规模大小及初始解；
2.分支：根据某种规则，将现有的一个节点分成若干个候选子节点，并构建子节点与父节点之间的映射关系；
3.限界：每个候选子节点都有一个下限价值，以降低算法计算量；
4.剪枝：根据某种明确的剪枝规则，去除那些应该剪枝的节点，减少计算量；
5.搜索：递归搜索下一个更优解，直至得出最优解。

分支限界法

分支限界法

• 在子树X中离X最近的那个 在子树X中离X
答案结点到X的路径长度。 答案结点到X的路径长度。
X
a
6
分支限界法的基本思想
用c(·)表示有智力的排序函数，又称为结点成本函数。 c(·)表示有智力的排序函数，又称为结点成本函数。 表示有智力的排序函数 它的定义如下： 它的定义如下： 如果X是答案结点， c(X)是由解空间树的根结点 1. 如果X是答案结点，则c(X)是由解空间树的根结点 到X的成本； 的成本； 如果X不是答案结点且子树X不包含任何答案结点， 2. 如果X不是答案结点且子树X不包含任何答案结点， 则c(X)=∞; 否则c(X)等于子树X c(X)等于子树 3. 否则c(X)等于子树X中具有最小成本的答案结点的 成本。 成本。 但要指出的事，要得到结点成本函数c(·)所用的计算工作量 但要指出的事，要得到结点成本函数 所用的计算工作量 与解原问题具有相同复杂度， 与解原问题具有相同复杂度，这是因为计算一个结点的代价 通常要检索包含一个答案结点的子树X才能确定 才能确定， 通常要检索包含一个答案结点的子树 才能确定，因此要得 到精确的成本函数一般是不现实的。 到精确的成本函数一般是不现实的。在算法中检索活结点的 ˆ 来排出。 次序通常根据能大致估计结点成本函数 c(⋅)来排出。 7
10 0 20 2 20 10 4
∞
∞
10
• •
LC没能达到这个最小成本答案结点的原因在于有两个这样 LC没能达到这个最小成本答案结点的原因在于有两个这样 ˆ ˆ 的节点X 的节点X和Y，当 c ( X ) > c (Y ) 时，却有 c ( X ) < c (Y ) ˆ ˆ 那么， 如果是每对 c ( X ) < c (Y ) 的X、Y都有 c ( X ) < c (Y ) ，那么， LC总会找到一个最小成本答案结点 总会找到一个最小成本答案结点。 LC总会找到一个最小成本答案结点。 12

《算法设计与分析》-第六章 分支限界

《算法设计与分析》-第六章 分支限界

例：n=3,w=[16,15,15],p=[45,25,25],c=30 队列式(FIFO)分支限界法
1 1 D 1 H 0 I 1 J B 0 E 0 K 1 L 1 F M 1 N A 0 C 0 G 0 O
6.2
0-1背包问题 背包问题
优先队列式分支限界法 算法的思想
首先，要对输入数据进行预处理，将各物品依其单位重量价值从大 到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物 品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子 结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展 结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才 将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。
6.1 分支限界法的基本思想
3. 常见的两种分支限界法
(两种选择下一个E节点的方法：) （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为 扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节 点成为当前扩展节点。
6.2
Байду номын сангаас
0-1背包问题 背包问题
6.3 回溯法与分支限界法对比
优先队列分支限界法能够有效地减少搜索的结点数目， 从而减少计算时间。因此比较适合于求解目标则是找出 满足约束条件的一个解或最优解；而回溯法则比较适合 于找出解空间树中满足约束条件的所有解。 回溯法比分支限界在占有内存方面具有优势。 – 回溯法占用的内存是O(解空间的最大路径长度)，而 分支定界所占的内存为O(解空间的大小)。 对于子集空间，回溯法需O(n)的内存空间，而分 支定界需O(2n) 对于排列空间，回溯法需O(n)的内存空间，而分 支定界需O(n!)

模块06分支限界法

模块06分支限界法

分支限界法
Ø 分支限界法常以广度优先或以最小耗费（最大效益）优 先的方式搜索问题的解空间树。 Ø 在分支限界法中，每一个活结点只有一次机会成为扩展 结点。活结点一旦成为扩展结点，就一次性产生其所有 儿子结点。在这些儿子结点中，导致不可行解或导致非 最优解的儿子结点被舍弃，其余儿子结点被加入活结点 表中。 Ø 此后，从活结点表中取下一结点成为当前扩展结点，并 重复上述结点扩展过程。这个过程一直持续到找到所需 的解或活结点表为空时为止。
（1）求解目标不同 • 回溯法的求解目标是找出解空间树中满足 约束条件的所有解，而分支限界法的求解 目标则是找出满足约束条件的一个解，或 是在满足约束条件的解中找出在某种意义 下的最优解。 （2）搜索方式的不同 • 回溯法以深度优先的方式搜索解空间树， 而分支限界法则以广度优先或以最小耗费 优先的方式搜索解空间树。
2. 队列式分支限界法
Ø 在算法的while循环中，首先检测当前扩展结点的左儿子结点 是否为可行结点。如果是则将其加入到活结点队列中。然后 将其右儿子结点加入到活结点队列中(右儿子结点一定是可行 结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 Ø 活结点队列中的队首元素被取出作为当前扩展结点，由于
队列中每一层结点之后都有一个尾部标记-1，故在取队首元素 时，活结点队列一定不空。当取出的元素是-1时，再判断当前 队列是否为空。如果队列非空，则将尾部标记-1加入活结点队 列，算法开始处理下一层的活结点。
2. 队列式分支限界法
while (true) { // 检查左儿子结点 if (Ew + w[i] <= c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n); // 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++;} // 进入下一层 } }

第6章__分支限界法

第6章__分支限界法
20
算法的改进

节点的左子树表示将此集装箱装上船，右 子树表示不将此集装箱装上船。

设bestw是当前最优解；ew是当前扩展结点所相 应的重量；r是剩余集装箱的重量。则当 ew+rbestw时，可将其右子树剪去，因为此时 若要船装最多集装箱，就应该把此箱装上船。

另外，为了确保右子树成功剪枝，应该在 算法每一次进入左子树的时候更新bestw的 值。
28
优先队列式分支限界法

在优先队列式分支限界法中，一旦有一个叶结 点成为当前扩展结点，则可以断言该叶结点所 相应的解即为最优解。此时可终止算法。 最大优先级队列中的活节点都是互相独立的， 因此每个活节点内部必须记录从子集树的根到 此节点的路径。 一旦找到了最优装载所对应的叶节点，就利用 这些路径信息来计算x 值。
分支限界法
1
提纲
分支限界法的基本思想 装载问题 布线问题 0-1背包问题 小结

2
提纲
分支限界法的基本思想 装载问题 布线问题 0-1背包问题 小结

3
分支限界法的基本思想

分支限界法与回溯法的不同

求解目标

回溯法：所有解 分支限界法：找出满足约束条件的一个解，或是满 足约束条件的解中找出在某种意义下的最优解。 回溯法：深度优先搜索解空间树 分支限界法：广度优先或以最小耗费(最大收益)优先 的方式搜索解空间树。
25
构造最优解
算法EnQueue做如下修改： void EnQueue(…..) {// 如不是叶节点，向Q中添加一个i 层、重量为wt的活节点 // 新节点是E的孩子。当且仅当是左孩子时，ch为true。 if (i == n) // 叶子 { if (wt == bestw) // 目前的最优解 { bestE = E; bestx[n] = ch;} return; } QNode<T> *b; // 不是叶子, 添加到队列中 b = new QNode<T>; b->weight = wt; b->parent = E; b->LChild = ch; Q.Add(b); }

第6章分支限界法

第6章分支限界法

堆的定义： 若n个元素的序列{a1 a2 … an} 满足 ai ≤ a2i ai ≤ a2i+1 或 ai ≥ a2i ai ≥ a2i+1
则分别称该序列{a1 a2 … an}为小根堆 和大根堆。 从堆的定义可以看出，堆实质是满足如下性质的完 全二叉树： 二叉树中任一非叶子结点均小于(大于)它的孩子结点
问题定义：在n×n的国际象棋棋盘上摆下n个皇后，使所有 的皇后都不能攻击到对方，找出所有符合要求的情况。 分析： n后问题的解空间树是一棵排列树，解与解之间不存在优 劣的分别。直到搜索到叶结点时才能确定出一组解。 采用回溯法可以系统地搜索问题的全部解。
分支限界法的基本思想
既可以采用回溯法也可以采用分支限界法解决
4
B G H I H I E J C D
(0,0)
0
D
0
E
0
(5,15)
F
0
1
G M
(0,0)
1
1
1
0
H
10 0
I
J
15 10 5
K
0
L
N
15 0
O
15 10 20 5
B C D E F G I K L M N O
20 0 35 20 15 0 35 20 40 15 25 0 当前最优解 当前最优解
举例：0-1背包问题
n=3时0-1背包问题的一个实例：w=[16, 15, 15]，p=[45, 25, 25]，
的问题 — 0-1背包问题
问题定义：给定若干物品的重量和价值，以及 一个背包的容量上限。求出一种方案使得背包 中存放物品的价值最高。
分析：0-1背包问题的解空间树是一棵子集树， 所要求的解具有最优性质。

算法设计与分析 第六章分支界限法

算法设计与分析 第六章分支界限法

Closed表
[1, 0, 0] [2, 10, 1]
[4, 30, 1]
[3, 50, 4]
取出[3, 60, 3]，因其已经是目标结点，算法成 3] 取出[4, 30, 1]放入Closed；生成其后继[3, 50, 2]， 取出[5, 50, 4]放入Closed；生成其后继[2, 100, 取出[2, 10, 1]放入Closed；生成其后继[3, 60, 4] 取出[1, 0, 0]放入Closed；生成其后继[2, 10, 1]、 初始时，将源[1, 0, 0]放入Open，Closed为空。 和[5, 90, 4] ，修订Open中已有的两个结点并依 60, 3]，前者因劣于Closed中的[2, 10, 功并终止。 100, 1]，并依序放入Open。 1]而 并依序插入Open。 [4, 30, 1]和[5, 被抛弃，后者修订了Open中的[5, 90, 4]。 序排列。 依据逆向指针可得最短路径为1→4→3→5。

2013-8-14 计算机算法设计与分析 18
用新的评价函数求TSP

下面用新的评价函数求前面的例子，我们已经 求得了它的归约矩阵C’和约数r = 47。 5 3 63× 62 2 51 4 50
121 2 69×64× 67× 68× 81 4 × 3 4 2 3 ×
47 1
62 3 84× 72× 4 5 4 × 76
找到了一条周游路线 1→5→3→4→2→1， 其长度为95。 这不是最短周游路线，需要修改上界后继续搜索。
2013-8-14 计算机算法设计与分析 12
32 3 35 4 46 37 84 58 2 4 2 3 3 4 49 62 86 2
归约矩阵以及约数
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
24
6.4 布线问题
for (int i = 0; i < NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) {
5
6.1 分支限界法的基本思想
常见的两种分支限界法
（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点 为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节 点成为当前扩展节点。
6
6.1 分支限界法的基本思想
优先队列中规定的结点优先级常用一个与该
13
6.2 单源最短路径问题
while (true) { for (int j = 1; j <= n; j++) if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])) { // 顶点i到顶点j可达，且满足控制约束 dist[j]=E.length+c[E.i][j]; 顶点I和j间有边，且此 prev[j]=E.i; 路径长小于原先从原点 // 加入活结点优先队列 到j的路径长 MinHeapNode<Type> N; N.i=j; N.length=dist[j]; H.Insert(N);} try {H.DeleteMin(E);} // 取下一扩展结点 catch (OutOfBounds) {break;} // 优先队列空 } }
18
6.3 装载问题
3. 算法的改进
// 检查左儿子结点
提前更新 bestw
// 检查右儿子结点
右儿子剪枝
Type wt = Ew + w[i]; // 左儿子结点的重量
if (wt <= c) { // 可行结点 if (Ew + r > bestw && i < n) Q.Add(Ew); Q.Delete(Ew); // 可能含最优解 // 取下一扩展结点
10
6.2 单源最短路径问题
1. 问题描述
下图是用优先队列式分支限界法解有向图G的单源最短路径问 题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对 应的当前路长。
11
6.2 单源最短路径问题
2. 算法思想
解单源最短路径问题的优先队列式分支限界法用一极小堆来 存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它 的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当 前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相 邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源 出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优 路径长度，则将该顶点作为活结点插入到活结点优先队列中。这 个结点的扩展过程一直继续到活结点优先队列为空时为止。
12
6.2 单源最短路径问题
3. 剪枝策略
在算法扩展结点的过程中，一旦发现一个结点的下界不小 于当前找到的最短路长，则算法剪去以该结点为根的子树。
在算法中，利用结点间的控制关系进行剪枝。从源顶点s出 发，2条不同路径到达图G的同一顶点。由于两条路径的路长不 同，因此可以将路长长的路径所对应的树中的结点为根的子树 剪去。
4
分支限界法对回溯法的改进之处

回溯法对问题状态空间树的搜索过程是盲目进行的， 当问题求最优解时，搜索也只有在找到了一个可行 解之后目标函数的界才有实际意义，在寻找第一个 可行解时，搜索过程仍然是盲目的。分支限界法不 再像单纯的回溯法那样盲目进行搜索，也不是遇到 死结点才往回走，而是预先分别估算沿着扩展结点 各个儿子结点向下搜索路径中目标函数可能取得的 “界”，把它们保存在一张结点表中，依据结点表 中不断更新的信息，不断调整自己的搜索方向，有 选择、有目的地往前搜索，回溯也不是单纯地沿父 亲结点，一层层向上回溯，而是依据结点表中的信 息进行回溯。
25
6.5
算法的思想
0-1背包问题
首先，要对输入数据进行预处理，将各物品依其单位 重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级 由已装袋的物品价值加上剩下的最大单位重量价值的物品 装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。 如果该左儿子结点是可行结点，则将它加入到子集树和活 结点优先队列中。当前扩展结点的右儿子结点一定是可行 结点，仅当右儿子结点满足上界约束时才将它加入子集树 和活结点优先队列。当扩展到叶节点时为问题的最优值。
// 该方格未标记
grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) &&
(nbr.col == finish.col)) break; // 完成布线
Q.Add(nbr);} }
找到目标位置后，可以通过回溯方法找到这条最短路径。
21
6.3 装载问题
5. 优先队列式分支限界法
解装载问题的优先队列式分支限界法用最大优先队列存储 活结点表。活结点x在优先队列中的优先级定义为从根结点到结 点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以 结点x为根的子树中所有结点相应的路径的载重量不超过它的优 先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前 扩展结点，则可以断言该叶结点所相应的解即为最优解。此时 可终止算法。
while (true) { // 检查左儿子结点 if (Ew + w[i] <= c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n); // 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++;} // 进入下一层 } }
17
6.3 装载问题
3. 算法的改进
节点的左子树表示将此集装箱装上船，右子树表示不将 此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点 所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时， 可将其右子树剪去，因为此时若要船装最多集装箱，就应该 把此箱装上船。
另外，为了确保右子树成功剪枝，应该在算法每一次进 入左子树的时候更新bestw的值。
22
6.4 布线问题
1. 算法思想
解此问题的队列式分支限界法从起始位置a开始将它作 为第一个扩展结点。与该扩展结点相邻并且可达的方格成为 可行结点被加入到活结点队列中，并且将这些方格标记为1， 即从起始方格a到这些方格的距离为1。
接着，算法从活结点队列中取出队首结点作为下一个扩 展结点，并将与当前扩展结点相邻且未标记过的方格标记为 2，并存入活结点队列。这个过程一直继续到算法搜索到目 标方格b或活结点队列为空时为止。即加入剪枝的广度优先 搜索。
3
6.1 分支限界法的基本思想
分支限界法常以广度优先或以最小耗费（最大效益）优先的方 式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些 儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其 余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上 述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为 空时为止。
(2)将剩余的集装箱装上第二艘轮船。
15
6.3 装载问题
2. 队列式分支限界法
在算法的while循环中，首先检测当前扩展结点的左儿子 结点是否为可行结点。如果是则将其加入到活结点队列中。然 后将其右儿子结点加入到活结点队列中(右儿子结点一定是可 行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。
4个城 市的旅 行售货 员问题 的解空 间树
8
分支限界法的优缺点
优点
分支限界法可以求得最优解，且平均速度快，检
查的子问题较少，能较快求得最佳解；
缺点
要存储很多叶子结点限界和对应耗费矩阵，花费
的空间多；
9
6.2 单源最短路径问题
1. 问题描述
下面以一个例子来说明单源最短路径问题：在下图所给的有 向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目 标顶点t之间的最短路径。
（5）最大团问题； （6）旅行售货员问题 （7）电路板排列问题 （8）批处理作业调度问题
2
6.1 分支限界法的基本思想
分支限界法与回溯法
（1）求解目标不同：分支限界法的求解目标则是找出满足约束条 件的一个解，或是在满足约束条件的解中找出在某种意义下的最优 解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树， 而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
第6章
分支限界法
1

学习要点 理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 （1）单源最短路径问题 （2）装载问题； （3）布线问题

相关主题