当前位置：文档之家 › 第6章 分支限界法(1-例子)

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

  • 格式：pdf
  • 大小：208.86 KB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

第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）最小优先队列：数值小则优先级高 实现方式：最小堆

第六章 分支与界限

第六章 分支与界限
4
• 在整个搜索过程中，每遇到一个活结点，就对它的各个孩 子结点进行目标函数可能取得值得估算，然后把以此来更 新表结点：丢弃不再需要的结点，加入新的结点。再从表 中选取“界”取极值的结点，并重复上述过程。 • 随着过程的不断深入，结点表中所估算的目标函数的极值， 越来越接近问题的解。当搜索到一个叶子结点时，如果对 该结点所估算的目标函数的值就是结点表中最大或最小值， 那么沿叶子结点到根结点的路径确定的解就是问题的解。
∞ 5 20 10 23
25 ∞ 16 51 9
41 18 ∞ 25 7
32 31 7 ∞ 11
28 26 1 6 ∞
13
14
6.2.1 费用矩阵的行归约（列归约）
• 费用矩阵c的第i行（或第j列）中的每个元素减去一个正常 数lhi（或chj），得到一个新的费用矩阵，使得新矩阵中第i 行（或第j列）中的最小值为0，称为费用矩阵的行归约 （列归约），称lhi为行归约常数，称chj为列归约常数。 0 0 1 2 3 4 1 2 3 4 0
∞ 13 3 43 4 0
0 2
3 lh0=3 4
13 ∞ 19 0
0 2 ∞ 0
0 0 0 ∞
∞ 0 19 4 16
0 ∞ 15 45 2
16 13 ∞ 19 0
3 22 2 ∞ 0
3 21 0 0 ∞
的选择中，必然包含第i行 的最小元素和第j列的最小 元素（除cij之外的）。
ch1=2
25 26
0 ∞ 15 45 2
16 13 ∞ 19 0
3 22 2 ∞ 0
3 21 0 0 ∞
h lhi ch j
j 0
3 4
∞ 5 20 10 23

第6章 分支限界法

第6章 分支限界法

6.3 装载问题
1. 问题描述
• 有一批共个集装箱要装上 2 艘载重量分别为 C1 和C2的轮船，其中集装箱i的重量为wi，且
w
i 1
n
i
c1 c2
• 装载问题要求确定是否有一个合理的装载方案 可将这个集装箱装上这2艘轮船。如果有，找出 一种装载方案。 • 如果一个给定装载问题有解，则采用装载策略
最短路径问题关键部分算法
while (true){ // 搜索问题的解空间 for (int j=1;j<=n;j++) if(c[E.i][j] <max && E.length+cE.i][j] < dist[j]) { // 顶点i到顶点j可达，且满足控制约束 dist[j]=E.length+c[E.i][j]; //修正数值
bestx[j] = (bestE.LChild) ? 1 : 0; bestE = bestE.parent; }
学习要点
理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架，会描述队列变化
（1）队列式(FIFO)分支限界法
（2）优先队列式分支限界法 ：会确定优先级
通过应用范例学习分支限界法的设计策略
掌握两类例子每类2个例子：子集树、排列树
分支限界法与回溯法
（1）求解目标：基本相同 回溯法：通过回溯找出满足约束条件的所有解或最 优解 分支限界法：找出满足约束条件的一个解，或是在 满足约束条件的解中找出在某种意义下的最优解 （2）搜索方式：不同
3. 约束条件 1）显式约束：对分量xi的取值限定。
2）隐式约束：为满足问题的解而对不同分量之 间施加的约束。 4. 解空间：对于问题的一个实例，解向量满足显式 约束条件的所有多元组，构成了该实例的一个解空间。

第6章 分支限界法

