《算法优化策略》PPT课件

《《算法优化策略》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+=

2、a[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)计算时间和

4、O(n)空间。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个整数(可能为负整数)组成的

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

6、计算第i行的值时不必重新计算，节省了计算时间和空间。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堆货物的贪心策略，并不能得到最优解。适当放松相邻