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

第6章 限界剪枝法

  • 格式：ppt
  • 大小：749.50 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

第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); }

第6章 分支限界法(新)

第6章 分支限界法(新)

3
6.1 分支限界法的基本思想
2. 分支限界法基本思想
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜 索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结 点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿 子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其 余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结 点扩展过程。这个过程一直持续到找到所需的解或活结点表为空 时为止。
11
6.5
上界函数
0-1背包问题
// n表示物品总数，cleft为剩余空间
while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++;
//w[i]表示i所占空间 //p n) b += p[i] / w[i] * cleft; // 装填剩余容量装满背包 return b; //b为上界函数
算法的while循环体完成对排列树内部结点的扩展。对于当前 扩展结点，算法分2种情况进行处理：
15
6.7 旅行售货员问题
1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某 个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于 当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶 结点。 2、当s<n-2时，算法依次产生当前扩展结点的所有儿子结点。 由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点是从 剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给 有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点， 计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。当 lcost<bestc时，将这个可行儿子结点插入到活结点优先队列中。

第六章 分支限界法.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值。

第六章 分支与界限

第六章 分支与界限
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章 分支限界法
for (j ← n to 0) { x[j] ← (e.leftChild) ? 1 : 0; e ← e.parent;
}
16
6.3 装载问题
5. 优先队列式分支限界法
解装载问题的优先队列式分支限界法用最大优先队列 存储活结点表。活结点x在优先队列中的优先级定义为 从根结点到结点x的路径所相应的载重量再加上剩余集 装箱的重量之和。
if (ew + r > bestw && i < n) // 可能含最优解 queue.put( ew); ew ← queue.remove(); // 取下一扩展结点
6.3 装载问题
4. 构造最优解
为了在算法结束后能方便地构造出与最优值相应的最 优解，算法必须存储相应子集树中从活结点到根结点的 路径。为此目的，可在每个结点处设臵指向其父结点的 指针，并设臵左、右儿子标志。
依次从活结点表中取下一结点成为当前扩展结点，并 重复上述结点扩展过程。直至找到所需的解或活结点 表为空时为止。
3
6.1 分支限界法的基本思想
3. 常见的两种分支限界法
（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个 节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最 高的节点成为当前扩展节点。
23
6.5 旅行售货员问题
算法中while循环的终止条件是排列树的一 个叶结点成为当前扩展结点。当s=n时，已找 到的回路前缀是x[1:n]，它已包含图G的所有n 个顶点。因此，当s=n时，相应的扩展结点表 示一个叶结点。此时该叶结点所相应的回路的 费用等于该叶结点lcost的值。剩余的活结点 的lcost值不小于已找到的回路的费用。它们 都不可能导致费用更小的回路。因此已找到的 叶结点所相应的回路是一个最小费用旅行售货 员回路，算法可以结束。

第六部分 分支限界法

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

第6章-限界剪枝法


07 章
其他以i为起点和以j为终点的边；
限
将Aj1置为∞，以避免选入(j,1)；
界 剪 枝
如此得到的矩阵就是x的归约矩阵Ax， 归约于Ax的归约数为rx，则定义：
法 ~C(x) = ~C(y)+rx
归约于矩阵Ax的归约数rx是指Ax
相对于Ay的归约数的增量——由
第 于取消了某些边的选择，可能会
07 章
限
为耗费估计函数；
界 剪
1 3 4 15
1234
枝
2
5 12
5678
法
7 6 11 14
9 10 11 12
8 9 10 13
13 14 15
最小耗费搜索法
最小耗费搜索法
第
15迷问题
07
布局结构描述
章
布局结点不仅包括数字位的分布情况，还包括已经推演的步 数和与目标布局的差异，以及指向父结点的指针。
~C(e)≤~C(x)，
章
若e是回答结点，则
对x分枝中的任一解结点y，有
输出解或求解路径，求解结~束C(；x)≤C(y)=D(y)，
限
否则
又知：~C(e)=C(e)=D(e)，则
界
检查e的所有子结点x： D(e)≤D(y)。
剪
若x满足约束条件，则
枝
计算~C(x)，并将x入队；
法
记录搜索路径；
限
~C(y)>U，则由C(x)的单调性和~C(x)是C(x)的下界可知：
界
U<~C(y)≤C(y)≤C(x) x为解结点
剪
即，在y的子树中不会包含所要求的最优解结点x*，因而可以
枝
放弃对该子树的搜索。

