[工学]经典算法分析与设计教学案例.ppt

第3章 动态规划 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉有哪些信誉好的足球投注网站树。 动态规划解决问题的基本特征 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 例题一：排队买票问题 一场演唱会即将举行。现有 n 个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第 i 位歌迷买一张票需要时间Ti（1≤i≤n），队伍中相邻的两位歌迷（第 j 个人和第 j+1 个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为 Rj，假如 RjTj+Tj+1，这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程。现给出 n, Tj和 Rj，求使每个人都买到票的最短时间和方法。 最大子段和 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]的最大子段和为下面的形式。 A、B这两种情形可递归求得。对于情形C，容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，我们可以在a[1:n/2]和a[n/2+1:n]中分别计算出如下的s1和s2。则s1+s2即为出现情形C使得最优值。 int MaxSubSum(int a, int left, int right) { int sum=0; if (left==right)sum=a[left]0?a[left]:0; else{int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0; for (int i=center;i=left;i--) { lefts+=a[i]; if (leftss1) s1=lefts; } int s2=0;rights=0; for (int i=center+1;i=right;i++) { rights+=a[i]; if (rightss2) s2=rights; } sum=s1+s2; if (sumleftsum) sum=leftsum; if (sumsightsum) sum=rightsum; } return sum; } 最大子段和 3. 动态规划方法求解 在对上述分治算法的分析中我们注意到， 由bj的定义易知， 当bj-10 时 bj=bj-1+aj，