52第10章 算法优化策略

1第10章算法优化策略2算法设计策略的比较与选择3最大子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为０。依此定义，所求的最优值为:例如:A=(-2，11，-4，13，-5，-2)最大子段和为jikkajikknjia1max,0max2042kka4简单算法publicstaticintmaxSum(){intn=a.length-1;intsum=0;for(inti=1;i=n;i++){intthissum=0;for(intj=i;j=n;j++){for(intk=i;k=j;k++)thissum+=a[k];if(thissumsum){sum=thissum;besti=i;bestj=j;}}returnsum;}thissum+=a[j];注意到，则可将算法中的最后一个for循环省去，避免重复计算只需要O(n2)的计算时间。1jikkjikjkaaa5分治算法如果将所给的序列a[1:n]分为长度相等的2段a[1:n/2]和a[n/2+1:n]，分别求出这2段的最大子段和，则a[1:n]的最大子段和有3种情况。(1)a[1:n]的最大子段和与a[1:n/2]最大子段和相同；(2)a[1:n]的最大子段和与a[n/2+1:n]最大子段和相同；(3)a[1:n]的最大子段和为，且1≤i≤n/2，n/2+1≤j≤n。对于情形(3)。容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，可以在a[1:n/2]中计算出，并在a[n/2+1:n]中计算出。则s1＋s2即为出现情形(3)时的最优值。据此可设计出求最大子段和的分治算法。jikka2/2/1][max1niknikasinkninkas12/12/][max2复杂度分析T(n)=O(nlogn)cncnnOnTOnT)()2/(2)1()(6动态规划算法记，1jn，则所求的最大子段和为当b[j-1]0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式}][{max][1jikjikajb][max][maxmax][max1111jbkakanjjikjinjjiknjib[j]=max{b[j-1]+a[j]，a[j]}，1jn算法显然需要O(n)计算时间和O(n)空间。publicstaticintmaxSum(){intn=a.length-1;intsum=0,b=0;for(inti=1;i=n;i++){if(b0)b+=a[i];elseb=a[i];if(bsum)sum=b;}returnsum;}7最大子矩阵和问题记最大子矩阵和问题的最优值为由于其中，设，则给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。2121]][[)2,1,2,1(iiijjjjiajjiis)2,1,2,1(max211211jjiisnjjmii)2,1(max)}2,1,2,1(max{max)2,1,2,1(max211211211211211iitjjiisjjiismiinjjmiinjjmii2121211211]][[max)2,1,2,1(max)2,1(jjjiiinjjnjjjiajjiisiit21]][[][iiijiajb21211][max)2,1(jjjnjjjbiit由于解最大子段和问题的动态规划算法需要时间O(n)，故算法的双重for循环需要计算时间O(m2n)。8最大m子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和达到最大。设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j](1im，ijn)。则所求的最优值显然为与最大子段和问题类似地，计算b(i，j)的递归式为初始时，b(0，j)=0，(1jn);b(i，0)=0，(1im)。),(maxjmbnjm),1(]}[),1(max],[)1,(max{),(1njimijatibjajibjibjti优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1行和第i行的值。因而算法中只要存储数组b的当前行，不必存储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。9动态规划加速原理四边形不等式10货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最优值为m[1，n]。由最优子结构性质可知，jijitajkmkimjimjitjki]}[],[]1,[{min0],[根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法11四边形不等式jijijkmkimjiwjimjki]},[]1,[{min),(0],[货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。对于,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足时称W关于区间包含关系单调对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即)',(),'()','(),(jiwjiwjiwjiw''jjii)',(),'(jiwjiw)',(),'()','(),(jimjimjimjim12四边形不等式定义由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从而)},(),()1,(),(|max{),(jiwjkmkimjimkjiss(i,j)s(i,j+1)s(i+1,j+1)，ij)},()1,({min)},()1,({min),1()1,(jkmkimjkmkimjiskjisjki改进后算法speedDynamicProgramming所需的计算时间为)()),1(),(()1,(),1(121010101nOnOrsnrnsrnOriisriisOnrnrnrrni13问题的算法特征14贪心策略•采用每次合并集装箱数最少的相邻2堆货物的贪心策略，并不能得到最优解。•适当放松相邻性约束，引入相容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。•最小相容结点对a[i]和a[j]是满足下面条件的结点对：（1）结点a[i]和a[j]之间没有方形结点；（2）在所有满足条件（1）的结点中a[i]+a[j]的值最小；（3）在所有满足条件（1）和（2）的结点中下标i最小；（4）在所有满足条件（1）（2）和（3）的结点中下标j最小。•相应的最小相容合并树，如图所示。15相同层序定理相同层序定理：存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。16算法1.组合阶段:将给定的n个数作为方形结点依序从左到右排列，a[1]，a[2]，…，a[n]。反复删除序列中最小相容结点对a[i]和a[j]，(ij)，并在位置i处插入值为a[i]+a[j]的圆形结点，直至序列中只剩下1个结点。O(nlogn)2.标记层序阶段:将第一阶段结束后留下的惟一结点标记为第0层结点。然后以与第一阶段相反的组合顺序标记其余结点的层序。O(n)3.重组阶段:根据标记层序阶段计算出的各结点的层序，按下述规则重组。O(n)结点a[i]和a[j]重组为新结点应满足：（1）a[i]和a[j]在当前序列中相邻；（2）a[i]和a[j]均为当前序列中最大层序结点；（3）在所有满足条件（1）和（2）的结点中，下标i最小。17优化数据结构18带权区间最短路问题S是直线上n个带权区间的集合。从区间IS到区间JS的一条路是S的一个区间序列J(1)，J(2)，…，J(k)，其中J(1)=I，J(k)=J，且对所有1ik-1,J(i)与J(i+1)相交。这条路的长度定义为路上各区间权之和。在所有从I到J的路中，路长最短的路称为从I到J的最短路。带权区间图的单源最短路问题要求计算从S中一个特定的源区间到S中所有其他区间之间的最短路。区间集S(i)的扩展定义为：S(i)T，其中T是满足下面条件的另一区间集。T中任意区间I=[a,b]均有bb(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)…j(k)i，则dist(j(1),i)dist(j(2),i)…dist(j(k),i)。性质6：如果区间I(i)包含区间I(k)（因此ik），且dist(i,i)dist(k,i)，则I(k)是S(i)中的无效区间。性质7：当ik且dist(i,i)dist(k,i-1)时，I(k)是S(i)中的无效区间。性质8：如果区间I(k)(k1)不包含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)←+∞;elsedist(i,i)←dist(j,i-1)+w(i);(2.2):for(ki){if(dist(i,i)dist(k,i-1))dist(k,i)←+∞;elsedist(k,i)←dist(k,i-1);}}步骤3：for(i=2;i=n;i++){if(dist(i,n)=+∞){j=min{k|(dist(k,n)+∞)&&(a(i)b(k))};dist(i,n)=dist(j,n)+w(i);}}上述算法的关键是有效地实现步骤(2.1)和(2.2)