第6章 分支限界法
源最短路径问题的优先队 列式分支限界法用一极小堆来存储 活结点表。 活结点表。 其优先级是结点所对应的当前路长。 优先级是结点所对应的当前路长。
16
算法从图G的源顶点s和空优先队列开始。 算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。 结点s被扩展后，它的儿子结点被依次插入堆中。 此后， 此后，算法从堆中取出具有最小当前路长的结点 作为当前扩展结点， 作为当前扩展结点，并依次检查与当前扩展结点 相邻的所有顶点。 相邻的所有顶点。 如果从当前扩展结点i到顶点j有边可达， 如果从当前扩展结点i到顶点j有边可达，且从源 出发，途经顶点i再到顶点j 出发，途经顶点i再到顶点j的所相应的路径的长 度小于当前最优路径长度， 度小于当前最优路径长度，则将该顶点作为活结 点插入到活结点优先队列中。 点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列 为空时为止。 为空时为止。
r=14, p=45 不可解 r=14, r=15, p=45 p=25 r=30, p=0
不可解
r=14, p=45
r=0, p=50
7
用队列式分支限界法解此问题时，用一个队列 用队列式分支限界法解此问题时，用一个队列 来存储活结点表。 来存储活结点表。
不可解
队头 B C E F
不可解 G K L M N O
第6章 分支界限法
学习要点
• 理解分支限界法的剪枝搜索策略。 理解分支限界法的剪枝搜索策略。 • 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 队列式(FIFO)分支限界法 （2）优先队列式分支限界法 • 通过应用范例学习分支限界法的设计策略。 通过应用范例学习分支限界法的设计策略。
11

第六部分 分支限界法

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

六章分支限界法

六章分支限界法
（2）搜索方式的不同：回溯法以深度优先的方式搜索解 空间树，而分支限界法则以广度优先或以最小耗费优先 的方式搜索解空间树。
6.1 分支限界法的基本思想
分支限界法与回溯法
• 回溯与分支限后评估这个部分
解： – 如果加上剩下的分量也不可能求得一个解，就不再生
首先把物品按照P(i)/W(i)≥P(i+1)/W(i+1)的衡量标准排序， 以此顺序读入物品。并且定义一个大小为物品多少的解向量X， X的一个分量就代表某个物品的装入情况。
6.2 0-1背包问题 (0-1 Knapsack Problem)
[问题描述] 设有n个物体和一个背包，物体i的重量为wi ， 价值为pi ，背包的载荷为M，找一个装载方案，使得能放入 背包的物体总价值最高。
6.1 分支限界法的基本思想
（用于求解最优化问题）
目标函数限界U: 初始U可取，若x*是任一答案结点，且 c(x*)<U, 则更新U=c(x*)， x*为已知答案结点值最小者。当搜索 到结点x，而c(x)>U时， x将不必扩展（剪枝）。
活动结点表: 通常采用优先队列方式组织， c(x)小者优先。
6.1 分支限界法的基本思想
E-结点一直保持到死为止的状态生成方法导致分枝-限 界方法（branch-and-bound）。
6.1 分支限界法的基本思想
分支限界法常以广度优先或以最小耗费（最大效 益）优先的方式搜索问题的解空间树。对已处理的 各结点根据限界函数估算目标函数的可能取值，从 中选取使目标函数取得极值（极大/极小）的结点 优先进行广度优先搜索不断调整搜索方向，尽快 找到解。
• 然而，如果评价函数选择得好，采用分支限界法可 能有一个小得多的常数因子。
• 好的评价函数应该有一个尽可能高的下界估计和一 个尽可能低的上界估计，从而使得搜索空间能够得 到有效的压缩，从而提高效率。

分支限界法求单源最短路径

分支限界法求单源最短路径

分支限界法求单源最短路径分支限界法是一种求解最优化问题的算法，在图论中，可以用来求解单源最短路径。

本文将介绍分支限界法的基本原理和步骤，并通过一个具体的示例来说明其应用。

一、分支限界法简介分支限界法是一种穷举搜索算法，通过不断地将问题空间划分成更小的子问题，以寻找最优解。

它与传统的深度优先搜索算法相似，但在搜索过程中，通过引入上界（界限）来限制搜索范围，从而有效地剪枝和加速搜索过程。

分支限界法求解单源最短路径问题的基本思想是，首先将源点标记为已访问，然后以源点为根节点构建一棵搜索树，树中的每个节点表示当前访问的顶点，并记录到达该顶点的路径和权值。

