《算法设计与分析》第07章专用课件.ppt

第7章 动态规划法 7.1 一般方法和基本要素 动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。 7.1.1 一般方法 7.1.2 基本要素 7.1.3? 多段图问题 7.1.4 资源分配问题 7.2 每对结点间的最短路径 7.2.1? ?问题描述 7.2.2 动态规划法求解 7.2.3?弗洛伊德算法 7.2.4 算法正确性 7.3 矩阵连乘 7.3.1? 问题描述 7.3.2 动态规划法求解 7.3.3?矩阵连乘算法 7.3.4? 备忘录方法 7.5 最优二叉有哪些信誉好的足球投注网站树 7.5.1 问题描述 7.5.2?动态规划法求解 7.5.3 最优二叉有哪些信誉好的足球投注网站树算法 7.6 0/1背包 7.6.1? 问题描述 7.6.2? 动态规划法求解 7.6.3? 0/1背包算法框架 7.6.5 性能分析 7.7 流水作业调度 7.7.1 问题描述 7.7.2 动态规划法求解 7.7.3 Johnson算法 例题：最大子段和 问题描述： 给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。 依此定义，所求的最优值为： 例如，当(a1,a2, a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)时，最大子段和为： 1. 一个简单算法 一个简单算法： int MaxSum(int n, a, besti, bestj) { int sum=0; for(i=1;i=n;i++) for(j=1;j=n;j++){ int thissum=0; for(k=i;k=j;k++) thissum+=a[k]; if(thissumsum){ sum=thissum; besti=i; bestj=j;} } return sum; } 算法有3重循环，复杂性为O(n3)。 由于有： 算法可作如下改进： int MaxSum(int n, a, besti, bestj) { int sum=0; for(i=1;i=n;i++){ int thissum=0; for(j=i;j=n;j++){ thissum+=a[j]; if(thissumsum){ sum=thissum; besti=i; bestj=j; } } } } 改进后的算法复杂性为O(n2) 。 2. 分治方法求解 从问题的解的结构可以看出，它适合于用分治策略求解： 如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情形： a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； a[1:n]的最大子段和为下面的形式。 2. 分治方法求解 A、B这两种情形可递归求得。对于情形C，容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，我们可以在a[1:n/2]和a[n/2+1:n]中分别计算出如下的s1和s2。则s1+s2即为出现情形C时的最优值。 从而设计出下面所示的分治算法。 3. 动态规划方法求解 在对上述分治算法的分析中我们注意到， 由bj的定义易知，当bj-10时bj=bj-1+aj，否则bj=aj。由此可得计算bj的动态规划递归式bj=max{bj-1+aj，aj}，1≤j≤n。 据此，可设计出求最大子段和的动态规划算法如下： int MaxSum(int n, int a) { int sum=0; b=0; for (i=1;i=n;i++) { if (b0) b+=a[i]; else b=a[i]; if (bsum) sum=b; } return sum; } 显然该算法的计算时间为O(n)。 一组给定的作业的最优完成时间是F(S)的最小值。 OFT表示指非抢先调度最优完成时间 POFT表示抢先调度最优完成时间。 OMFT表示非抢先调