计算机算法设计与分析(第3版)王晓东__第6章


(2)将剩余的集装箱装上第二艘轮船。
11
6.3 装载问题
2. 队列式分支限界法
在算法的while 循环中，首先检测当前扩展结点的左儿子 结点是否为可行结点。如果是则将其加入到活结点队列中。然 后将其右儿子结点加入到活结点队列中 (右儿子结点一定是可 行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。
6
6.2 单源最短路径问题
1. 问题描述
下图是用优先队列式分支限界法解有向图G的单源最短路径问 题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对 应的当前路长。
7
6.2 单源最短路径问题
2. 算法思想
解单源最短路径问题的优先队列式分支限界法用一极小堆来 存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它 的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当 前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相 邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源 出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优 路径长度，则将该顶点作为活结点插入到活结点优先队列中。这 个结点的扩展过程一直继续到活结点优先队列为空时为止。
9
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;} // 优先队列空 } }

分支限界法


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

Matlab教程课件-第6章_分支限界法

• 极大堆中最大的元素必定是其根节点，堆 排序算法正是根据这个特性而产生的：对 一个序列，将其构造为极大堆，然后将根 节点（数组首元素）和数组的尾元素交换， 之后对除了尾元素之外的序列继续以上过 程，直到排序完成。
8
例 1 ：0-1背包问题(0-1Knapsack Problem )
问题陈述 设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包 的载荷为M, 若将物体i(1 i n,)装入背包,则有价值为pi . 目标是找到一个方案, 使得能放入背包的物体总价值最高.
原则选取下一个结点为扩展结点。
（2）优先队列式分支限界法 将活结点表组织成一个优先队列，按照规定的优先
级选取优先级最高的结点成为当前扩展结点。
• 算法实现时，通常用极大（小）堆来实现 最大（小）优先队列，提取堆中下一个结 点为当前扩展结点，体现最大（小）费用 优先的原则。
• 极大堆满足一个节点必定不小于其子节点， 极小堆正好相反。
设N=3, W=(16,15,15), P=(45,25,25), C=30
1.队列式分支限界法 2.优先队列式分支限界法
9
0-1背包问题：队列式分支限界法
用一个队列存储活结点表，初始为空 A为当前扩展结点，其儿子结点B和C均为可行结点，将其
按从左到右顺序加入活结点队列，并舍弃A。 按FIFO原则，下一扩展结点为B，其儿子结点D不可行，
分支限界法以广度优先或以最小耗费（最大效益）优 先的方式搜索问题的解空间树。
每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子 结点。
儿子结点中，导致不可行解或导致非最优解的儿子结 点被舍弃，其余儿子结点被加入活结点表中。
从活结点表中取下一结点成为当前扩展结点，并重复 上述结点扩展过程。这个过程一直持续到找到所需的解 或活结点表为空时为止。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4 8 12
2
7 8 6 9
5
11 10
12
14 13
最小耗费搜索法

最小耗费搜索法

第 07 章 限 界 剪 枝 法
15迷问题

布局结构描述

布局结点不仅包括数字位的分布情况，还包括已经推演的步 数和与目标布局的差异，以及指向父结点的指针。 初始化集合S={}，记录曾经出现过的布局； 初始化优先队列Q，以布局的~C(x)作为权值； 起始布局入队，并记入S； 循环，直至队列空 布局T出队； 若T为目标布局，则从T倒推出移动步骤，求解结束； 将T的所有未处理的可推演布局入队，并记入S；
各行的约数分别为r(1)＝10，r(2)＝2，r(3)=2， r(4)=3，r(5)=4。 各列的约数分别为r‘(1)＝l，r’(2)=0， r‘(3)＝3 ，r’(4)= 0，r＇(5)＝0。该矩阵的约数为 r＝25。 第 从归约矩阵的定义可以推知，对于G中的任意 07 章 一条周游路线有：
ij 限 ( i . j ) p ( i , j ) p 界 由此可以得出结论：求带耗费矩阵C的有向图G 剪 枝 的最小耗费周游路线，等价于求带有耗费矩阵C＇ 法 的有向图G的最小耗费周游路线，而且，前者的周
限界剪枝法

