算法优化策略.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1,第,10,章 算法优化策略,2,算法设计策略的比较与选择,3,最大子段和问题,给定由,n,个整数,(,可能为负整数,),组成的序列,a,1,a,2,a,n,求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为。依此定义，所求的最优值为:,例如:,A=(-2,，,11,，,-4,，,13,，,-5,，,-2),最大子段和为,4,简单算法,public static int,maxSum,(),int n=a.length-1;,int sum=0;,for,(int i=1;i=ni+),int thissum=0;,for,(int j=i;j=n;j+),for,(int k=i;ksum),sum=thissum;,besti=i;,bestj=j;,return,sum;,thissum+=aj;,注意到 ，则可将算法中的最后一个,for,循环省去，避免重复计算只需要,O(n,2,),的计算时间。,5,分治算法,如果将所给的序列,a1:n,分为长度相等的,2,段,a1:n/2,和,an/2+1:n,，分别求出这,2,段的最大子段和，则,a1:n,的最大子段和有,3,种情况。,(1)a1:n,的最大子段和与,a1:n/2,最大子段和相同；,(2)a1:n,的最大子段和与,an/2+1:n,最大子段和相同；,(3)a1:n,的最大子段和为 ，且,1in/2,，,n/2+1jn,。,对于情形,(3),。容易看出，,an/2,与,an/2+1,在最优子序列中。因此，可以在,a1:n/2,中计算出 ，并在,an/2+1:n,中计算出 。则,s1,s2,即为出现情形,(3),时的最优值。据此可设计出求最大子段和的分治算法。,复杂度分析,T(n)=,O(nlogn),6,动态规划算法,记 ，,1,j,n,，则所求的最大子段和为,当,bj-10,时,bj=bj-1+aj,，否则,bj=aj,。由此可得计算,bj,的动态规划递归式,bj=maxbj-1+aj,，,aj,，,1,j,n,算法显然需要,O(n),计算时间和,O(n),空间。,public static int,maxSum,(),int n=a.length-1;,int sum=0,b=0;,for,(int i=1;i0)b+=ai;,else,b=ai;,if,(bsum)sum=b;,return,sum;,7,最大子矩阵和问题,记,最大子矩阵和问题的最优值为,由于,其中，,设 ，则,给定一个,m,行,n,列的整数矩阵,a,，试求矩阵,a,的一个子矩阵，使其各元素之和为最大。,由于解最大子段和问题的动态规划算法需要时间,O(n),，故算法的双重,for,循环需要计算时间,O(m,2,n),。,8,最大,m,子段和问题,给定由,n,个整数,(,可能为负整数,),组成的序列,a1,a2,an,以及一个正整数,m,，要求确定序列的,m,个不相交子段，使这,m,个子段的总和达到最大。,设,b(i,，,j),表示数组,a,的前,j,项中,i,个子段和的最大值，且第,i,个子段含,aj(1,i,m,，,i,j,n),。则所求的最优值显然为,与最大子段和问题类似地，计算,b(i,，,j),的递归式为,初始时，,b(0,，,j)=0,，,(1,j,n);b(i,，,0)=0,，,(1,i,m),。,优化：注意到在上述算法中，计算,bij,时只用到数组,b,的第,i-1,行和第,i,行的值因而算法中只要存储数组,b,的当前行，不必存储整个数组。另一方面，,b(i-1,，,t),的值可以在计算第,i-1,行时预先计算并保存起来。计算第,i,行的值时不必重新计算，节省了计算时间和空间。,9,动态规划加速原理,四边形不等式,10,货物储运问题,在一个铁路沿线顺序存放着,n,堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的,2,堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。,设合并,ai:j,，,1ijn,，所需的最少费用为,mi,j,，则原问题的最优值为,m1,，,n,。由最优子结构性质可知，,根据递归式，按通常方法可设计计算,m(i,j),的,O(n,3,),动态规划算法,11,四边形不等式,货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。,对于,当函数,w(i,j),满足,时称,w,满足,四边形不等式,。,当函数,w(i,j),满足,时称,W,关于区间包含关系单调,对于满足四边形不等式的单调函数,w,，可推知由递归式定义的函数,m(i,j),也满足四边形不等式，即,12,四边形不等式,定义,由函数,m(i,j),的四边形不等式性质可推出函数,s(i,j),的单调性，即,根据前面的讨论，当,w,是满足四边形不等式的单调函数时，函数,s(i,j),单调，从而,s(i,j),s(i,j+1),s(i+1,j+1),，,i,j,改进后算法,speedDynamicProgramming,所需的计算时间为,13,问题的算法特征,14,贪心策略,采用每次合并集装箱数最少的相邻,2,堆货物的贪心策略，并不能得到最优解。,适当放松相邻性约束，引入相容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。,最小相容结点对,ai,和,aj,是满足下面条件的结点对：,（,1,）结点,ai,和,aj,之间没有方形结点；,（,2,）在所有满足条件（,1,）的结点中,ai+aj,的值最小；,（,3,）在所有满足条件（,1,）和（,2,）的结点中下标,i,最小；,（,4,）在所有满足条件（,1,）（,2,）和（,3,）的结点中下标,j,最小。,相应的最小相容合并树，如图所示。,15,相同层序定理,相同层序定理,：存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。,根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。,16,算 法,1.,组合阶段,:,将给定的,n,个数作为方形结点依序从左到右排列，,a1,，,a2,，,，,an,。反复删除序列中最小相容结点对,ai,和,aj,，,(ib(i),。,设区间,I(k)(k,i),是区间集S(i),中的一个区间，,1,i,n,。如果对于,S(i),的任意扩展,S(i),T,，当区间,J,T,且在,S(i),T,中有从,I(1),到,J,的路时，在,S(i),T,中从,I(1),到,J,的任一最短路都不含区间,I(k),，则称区间,I(k),是,S(i),中的,无效区间,。若,S(i),中的区间,I(k),不是无效区间则称其为,S(i),中的,有效区间,。,19,带权区间最短路问题,性质,1,：,区间,I(k),是,S(i),中的有效区间，则对任意,k,j,i,，区间,I(k),是,S(j),中的有效区间。另一方面，若区间,I(k),是,S(i),中的无效区间，则对任意,ji,区间,I(k),是,S(j),中的无效区间。,性质,2,：,集合,S(i),中所有有效区间的并覆盖从,a(1),到,b(j),的线段，其中,b(j),是,S(i),的最右有效区间的右端点。,性质,3,：,区间,I(i),是集合,S(i),中的有效区间当且仅当在,S(i),中有一条从,I(1),到,I(i),的路。,性质,4,：,当,ik,且,dist(i,i)dist(k,i),时，,I(k),是,S(i),中的无效区间。,性质,5,：,设,I(j(1),，,I(j(2),，,，,I(j(k),是,S(i),中的有效区间，且,j(1)j(2)k,），且,dist(i,i)k,且,dist(ii)1),不包含,S(k-1),中任一有效区间,I(j),的右端点,b(j),，则对任意,i,k,，,I(k),是,S(i),中的无效区间。,20,带权区间图的最短路算法,算法,shortestIntervalPaths,步骤,1,：,dist(1,1)w(1),；,步骤,2,：,for(i=2;i=n;i+),(2.1):,j=min k|a(i)b(k);1,ki;,if(j,不存在,)dist(i,i)+;,else dist(i,i)dist(j,i-1)+w(i);,(2.2):,for(ki),if(dist(i,i)dist(k,i-1)dist(k,i)+;,else dist(k,i)dist(k,i-1);,步骤,3,：,for(i=2;i=n;i+),if(dist(i,n)=+),j=min k|(dist(k,n)+),dist(i,n)=dist(j,n)+w(i);,上述算法的关键是有效地实现步骤,(2.1),和,(2.2),21,实现方案,1,用一棵平衡搜索树（,2-3,树）存储当前区间集,S(i),中的有效区间。以区间的右端点的值为序。如图所示。,(2.1),的实现对应于平衡搜索树从根到叶的一条路径上的搜索，在最坏情况下需要时间,O(logn),。,(2.2),的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点。在最坏情况下，每删除一个结点需要时间,O(logn),。,综上，算法,shortestIntervalPaths,用平衡搜索树的实现方案，在最坏情况下的计算时间复杂性为,O(nlogn),。,22,实现方案,2,采用并查集结构。用整数,k,表示区间,I(k),1,k,n,。初始时每个元素,k,构成一个单元素集，即集合,k,是,k,，,1,k,n,。,(1),每个当前有效区间,I(k),在集合,k,中。,(2),对每个集合,S(i),，设,L(S(i)=I(k)|I(k),是,S(i),的无效区间，且,I(k),与,S(i),的任一有效区间均不相交,L(S(i),中所有区间均位于,S(i),的所有有效区间并的右侧。,(3),用一个栈,AS,存放当前有效区间,I(i(1),，,I(i(2),，,，,I(i(k),。,I(i(k),是栈顶元素。该栈称为当前有效区间栈。,(4),对于,1,k,n,，记,prev(I(k)=minj|a(k)a,i,由,a,j,+a,k,k,ji,所构成。,private static void,backtrack,(int step),/,解最短加法链问题的标准回溯法,int i,j,k;,if(astep=n)/,找到一条加法链,if(step=1;i-),if(2*aiastep),for(j=i;j=1;j-),k=ai+aj;,astep+1=k;,if(kastep),由于加法链问题的状态空间树的每一个第,k,层结点至少有,k+1,个儿子结点，因此从根结点到第,k,层的任一结点的路径数至少是,k!,。用标准的回溯法只能对较小的构造出最短加法链。,26,迭代搜索法,深度优先搜索,:,算法所搜索到的第一个加法链不一定是最短加法链。,广度优先搜索,:,算法找到的第一个加法链就是最短加法链，但这种方法的空间开销太大。,迭代搜索算法,:,既能保证算法找到的第一个加法链就是最短加法链，又不需要太大的空间开销。其基本思想是控制回溯法的搜索深度,d,，从,d=1,开始搜索，每次搜索后使,d,增,1,，加深搜索深度，直到找到一条加法链为止。,private static void,iterativeDeepening,(),/,逐步深化的迭代搜索算法,best=n+1;,found=false;,lb=2;/,初始迭代搜索深度,while(!found),a1=1;,backtrack(1);,lb+;/,加深搜索深度,对于正整数，记,(n),=,logn,，,v(n)=n,的,2,进制表示中,1,的个数。迄今为止所知道的,l(n),的最好下界是,l(n),lb(n)=,(n)+logv(n),。利用这个下界，可以从深度,lb(n),开始搜索，大大加快了算法的搜索进程。,27,剪枝函数,设,ai,和,aj,是加法链中的两个元素，且,a,i,2,m,a,j,。由于加倍是加法链中元素增大的最快的方式，即,a,i,2a,i-1,，所以从,a,j,到,a,i,至少需要,m+1,步。如果预期在状态空间树,T,的第,d,层找到关于,n,的一条加法链，则以状态空间树第,i,层结点,a,i,为根的子树中，可在第,d,层找到一条加法链的必要条件是,2,d-i,a,i,n,。,当 时，状态空间树中以结点,a,i,为根的子树中不可能在第,d,层之前找到最短加法链。,设在求正整数,n,的最短加法链的逐步深化迭代搜索算法中，当前搜索深度为,d,。且正整数可表示为,n=2,t,(2k+1),，,k0,，则在状态空间树的第,i,层结点,a,i,处的一个剪枝条件是,28,最短加法链长的上界,与加法链问题密切相关的幂树给出了,l(n),的更精确的上界。,假设已定义了幂树,T,的第,k,层结点，则,T,的第,k+1,层结点可定义如下。依从左到右顺序取第,k,层结点,ak,，定义其按从左到右顺序排列的儿子结点为,ak+aj,，,0,jk,。其中,a0,a1,ak,，是从,T,的根到结点,ak,的路径。且,ak+aj,在,T,中未出现过。,含正整数,n,的部分幂树,T,容易在线性时间内用迭代搜索方式构造出来。,29,优化算法,综合前面的讨论，对构造最短加法链的标准回溯法作如下改进。,(1),采用逐步深化迭代搜索策略；,(2),利用,l(n),的下界,lb(n),对迭代深度作精确估计；,(3),采用剪枝函数对问题的状态空间树进行剪枝搜索，加速搜索进程；,(4),用幂树构造,l(n),的精确上界,ub(n),。,当,lb(n)=ub(n),时，幂树给出的加法链已是最短加法链。,当,lb(n)ub(n),时，用改进后的逐步深化迭代搜索算法，从深度,d=lb(n),开始搜索。,