《算法设计与分析》第07讲

1、上海海洋大学信息学院2009-12-2,第7讲 分支限界法,7.1 概述 7.2 复杂的有限作业调度问题 7.3 货郎担问题的分支限界法,上海海洋大学信息学院2009-12-2,上海海洋大学信息学院2009-12-2,7.1 概述,上海海洋大学信息学院2009-12-2,分枝限界法概述,采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，并将它们一一加入活结点表，此时R自身成为死结点。算法从活结点表中另选一个活结点作为E-结点。,不同的活结点表形成不同的分枝限界法，分为：FIFO分

2、枝限界法、LIFO分枝限界法和LC（least cost）分枝限界法。三种不同的活结点表，规定了从活结点表中选取下一个E-结点的不同次序。 FIFO分枝限界法的活结点表是先进先出队列 LIFO分枝限界法的活结点表是堆栈； LC分枝限界法的活结点表是优先权队列，LC分枝限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。,上海海洋大学信息学院2009-12-2,例 (4-皇后问题) FIFO分枝限界法求解,上海海洋大学信息学院2009-12-2,分枝限界算法 template struct Node T cost; Node* parent; ,上海海洋大学信息学院2009-12-2,t

3、emplate void BranchBound(Node* t) LiveList* lst(mSize); Node *x,*E=t; do for( 对结点E的每个不受限的孩子) x=new Node;x-parent=E; if ( x是一个答案结点 ) 输出从x到 t的一条路径；return; lst.Append(x); ,上海海洋大学信息学院2009-12-2,if(lst.IsEmpty() cout“没有答案结点”；return； lst.Serve(E); /从lst输出一个活结点为E-结点 while（1）； ,上海海洋大学信息学院2009-12-2,上海海洋大学信息学院

4、2009-12-2,LC分枝限界法,代价函数c() 若X是答案结点，则c(X)是从根结点到X的搜索代价；若X不是答案结点且子树X上不含任何答案结点，则c(X) = ；若X不是答案结点但子树X上包含答案结点，则c(X)等于子树X上具有最小搜索代价的答案结点的代价。,相对代价函数g() 衡量一个结点X的相对代价一般有两种标准： 在生成一个答案结点之前，子树X上需要生成的结点数目； 在子树X上，离X最近的答案结点到X的路径长度。容易看出，如果采用标准，总是生成最小数目的结点；如果采用标准，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。,上海海洋大学信息学院2009-12-2,假

5、设状态空间树上含A、B、C三个答案结点，且搜索代价为ABC,则： C(T)=C(X)=C(Y)=C(A)=cost(A) C(Z)=C(B)=cost(B) C(W)=C(Q)=C(C)=cost(C) C(U)=C(V)=,若按标准(1),则:g(X)=4,g(Y)=3,g(Z)=2 若按标准(2), 则:g(X)=1,g(Y)=g(Z)=2,上海海洋大学信息学院2009-12-2,相对代价估计函数(.) (X)作为g(X)的估计值，用于估计结点X的相对代价，它是由X到达一个答案结点所需代价的估计函数。一般地，假定(X)满足如下特性：如果Y是X的孩子，则有(Y) (X)。 代价估计函数(.)

6、 (X)是代价估计函数，它由两部分组成：从根到X的代价f(X)和从X到答案结点的估计代价(X)，即(X)=f(X)+ (X)。一般而言，可令f(X)等于X在树中的层次。,上海海洋大学信息学院2009-12-2,7.2 复杂的有限作业调度问题,上海海洋大学信息学院2009-12-2,问题描述,对于单处理机的带时限作业排序问题，如果每个作业具有相同的处理时间，则可以用贪心法求解。如果每个作业的处理时间允许不同，带时限的作业排序问题可描述为：设有n个作业和一台处理机，每个作业所需的处理时间、要求的时限和收益可用三元组（ti, di, pi）， 0in表示，其中，作业i的所需时间为ti，如果作业i能够

7、在时限di内完成，将可收益pi，求使得总收益最大的作业子集J。,上海海洋大学信息学院2009-12-2,例: 设有带时限的作业排序实例：n=4，(p1 , t1, d1)=(5, 1, 1)，(p2 , t2, d2)=(10 , 2, 3)，(p3 , t3, d3)=(6 , 1, 2)和(p4 , t4, d4)=(3, 1, 1)，求使得总收益最大的作业子集J。,上海海洋大学信息学院2009-12-2,分枝限界法求解,可变大小元组（x0, x1, xk）表示解，xi为作业编号。 问题的显式约束为：xi0, 1, n1且xixi+1(0in1)， 隐式约束为：对于选入子集J的作业（x0,

8、 x1, xk），存在一种作业排列使J中作业均能如期完成。问题的目标函数是作业子集J中所有作业所获取的收益之和，使得总收益最大的作业子集是问题的最优解。如果希望以最小值为最优解，则可以适当改变目标函数，将其改为未入选子集J的作业所导致的损失，即为：,上海海洋大学信息学院2009-12-2,(X) u(X) (X) c(X) u(X),上海海洋大学信息学院2009-12-2,可变大小元组状态空间树,上海海洋大学信息学院2009-12-2,上海海洋大学信息学院2009-12-2,7. 3 货郎担问题的分支限界法,上海海洋大学信息学院2009-12-2,问题描述,旅行商问题（travelling s

9、alesperson）是一个看似简单其实十分难解的著名难题之一，至今仍有许多人在研究它。此问题描述为：一个旅行商准备到n个村庄售货。他从A村出发经过其它n-1个村庄，又回到出发地A村。现要求一条最短路径，使得每个村庄都经过且仅经过一次。,分枝限界法求解,设带权有向图G=(V,E)，|V|=n，表示连接n个村庄的道路交通图，边上的权值为两个村庄间的路程，cnn是该图的邻接矩阵，下面也称代价矩阵。 旅行商问题的解是一条回路：（x0,x1,xn1,xn），x0=xn，0 xiE，0in-1。其状态空间树结构见下页图中的例子。图中采用的解结构形式为（x1,xn-1），这里假定x0 xn0。本问题的目标

10、函数是路径长度。,上海海洋大学信息学院2009-12-2,上海海洋大学信息学院2009-12-2,归约代价矩阵 定义7-1 如果矩阵的一行（或列）中至少包含一个零且其余元素均非负，则称此行（或列）已归约。 定义7-2 如果一个矩阵的所有行和列均已归约，则称此矩阵为归约矩阵（reduced matrix）。 对矩阵的一行（列）进行归约，可以通过将该行(列)中的每个元素减去该行（列）的最小数进行，此最小数称为该行（列）的约数。通过逐行逐列的归约，可得到一个代价矩阵的归约矩阵。假定第i行的约数为ti，第j列的约数为rj，0i,jn，则所有行和列约数之和称为矩阵约数，设为 。,上海海洋大学信息学院2009-12-2,上海海洋大学信息学院2009-12-2,代价矩阵 归约矩阵,上海海洋大学信息学院2009-12-2,归约行,上海海洋大学信息学院2009-12-2,归约列,矩阵约数L=25,上海海洋大学信息学院2009-12-2,下界函数计算方法 根结点R的归约矩阵是对邻接矩阵直接归约得到，其下界函数(R)=L，L是矩阵约数。 树中任意非叶状态X的归约矩阵B，可由其双亲状态P的归约矩阵A，先变换成A后再归约得到B；X的下界函数(X)= (P)+Aij+r，r是从A归约到B的矩阵约数。 叶状态S的下界函数(S)=c(S)，c(S)为从根到S的路径长度