通过遍历搜索树，逐步更新最短路径以及当前最优权值，从而找到最短路径。

二、分支限界法的步骤1. 创建搜索树：- 将源点标记为已访问，并将其作为根节点。

- 根据源点与其他顶点之间的边权值构建搜索树的第一层。

- 初始化当前最优路径和权值。

2. 遍历搜索树：- 从当前层中选择一个未访问的顶点作为扩展节点。

- 计算到达该扩展节点的路径和权值，并更新当前最优路径和权值。

- 根据已有的路径和权值，计算该扩展节点的上界，并与当前最优权值进行比较。

若上界小于当前最优权值，则进行剪枝操作，否则继续搜索。

- 将该扩展节点的子节点添加到搜索树中。

3. 更新最短路径：- 当搜索树的所有叶子节点都已遍历时，找到最短路径以及相应的权值。

三、示例分析为了更好地理解分支限界法的运行过程，我们将通过一个具体的示例来进行分析。

假设有一个有向带权图，其中包含5个顶点和6条边。

首先，我们需要构建初始搜索树，将源点A作为根节点。

根据源点与其他顶点之间的边权值，我们可以得到搜索树的第一层B(2)、C(3)、D(4)、E(5)。

接下来，我们从第一层选择一个未访问的顶点作为扩展节点。

假设选择节点B进行扩展。

此时，我们计算到达节点B的路径和权值，并更新当前最优路径和权值。

对于节点B，到达它的路径为AB，权值为2。

分支限界法典型例题

分支限界法典型例题

分支限界法典型例题分支限界法(Branch and Bound)是一种常见的算法分析技术,用于解决搜索问题和动态规划问题。

以下是一些分支限界法的典型例题:1. 最长公共子序列(LCS):求给定两个字符串的最长公共子序列。

可以使用分支限界法,首先找出两个字符串中的不同字符出现的次数,然后用哈希表存储这些计数器。

最后,遍历哈希表中的每个计数器,找到最大的计数器的值,即为最长公共子序列的长度。

2. 背包问题(Knapsack problem):给定一个背包,容量为64,有多个选项,每个选项的重量和容量不限。

求给定背包中可以放入的最大重量的背包物品。

可以使用分支限界法,首先列出所有可能背包容量的组合,然后用枚举法找出每个背包容量下可以放入的最大重量的物品,最后计算出可以放入的最大重量的物品数量。

3. 最短路径问题(Shortest Path problem):给定一个二维图,目标为找到从源点出发,到达所有目标点的路径。

可以使用分支限界法,首先找出图中的所有节点和它们之间的联系,然后用递归算法计算每个节点到源点的路径。

最后,通过剪枝,可以找到最短路径。

4. 最大子数组和问题(Maximum Subarray and Problem):给定一个数组,求出其中任意一个元素的最大值。

可以使用分支限界法,首先找出数组中的最小值和最大值,然后用递归算法计算每个元素的最大值。

最后,通过剪枝,可以找到最大子数组和问题。

5. 模拟退火问题(Simulated Annealing Problem):给定一个概率分布,求出在一定条件下,随机变量的取值分布。

可以使用分支限界法,首先找出概率分布中所有可能的取值,然后用模拟退火算法计算在这些取值中随机变量的取值分布。

最后,通过剪枝,可以找到最优解。

分支限界法

分支限界法

• 在子树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!)

分支限界法

分支限界法

57 B
x3=1
59 B
x3=3
18
采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）：
活结点
扩展活结点得到的状态空间树
活结点表（队列）
head 14
30 38 54
tail
扩展结点14，得新结点15 利用限界函数杀死结点15 1
x1=1
没有新的活结点入队列 50
2
x2=4
18
34 51
3 B

5
1
1 分支搜索-LIFO搜索
8

