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

上海海洋大学信息学院2009-12-2第7讲分支限界法上海海洋大学信息学院2009-12-27.1概述7.2复杂的有限作业调度问题7.3货郎担问题的分支限界法上海海洋大学信息学院2009-12-27.1概述上海海洋大学信息学院2009-12-2分枝限界法概述采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，并将它们一一加入活结点表，此时R自身成为死结点。算法从活结点表中另选一个活结点作为E-结点。上海海洋大学信息学院2009-12-2不同的活结点表形成不同的分枝限界法，分为：FIFO分枝限界法、LIFO分枝限界法和LC（leastcost）分枝限界法。三种不同的活结点表，规定了从活结点表中选取下一个E-结点的不同次序。FIFO分枝限界法的活结点表是先进先出队列LIFO分枝限界法的活结点表是堆栈；LC分枝限界法的活结点表是优先权队列，LC分枝限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。上海海洋大学信息学院2009-12-2例(4-皇后问题)FIFO分枝限界法求解上海海洋大学信息学院2009-12-2分枝限界算法templateclassTstructNode{Tcost;Node*parent;}上海海洋大学信息学院2009-12-2templateclassTvoidBranchBound(NodeT*t){LiveListNodeT*lst(mSize);NodeT*x,*E=t;do{for(对结点E的每个不受限的孩子){x=newNode;x-parent=E;if(x是一个答案结点){输出从x到t的一条路径；return;}lst.Append(x);}上海海洋大学信息学院2009-12-2if(lst.IsEmpty()){cout“没有答案结点”；return；}lst.Serve(E);//从lst输出一个活结点为E-结点}while（1）；}上海海洋大学信息学院2009-12-2LC分枝限界法代价函数c(·)若X是答案结点，则c(X)是从根结点到X的搜索代价；若X不是答案结点且子树X上不含任何答案结点，则c(X)=；若X不是答案结点但子树X上包含答案结点，则c(X)等于子树X上具有最小搜索代价的答案结点的代价。上海海洋大学信息学院2009-12-2相对代价函数g(·)衡量一个结点X的相对代价一般有两种标准：①在生成一个答案结点之前，子树X上需要生成的结点数目；②在子树X上，离X最近的答案结点到X的路径长度。容易看出，如果采用标准①，总是生成最小数目的结点；如果采用标准②，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。上海海洋大学信息学院2009-12-2假设状态空间树上含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)。代价估计函数ĉ(.)ĉ(X)是代价估计函数，它由两部分组成：从根到X的代价f(X)和从X到答案结点的估计代价ĝ(X)，即ĉ(X)=f(X)+ĝ(X)。一般而言，可令f(X)等于X在树中的层次。上海海洋大学信息学院2009-12-27.2复杂的有限作业调度问题上海海洋大学信息学院2009-12-2问题描述对于单处理机的带时限作业排序问题，如果每个作业具有相同的处理时间，则可以用贪心法求解。如果每个作业的处理时间允许不同，带时限的作业排序问题可描述为：设有n个作业和一台处理机，每个作业所需的处理时间、要求的时限和收益可用三元组（ti,di,pi），0≤i＜n表示，其中，作业i的所需时间为ti，如果作业i能够在时限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为作业编号。问题的显式约束为：xi{0,1,…,n1}且xi＜xi+1(0≤i＜n1)，隐式约束为：对于选入子集J的作业（x0,x1,…,xk），存在一种作业排列使J中作业均能如期完成。问题的目标函数是作业子集J中所有作业所获取的收益之和，使得总收益最大的作业子集是问题的最优解。如果希望以最小值为最优解，则可以适当改变目标函数，将其改为未入选子集J的作业所导致的损失，即为：}pmin{1..nJ,iii上海海洋大学信息学院2009-12-2ĉ(X)u(X)ĉ(X)c(X)u(X)}J{i|imax,mpmJ,iii1,...,nmiimJ,iii1..nJ,iiippp上海海洋大学信息学院2009-12-2可变大小元组状态空间树上海海洋大学信息学院2009-12-27.3货郎担问题的分支限界法上海海洋大学信息学院2009-12-2问题描述旅行商问题（travellingsalesperson）是一个看似简单其实十分难解的著名难题之一，至今仍有许多人在研究它。此问题描述为：一个旅行商准备到n个村庄售货。他从A村出发经过其它n-1个村庄，又回到出发地A村。现要求一条最短路径，使得每个村庄都经过且仅经过一次。上海海洋大学信息学院2009-12-2分枝限界法求解设带权有向图G=(V,E)，|V|=n，表示连接n个村庄的道路交通图，边上的权值为两个村庄间的路程，c[n][n]是该图的邻接矩阵，下面也称代价矩阵。旅行商问题的解是一条回路：（x0,x1,,xn1,xn），x0=xn，0xin；xixj，当ij和i,j0,n；xi，xi+1E，0in-1。其状态空间树结构见下页图中的例子。图中采用的解结构形式为（x1,,xn-1），这里假定x0＝xn＝0。本问题的目标函数是路径长度。上海海洋大学信息学院2009-12-2上海海洋大学信息学院2009-12-2归约代价矩阵定义7-1如果矩阵的一行（或列）中至少包含一个零且其余元素均非负，则称此行（或列）已归约。定义7-2如果一个矩阵的所有行和列均已归约，则称此矩阵为归约矩阵（reducedmatrix）。对矩阵的一行（列）进行归约，可以通过将该行(列)中的每个元素减去该行（列）的最小数进行，此最小数称为该行（列）的约数。通过逐行逐列的归约，可得到一个代价矩阵的归约矩阵。假定第i行的约数为ti，第j列的约数为rj，0i,jn，则所有行和列约数之和称为矩阵约数，设为。1n0jj1n0iirtL上海海洋大学信息学院2009-12-2上海海洋大学信息学院2009-12-21674163186194253241615111030201200110123152030021112101710代价矩阵归约矩阵上海海洋大学信息学院2009-12-21674163186194253241615111030204322101230120153162031021413102010归约行上海海洋大学信息学院2009-12-20003112001101231520300211121017104322101230120153162031021413102010归约列矩阵约数L=25上海海洋大学信息学院2009-12-2下界函数计算方法根结点R的归约矩阵是对邻接矩阵直接归约得到，其下界函数ĉ(R)=L，L是矩阵约数。树中任意非叶状态X的归约矩阵B，可由其双亲状态P的归约矩阵A，先变换成A’后再归约得到B；X的下界函数ĉ(X)=ĉ(P)+A[i][j]+r，r是从A’归约到B的矩阵约数。叶状态S的下界函数ĉ(S)=c(S)，c(S)为从根到S的路径长度。上海海洋大学信息学院2009-12-2上海海洋大学信息学院2009-12-2上界函数对于树中任何状态结点X，令上界函数值u(X)=。上海海洋大学信息学院2009-12-2上海海洋大学信息学院2009-12-2上海海洋大学信息学院2009-12-2上海海洋大学信息学院2009-12-2