算法设计与分析_第10章 算法优化策略.ppt

《算法设计与分析_第10章 算法优化策略.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章算法优化策略1算法设计策略的比较与选择2最大子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为０。依此定义，所求的最优值为:例如:A=(-2，11，-4，13，-5，-2)最大子段和为3简单算法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[

2、k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}thissum+=a[j];注意到，则可将算法中的最后一个for循环省去，避免重复计算只需要O(n2)的计算时间。4分治算法如果将所给的序列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]的最大子段和为，且

3、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)时的最优值。据此可设计出求最大子段和的分治算法。复杂度分析T(n)=O(nlogn)5动态规划算法记，1jn，则所求的最大子段和为当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式b[j]=max{b[j-1]+a[j]，a[j]}，1jn算法显然需要O(n)计算时间和O(n)空间

4、。publicstaticintmaxSum(){intn=a.length-1;intsum=0,b=0;for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;}6最大子矩阵和问题记最大子矩阵和问题的最优值为由于其中，设，则给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。由于解最大子段和问题的动态规划算法需要时间O(n)，故算法的双重for循环需要计算时间O(m2n)。7最大m子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,

5、…,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)。优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1行和第i行的值。因而算法中只要存储数组b的当前行，不必存储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来。计算第i行的值时不必

6、重新计算，节省了计算时间和空间。8动态规划加速原理四边形不等式9货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最优值为m[1，n]。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法10四边形不等式货物储运问题的动态规划递归式是下面更一般的递归计算

7、式的特殊情形。对于,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足时称W关于区间包含关系单调对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即11四边形不等式定义由函数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所需的计算时间为12问题的算法特征13贪心策略采用每次合并集装箱数最少的相

8、邻2堆货物的贪心策略，并不能得到最优解。适当放松相邻