旅行售货员问题

问题：某售货员要到若干城市去推销，已知各城市之间的路程 （或旅费），求一条从驻地出发，经过每个城市仅一次，最后回 到驻地的路线，使总的路程（或总旅费）最小。 问题可以描述成一个有向网G上的最小权值极大简单回路问题；不 失一般性，设起点为顶点1，则解的形式为{1,p1,p2…pn-1,1}，取中 间部分p1,p2…pn-1作为解结点的形式， p1,p2…pn-1可以看作2到n的 一个排列，若G是一个完全图，则显然状态空间中的结点数为(n1)!； 定义耗费函数C(x)： 当x为解结点时，C(x)取x的路线耗费； 当x不是解结点时，C(x)取x的子树中最小耗费解结点的耗费； 定义上界函数u(x)： 当x为解结点时，u(x) = C(x)； 当x不是解结点时，u(x) = ∞；
2
一 限界剪枝法的基本思想
1. 限界剪枝法与回溯法的不同
（1）求解目标：回溯法的求解目标是找出解空 间树中满足约束条件的所有解，而分支限界法 的求解目标则是找出满足约束条件的一个解， 或是在满足约束条件的解中找出在某种意义下 的最优解。
（2）搜索方式的不同：回溯法以深度优先的方 式搜索解空间树，而分支限界法则以广度优先 或以最小耗费优先的方式搜索解空间树。
∞
10 ∞ 3 3 0
20 14 ∞ 15 3
0 2 0 ∞ 12
1 0 2 0 ∞
行归约
13 1 16 12
第 07 章 限 界 剪 枝 法
16
列归约
∞ 12 0 15 11 10 ∞ 3 3 0 17 11 ∞ 12 0 0 2 0 ∞ 12 1 0 2 0 ∞
归约数为：10+2+2+3+4+1+3 = 25
《算法设计与分析》
第6章 限界剪枝法
第六章
本章主要知识点
• • •
分支限界法
6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.3 装载问题
•
• • • • •
6.4 布线问题
6.5 6.6 6.7 6.8 6.9 0－1背包问题 最大团问题 旅行售货员问题 电路板排列问题 批处理作业调度

算法描述

procedure LC (T,C) ( EMPTY(Q)在Q为空时返回true，否则返回false。) begin if T 的根是一个回答结点 then 输出T的根 else begin MAKENULL (Q); 计算C（T）’; INSERT(T,Q); while not EMPTY(Q) do 第 begin e: = DELETEMIN (Q)； 07 for e 的每个儿子结点 x do 章 if x满足约束条件then begin if x 是回答结点 then 限 begin 输出从T到x的逆路径; return; end ； 界 计算C(x)＇；INSERT(x,Q); x ↑. parent =e; 剪 end ; end； 枝 print“没有回答结点” 法 end; end；
最小耗费搜索法

第 07 章 限 界 剪 枝 法
最小耗费搜索法 最小耗费搜索法的算法描述 设T为状态空间树的根结点；~C(x)为耗费估计函数；初 始化优先队列Q； 计算~C(T)，并将T入队； 对活结点表中的任一结点x，有 循环，直到队列Q空（无解）： ~C(e)≤~C(x)， 结点e出队； 对x分枝中的任一解结点y，有 若e是回答结点，则 ~C(x)≤C(y)=D(y)， 输出解或求解路径，求解结束； 又知：~C(e)=C(e)=D(e)，则 否则 D(e)≤D(y)。 检查e的所有子结点x： 若x满足约束条件，则 计算~C(x)，并将x入队； 记录搜索路径； 当~C(x)满足：~C(x)≤C(x)，C(x)单调，解结点的 ~C(x)=C(x)时，上述算法可以正确找到C(x)的最小耗费解；
限界剪枝法
第 07 章 限 界 剪 枝 法