2
3
4
9 10
5
11 12
6
13 14
7
15
一开始，根结点入栈。 从栈中弹出一个结点为当前扩展结点。 对当前扩展结点，先从左到右地产生它的所有儿子，用约 束条件检查，把所有满足约束函数的儿子入栈; 再从栈中弹出一个结点（栈中最后进来的结点）为当前扩 展结点，……，直到找到一个解或栈为空为止。
活结点54入队列
x1=4
2 19 B 11 B 14 16 B
18
34
x2=1
50
3 B 9 B
8
13
24 B
29
35
40 B
45 B 52 B
x3=2
51
56
61 B
30
32
B
36
B
38
54
x3=3
17
采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）：
活结点
扩展活结点得到的状态空间树
活结点表（队列）
30 31
32 B
36 B
38
54

模块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章分支限界法

堆的定义： 若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
归约矩阵以及约数

第6章 分支限界法

第6章 分支限界法

2. 算法思想
解单源最短路径问题的优先队列式分支限界法用一极小
堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后， 它的儿子结点被依次插入堆中。
算法每次从堆中取出具有最小当前路长的结点作为当前扩 展结点，并依次检查与当前扩展结点相邻的所有顶点。
class QNode {QNode *parent; // 指向父结点的指针
bool LChild;
Type weight;
// 左儿子标志
// 结点所相应的载重量
找到最优值后，可以根据parent回溯到根节点，找到 最优解。
// 构造当前最优解 for (int j = n - 1; j > 0; j--) { bestx[j] = bestE->LChild; //bestx存储最优解路径 bestE = bestE->parent; //回溯构造最优解 }
直到找到所需的解或活动结点表为空为止
5
分支限界法与回溯法的差别
分支限界法不仅通过约束条件, 而且可通过 目标函数的限界来减少无效搜索.
回溯法是深度优先搜索, 而分支限界法是广 度优先搜索. 采用广度优先搜索策略的目的是: 尽早发现 剪枝点.
6
常见的两种分支限界法
（1）队列式(FIFO)分支限界法 将活结点表组织成一个队列，按照先进先出 （FIFO）原则选取下一个结点为扩展结点。 （2）优先队列式分支限界法
将活结点表组织成一个优先队列，按照规定的优先 级选取优先级最高的结点成为当前扩展结点。
• 算法实现时，通常用极大（小）堆来实现 最大（小）优先队列，提取堆中下一个结 点为当前扩展结点，体现最大（小）费用 优先的原则。 • 极大堆满足一个节点必定不小于其子节点， 极小堆正好相反。 • 极大堆中最大的元素必定是其根节点，堆 排序算法正是根据这个特性而产生的：对 一个序列，将其构造为极大堆，然后将根 节点（数组首元素）和数组的尾元素交换， 之后对除了尾元素之外的序列继续以上过 程，直到排序完成。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
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); }
6
6.3 装载问题
4. 构造最优解
为了在算法结束后能方便地构造出与最优值相应的最 优解，算法必须存储相应子集树中从活结点到根结点的路 径。为此目的，可在每个结点处设置指向其父结点的指 针，并设置左、右儿子标志。 class QNode { QNode *parent; // 指向父结点的指针 bool LChild; Type weight; } // 左儿子标志 // 结点所相应的载重量
4
6.3 装载问题
3. 算法的改进
节点的左子树表示将此集装箱装上船，右子树表示不将 此集装箱装上船。 设bestw是当前最优解；Ew是当前扩展结点所相应的重 量；r是剩余集装箱的重量。 则当Ew+rbestw时，可将其右子树剪去。 另外，为了确保右子树成功剪枝，应该在算法每一次进 入左子树的时候更新bestw的值。
a
b
在布线时，电路只能沿直线 或直角布线，为了避免线路 相交，已经布线了的方格要 做封锁标记，其它线路不允 许穿过被封锁了的方格。
11
6.4 布线问题
2. 算法思想
1）解此问题的队列式分支限界法从起始位置a开始将它作 为第一个扩展结点。与该扩展结点相邻并且可达的方格成 为可行结点被加入到活结点队列中，并且将这些方格标记 为1，即从起始方格a到这些方格的距离为1。 2）接着，算法从活结点队列中取出队首结点作为下一个扩 展结点，并将与当前扩展结点相邻且未标记过的方格标记 为2，并存入活结点队列。 3）这个过程一直继续到算法搜索到目标方格b或活结点队 列为空（表示没有通路）时为止。
7
6.3 装载问题
4. 构造最优解
找到最优值后，可以根据parent回溯到根节点，找到 最优解。 // 构造当前最优解 for (int j = n - 1; j > 0; j--) { bestx[j] = bestE->LChild; bestE = bestE->parent; }
8
6.3 装载问题
2. 队列式分支限界法
1）如何获知当前结点是叶子？即如何判断当前结 点的层数？ 解决：设置同层尾部标志，每处理到同层尾部，层 数i++；或者将层数归入结点类的成员中去。 2）如何获得从根到当前可行叶节点的一条从上至 下的纵向路径？ 解决：将父节点的指针和左右标志归入结点类成员 中去，以便找到最优叶节点时，从叶向根回溯得到 路径。 3
9
6.3 装载问题
5. 优先队列式分支限界法 具体实现优先队列的时候，有两个实现 难
点需要处理：
1）优先队列中节点的 “ 优先级 ” 如何定义？ 是否要搜索完所有叶节点？或者是第1个可 行的叶节点即为最优解？ 2）如何保存从根到当前扩展节点的路径？
10
6.4 布线问题
1. 问题描述
印刷电路板将布线区域划分成n×n的方格阵列，如下 图所示。精确的布线问题要求确定连接方格a的中点到方格 b的中点的最短布线方案。
6.3 装载问题
1. 问题描述
有一批共个集装箱要装上2艘载重量分别为C1和C2的轮 船，其中集装箱i的重量为Wi，且
n
w c c
i 1 i 1
2
装载问题要求确定是否有一个合理的装载方案可将这个集 装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策 略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。
找到目标位置后，可以通过回溯方 法找到这条最短路径。 15

6.4 布线问题
3. 算法实现
找到目标位置后，可以通过回溯方法找到这条最短路径。 here=finish; PathLen= grid[here.row][here.col] - 2; for (int j = PathLen-1; j>=0; j--) { //往四个邻域位置寻找前驱位置; …… //here=前驱位置; …… } //记录下here走过的路径就是从起点到终点的最短布线路径
16
6.5 0-1背包问题
P206-210 算法
“完全二叉树”为搜索空间树。 采用“优先队列”为活结点表，优先级为该结点上 界函数Bound计算得出，同回溯算法章节讨论的 Bound值。 最大值堆来实现“优先队列”。 左儿子可行，则入优先队列；右儿子一定可行， 但不一定入优先队列，只有满足上界约束才入优先 队列中。 看P209 MaxKnapsack()。
设置边界的围墙 for (int i = 0; i <= m+1; i++) grid[0][i] = grid[n+1][i] = 1; // 顶部和底部 for (int i = 0; i <= n+1; i++) grid[i][0] = grid[i][m+1] = 1; // 左翼和右翼
14
17
6.7 旅行售货员问题
P213-216 算法
“排列树”为搜索空间树。 用一个“优先队列”存储活结点表。 看P214 BBTSP()。
18
12
6.4 布线问题
2. 算法思想
3 2 2 1 1 a 2 1 2
1 2 3
a b
4 5 6 6 7 8 7 8 8 1 2
b
3 4 5 6 8 7
13
6.4 布线问题
3. 算法实现
定义移动方向 的相对位移
Position offset[4]; offset[0].row = 0; offset[0].col = 1; // 右 offset[1].row = 1; offset[1].col = 0; // 下 offset[2].row = 0; offset[2].col = -1; // 左 offset[3].row = -1; offset[3].col = 0; // 上
1
6.3 装载问题
2. 队列式分支限界法 具体实现的时候，总是将当前扩展结点的所 有儿子入队，然后从队首取结点作为下一个 扩展结点，这有两个实现难点需要处理： 1）如何获知当前结点是叶子？即如何判断 当前结点的层数？ 2）如何获得从根到当前可行叶节点的一条 从上至下的纵向路径？
2
6.3 装载问题
6.4 布线问题
3. 算法实现
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) { // 该方格未标记 grid[nbr.row][nbr.col]=grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布线 Q.Add(nbr); } }