第08章 分支与限界

1第八章分支与限界8.1分支与限界法的基本思想

8.2作业分配问题

8.3单源最短路径问题

8.40/1背包问题

2l_结点（活结点）：所搜索到的结点不是叶结点，且满足约束条件和目标函数的界，其儿子结点还未全部搜索完毕e_结点（扩展结点）：正在搜索其儿子结点的结点，它也是一个l_结点；d_结点（死结点）：不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结点、或者叶结点。以d_结点作为根的子树，可以在搜索过程中删除

一基本思想8.1分支与限界法的基本思想3一基本思想1.在e_结点估算沿着它的各儿子结点搜索时，目标函数可能取得的“界”，2.把儿子结点和目标函数可能取得的“界”，保存在优先队列或堆中，3.从队列或堆中选取“界”最大或最小的结点向下搜索，直到叶子结点，4.若叶子结点的目标函数的值，是结点表中的最大值或最小值，则沿叶子结点到根结点的路径所确定的解，就是问题的最优解，否则转3继续搜索8.1分支与限界法的基本思想4二目标函数“界”的特性

是局部解是相应的界1.对最小值问题，称为下界，意思是向下搜索所可能取得的值最小不会小于这些下界若是所得到的局部解，满足：

2.对最大值问题，称为上界，意思是向下搜索所可能取得的值最大不会大于这些上界若是所得到的部分解，满足：5三两种分支方法设解向量，的取值范围为有穷集，1in1.每棵子树都有个分支：最坏情况下，结点表的空间为若状态空间树是完全n叉树，结点表的空间为2.每棵子树只有两个分支，取特定值的分支、及不取特定值的分支：状态空间树是完全二叉树，最坏情况下结点表的空间为6一分支限界法解作业分配问题的思想方法1.问题描述：

n个操作员以n种不同时间完成n种不同作业。要求分配每位操作员完成一项工作，使完成n项工作的总时间最少操作员编号为0,1,…n-1，作业也编号为0,1,…n-1，矩阵c描述每位操作员完成每个作业时所需的时间，元素ci,j表示第i位操作员完成第j号作业所需的时间向量x描述分配给操作员的作业编号，分量xi表示分配给第i位操作员的作业编号。8.2作业分配问题7一分支限界法解作业分配问题的思想方法2.思想方法：

1）从根结点开始，每遇到一个e_结点，就对它的所有儿子结点计算其下界，把它们登记在结点表中。

2）从表中选取下界最小的结点，重复上述过程。

3）当搜索到一个叶子结点时，如果该结点的下界是结点表中最小的，那么，该结点就是问题的最优解。

4）否则，对下界最小的结点继续进行扩展

8一分支限界法解作业分配问题的思想方法3.下界的确定：

1）搜索深度为0时，把第0号作业分配给第i位操作员所需时间至少为第i位操作员完成第0号作业所需时间，加上其余n-1个作业分别由其余n-1位操作员单独完成时所需最短时间之和，有：

9一分支限界法解作业分配问题的思想方法3.下界的确定：例：4个操作员完成4个作业所需的时间表如下：

把第0号作业分配给第0位操作员时，所需时间至少不会小于3+7+6+3=1910一分支限界法解作业分配问题的思想方法3.下界的确定：

2）搜索深度为k时，前面第0,1,,k-1号作业已分别分配

给编号为i0,i1,,ik-1的操作员。S={0,1,,n-1}表示所有操作员的编号集合；mk-1={i0,i1,,ik-1}表示作业已分配的操作员编号集合。

当把第k号作业分配给编号为ik的操作员时，ikS-mk-1，

所需时间至少为：(8.2.1)

则上式为把第k号作业分配给编号为ik的操作员时的下界11一分支限界法解作业分配问题的思想方法4.算法实现步骤：

每个结点都包含已分配作业的操作员编号集合m、

未分配作业的操作员编号集合

S、

操作员的分配方案向量x、搜索深度

k、所需时间的下界t1）建立根结点X，令X.k=0，X.S={0,1,n-1}

，X.m=

把当前问题的可行解的最优时间下界bound置为∞。2）对所有编号为

i的操作员，iX.S

，建立儿子结点

Yi，

把结点X的数据复制到结点

Yi。3）令Yi.m=Yi.m{i}，Yi.S=Yi.S-{i}

，Yi.x=Yi.k，Yi.k=Yi.k+1，按式（8.2.1）计算

Yi.t。12一分支限界法解作业分配问题的思想方法4.算法实现步骤：4）如果Yi.t<buond，转步骤5），否则剪去结点Yi

，转

步骤6）。5）把结点

Yi插入优先队列。如果结点

Yi是叶结点，表明它

是问题的一个可行解，用

Yi.t更新当前可行解的最优时

间下界bound。（6）取下队列首元素作为子树的根结点X，若

