清华大学出版社：《算法设计与分析》课程教学资源（PPT课件讲稿）第10章 算法优化策略

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第10章算法优化策略

1 第10章 算法优化策略

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法设计策略的比较与选择 2

2 算法设计策略的比较与选择

最大子段和问题 RESS 给定由n个整数(可能为负整数)组成的序列a1,a2 a n 求该序列形如Σa的子段和的最大值。当所有整数均为 负整数时定义其最大子段和为0。依此定义,所求的 最优值为 max. max 1≤i≤j≤ 例如: A=(-2,11,-4,13,-5,-2) 最大子段和为∑ak=20

3 最大子段和问题 给定由n个整数(可能为负整数)组成的序列a1 ,a2 ,…,an , 求该序列形如 的子段和的最大值。当所有整数均为 负整数时定义其最大子段和为０。依此定义，所求的 最优值为: 例如: A=(-2，11，-4，13，-5，-2) 最大子段和为 = j k i k a       =    j k i k i j n a 1 max 0, max 20 4 2  = k = ak

清华大学出版社 public static int maxSumO 简单算法 RS/Y PRESS int n=a length-1 int sum=0 for(int i=1; isumi sum=thissum besti=i best= 注意到Σa=a+Σ4,则可将算法 中的最启一个fo循环省去,避 return sum 免重复计算只需要O(n2)的计算 时间。 4

4 public static int maxSum() 简单算法 { int n=a.length-1; int sum=0; for (int i=1;isum) { sum=thissum; besti=i; bestj=j; } } return sum; } thissum+=a[j]; 注意到 ，则可将算法 中的最后一个for循环省去，避 免重复计算只需要O(n2 )的计算 时间。   − = = = + j 1 k i k j k i ak aj a

清华大学出版社 分治算法 RSITY PRESS 如果将所给的序列a[1:n分为长度相等的2段a[1n/2]和 a[n/2+1n],分别求出这2段的最大子段和,则a1n的 最大乙几和2种娃 (1)复杂度分析 O ≤C (2) T(n)= 27(n/2)+O(n)n>c (3) T(n=o(nlogn) sano 对 子序 列中。因此,可以在a1n/2中计算出 ,并在 a[n/2+1n中计算出 。则ss2即为出现 情形(3)时的最优值。据龀可姗计出求最大子段和的分 治算法

5 分治算法 如果将所给的序列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)时的最优值。据此可设计出求最大子段和的分 治算法。 = j k i k a =   = / 2 1 / 2 1 max [ ] n k i i n s a k = + +   = i k n n i n s a k / 2 1 / 2 1 2 max [ ] 复杂度分析 T(n)=O(nlogn) n c n c T n O n O T n      + = 2 ( / 2) ( ) (1) ( )

清华大学出版社 动态规划算法 记b=m1≤j≤n,则所求的最大子段和为 mx∑q=mxmx∑]=mxb 当b1>0时b=b-1+a,否则b=a。由此可得计算b的 动态规划递归式 b]=maxb-1+a],a},1≤j≤n public static int maxSumO int n=a length-1 int sum=0 b=0 for(int i=1; i0)+=a] else b=a0 if (b>sum)sum=b return sum|算法显然需要O()计算时间和o()空间

6 动态规划算法 记 ，1 j n，则所求的最大子段和为 当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的 动态规划递归式 [ ] max{ [ ]} 1 =   = j k i i j b j a k max [ ] max max [ ] max [ ] 1 1 1 1 a k a k b j j n j k i j n i j j k i i j n   =     =     =  = b[j]=max{b[j-1]+a[j]，a[j]}， 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+=a[i]; else b=a[i]; if (b>sum)sum=b; } return sum; }

半大学出版社 最大子矩阵和问题 给定一个m行n列的整数矩阵a,试求矩阵a的一个子矩阵,使其 各元素之和为最大 记s(12,八,12)=∑∑ i=il j=jl 最大子矩阵和问题的最优值为Xmn2,八2) 由于mXm812,几1,12)=mXn{X2(,2,八,12)=mm2) 其中,12)=mB(121,12)=m∑∑ 设小4,则似2)=m 由于解最大子段和问题的动态规划算法需要时间o(n),故算 法的双重for循环需要计算时间O(m2n)

7 最大子矩阵和问题 记 最大子矩阵和问题的最优值为 由于 其中， 设 ，则 给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其 各元素之和为最大。 = = = 2 1 2 1 ( 1, 2, 1, 2) [ ][ ] i i i j j j s i i j j a i j max ( 1, 2, 1, 2) 1 1 2 1 1 2 s i i j j j j n i i m       max ( 1, 2, 1, 2) max { max ( 1, 2, 1, 2)} max ( 1, 2) 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 s i i j j s i i j j t i i i i m j j n i i m j j n i i m                = = = =       = = 2 1 2 1 1 1 2 1 1 2 ( 1, 2) max ( 1, 2, 1, 2) max [ ][ ] j j j i i i j j n j j n t i i s i i j j a i j = = 2 1 [ ] [ ][ ] i i i b j a i j =    = 2 1 1 1 2 ( 1, 2) max [ ] j j j j j n t i i b j 由于解最大子段和问题的动态规划算法需要时间O(n)，故算 法的双重for循环需要计算时间O(m2n)

清华大学出版社 最大m子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及 个正整数m,要求确定序列的m个不相交子段,使这m个子段的总 和达到最大。 设b(i,j表示数组a的前项中个子段和的最大值,且第个子段 含a](1≤i≤m,j≤n)。则所求的最优值显然为mwxb(m 与最大子段和问题类似地,计算b(,〕的递归式为 b(2j)=max{b(i,-1)+a[门,maxb(i-1,t)+a门}(l≤i≤m,i≤j≤n) i-1≤<j 初始时,b(0,j)=0,(1≤j≤n;b(,0)=0,(1≤i≤m)。 优化:注意到在上述算法中,计算b[时只用到数组b的第i-1 行和第行的值。因而算法中只要存储数组b的当前行,不必存 储整个数组。另一方面,b(i-1,t)的值可以在计算第i1行时预 先计算并保存起来。计算第行的值时不必重新计算,节省了计 算时间和空间

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)。 max b(m, j) m jn ( , ) max{ ( , 1) [ ], max ( 1, ) [ ]} (1 , ) 1 b i j b i j a j b i t a j i m i j n i t j = − + − +     −   优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1 行和第i行的值。因而算法中只要存储数组b的当前行，不必存 储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预 先计算并保存起来。计算第i行的值时不必重新计算，节省了计 算时间和空间

清华大学出版社 TSINGHUA UNIVERSITY PRESS 动态规划加速原理 四边形不等式

9 动态规划加速原理 四边形不等式

清华大学出版社 货物储运问题 PRESS 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆,所需的运输费用与新的一堆中集 装箱数成正比。给定各堆的集装箱数,试制定一个运输方案, 使总运输费用最少。 设合并a,1≤jn,所需的最少费用为m[j,则原问题的最 优值为m[1,n]。由最优子结构性质可知, m小=1mnmk-1+m八+叫}1< t=l 根据递归式,按通常方法可设计计算m(i〕)的O(η3)动态规划算法

10 货物储运问题 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集 装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案， 使总运输费用最少。 设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最 优值为m[1，n]。由最优子结构性质可知， i j i j m i k m k j a t m i j j t i i k j  =     − + + = =   min { [ , 1] [ , ] [ ]} 0 [ , ] 根据递归式，按通常方法可设计计算m(i,j)的O(n3 )动态规划算法