限界与剪枝

为了进一步避免无效搜索，若能找到最优解的耗费上界U，即 对于最优解结点x*，有C(x*)≤U，则： 在进行最小耗费搜索时，对于待展开的状态结点y，若 ~C(y)>U，则由C(x)的单调性和~C(x)是C(x)的下界可知： U<~C(y)≤C(y)≤C(x) x为解结点 即，在y的子树中不会包含所要求的最优解结点x*，因而可以 放弃对该子树的搜索。
3. 常见的两种分支限界法
（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩 展节点。 （2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点 成为当前扩展节点。
基本思想
第 07 章 限 界 剪 枝 法
1、以回溯为基础，求最优解 2、启发式搜索 3、提前剪去不含最优解的分枝
第 07 章 限 界 剪 枝 法
旅行售货员问题
从状态空间树的根出发，定义非根 结点x的估值函数如下：
若x不是解结点，则：

设x的父结点y的归约矩阵Ay，

第 07 章 限 界 剪 枝 法
设x是由加入边(i,j)得到的，则将Ay的 第i行和第j列均置为∞，以避免选入 其他以i为起点和以j为终点的边； 将Aj1置为∞，以避免选入(j,1)； 如此得到的矩阵就是x的归约矩阵Ax， 归约于Ax的归约数为rx，则定义： ~C(x) = ~C(y)+r9;
游路线的耗费以r为下界。
第 07 章 限 界 剪 枝 法

因此，约数r可用来作为状态空 间树根结点的估值函数值。即令 C＇(T)＝r，而C＇是根结点对应 的归约矩阵。

第 07 章 限 界 剪 枝 法
对于状态空间树中的其他任 意结点x，我们也可建立与之相 应的C＇(x)和相应的归约矩阵。 设y是任一非叶结点，Ay是与结 点y相对应的归约矩阵，x是y的 儿子结点，状态空间树中的边(y ，x)对应于选择图G的边(y,x)加 入周游路线。
∞
∞
5
7
14
∞
9
10
∞
5
∞
12
最小耗费搜索法
第 07 章 限 界 剪 枝 法

下界估值函数~C(x)

~C(x)是C(x)的下界估值

~C(x)可即时计算
当x为解结点时，~C(x)=C(x)=D(x)

下界估值越小，分枝含有最优解的可能越大。 优先搜索下界估值最小的结点，则第一个待扩展的解结点为最优解。
限界剪枝法
第 07 章 限 界 剪 枝 法

限界与剪枝




基于以上思想，引入耗费函数的上界函数u(x)， 满足：~C(x)≤C(x)≤u(x)；和当前最小上界值U； 初始时令U=u(T)，T为起始结点； 在符合约束条件的结点x入队前，检查，若 ~C(x)>U，则该结点不入队（不激活）； 在结点x入队时，检查，若u(x)<U，则用u(x)更新 U（使U动态单调下降）； 在活动结点x出队后，检查，若~C(x)>U，则不须 对x进行扩展，避免无效搜索；
2. 限界剪枝法基本思想
分支限界法常以广度优先或以最小耗费（最大效益）优先的方 式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这 些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃， 其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上 述结点扩展过程。这个过程一直持续到找到所需的解或活结点表 为空时为止。
最小耗费搜索法

最小耗费搜索法

第 07 章 限 界 剪 枝 法
15迷问题

用布局作为问题状态，用空格的移动来表述状态的演化； 用根结点到解结点的路径长度作为耗费函数； 而用根到当前结点的路径长度加上当前结点与目标解的差异量作 为耗费估计函数；
1
3
4
15
1 5 9 13
2 6 10 14
3 7 11 15
第 07 章 限 界 剪 枝 法



限界剪枝法

旅行售货员问题

第 07 章 限 界 剪 枝 法
为了定义C(x)的下界~C(x)，引入权值矩阵的归约矩阵：

从权值矩阵的每一行（列）中减去该行（列）的最小值，称为 对行（列）的归约，被减去的最小值称为该行（列）的约数； 对一个矩阵的行和列都做归约，称为原矩阵的归约矩阵，行列 约数之和称为原矩阵的约数，记为r ；