X.k=n，则该

结点是叶结点，表明它是问题的最优解，算法结束，向

量X.x便是作业最优分配分案；否则，转步骤2）。13一分支限界法解作业分配问题的思想方法例：图8.1所示的4个操作员的作业最优分配方案的搜索树。14一分支限界法解作业分配问题的思想方法下界的确定：

则上式为把第k号作业分配给编号为ik的操作员时的下界求下面作业分配问题：

0123

0123

7344

6488

5133

371615一分支限界法解单源最短路径问题的思想方法1.问题描述：给定有向赋权图G=(V,E)，图中每一条边都具有非负长度，求从源顶点s到目标顶点t的最短路径问题

2.思想方法：把源顶点s作为根结点开始进行搜索。对源顶点s的所有邻接顶点，都产生一个分支结点，估计从源点s经该邻接顶点到达目标顶点的距离作为该分支结点的下界，选择下界最小的分支结点，对这个分支结点所对应的顶点的所有邻接顶点继续进行上述的搜索。

8.3单源最短路径问题

16一分支限界法解单源最短路径问题的思想方法3.下界的确定：假定d(node)是搜索树中从根结点到结点

node所对应的顶点

u的路径长度，顶点

u的邻接顶点为v1,v2,vi

，而

cu,vi为顶点

u到其邻接顶点

vi的距离。令

（8.3.1）

则结点

的下界

可表示为：

17一分支限界法解单源最短路径问题的思想方法4.结点内部数据的描述：顶点编号为0,1,，n-1

搜索树中结点的数据结构：structpath_node{int u; /*该结点所对应的顶点*/int path[n]; /*从源点开始的路径上顶点编号*/int k; /*当前搜索深度下,路径上的顶点个数*/int d；

/*从源点到本结点所对应顶点的路径长度*/floatb; /*经本结点到目标顶点最短路径长度下界*/structpath_node*next；};typedefstructpath_nodePATH_NODE;

18一分支限界法解单源最短路径问题的思想方法5.算法步骤：假定源顶点为s，目标顶点为

t，

1）初始化：建立根结点X，令根结点的X.u=s，X.k=1，X.path[0]=s，X.d=0，X.b=0，当前可行解的最短路径

下界

bound置为∞。

2）令顶点X.u所对应的顶点为u，对

u的所有邻接顶点vi

建立儿子结点

Yi，把结点

X的数据复制到结点

Yi。

3）令Yi.u=vi

，Yi.path[yi.k]=vi

，Yi.k=Yi.k+1，Yi.d=Yi.d+cu,vi

，对顶点

vi按式（8.3.1）和式（8.3.2）

计算

h和Yi.b。19一分支限界法解单源最短路径问题的思想方法5.算法步骤：

4）如果Yi.b<bound，转步骤5），否则剪去结点

Yi，转

步骤6）。

5）把结点

Yi插入优先队列。如果结点

Yi.u=t，表明它是问

题的一个可行解，用

Yi.b更新当前可行解的最短路径长

度下界

bound。

6）取下优先队列首元素作为子树的根结点

X，若X.u=t，

表明它是问题的最优解，算法结束，数组

X.path存放

从源点

s到目标顶点

t的最短路径上的顶点编号，X.d

存放该路径的长度；否则，转步骤（2）。20一分支限界法解单源最短路径问题的思想方法

21一分支限界法解单源最短路径问题的思想方法例

图8.5表示用分支限界法求图8.3所示有向图的从源点

到目标顶点

的最短路径的搜索过程。

22下界的确定：假定d(node)是搜索树中从根结点到结点

node所对应的顶点

u的路径长度，顶点

u的邻接顶点为v1,v2,vl

，而

cu,vi为顶点

u到其邻接顶点

vi的距离。令

（8.3.1）

则结点

的下界

可表示为：

画出搜索树，在节点旁标出相应的的下届，写出最后的最优解。231.思想方法

2.求解过程8.40/1背包问题

241.思想方法1）分支选择及物体分类

①

n个物体按价值重量比递减顺序排序后，重量分别为，价值分别为，物体序号集合为S={0,1,,n–1}，背包载重量为M②按物体价值重量比递减顺序（集合S中物体的顺序号）把物体k装入背包或不装入背包进行分支搜索③物体划分为三类：当搜索深度为k时确定装入背包的物体集合，确定不装入背包的物体集合，尚待选择的物体集合，

252）分支时的处理①

搜索深度为k+1时，被搜索物体序号就是集合S中的元素k②把物体装入背包的分支结点的处理：③不把物体装入背包的分支结点的处理：

263）上界的确定

①b(k)：搜索深度为k时，分支结点的背包中物体价值上界②若：令b(k)=0③若：则：272.求解过程1）把物体按价值重量比递减顺序排序2）建立根结点X，