算法课件(七)动态规划.ppt

动态规划法 1 内容 （一）动态规划基础 p斐波那契数列：重复子问题 p数塔问题：记忆化搜索和递推的方法 p多段图问题：无后效性和最优化原理 p动态规划的思想和概念 （二）动态规划典型实例 p矩阵连乘，最长子串， TSP，背包，流水线 调度 2 动态规划基础 3 例1.斐波那契数列问题 n递归求解 n重复/叠子问题 long int Fib_rec(int h)/递归 num+; if (h=1|h=2) return 1; else return (Fib_rec(h-1)+Fib_rec(h-2); 4 方法1：记忆化搜索 int fin; int Fib_memo(int n)/记忆化搜索 if (n = 0 | n = 1) return fin = n; else if (fin != 0) return fin; return fin = Fib_memo(n-1) + Fib_memo(n-2); 5 方法2：递推 long int Fib_ita(int h)/递推 int i,f1,f2,f3; f1=1;f2=1; for (i=3;iright)? (left+aij) : (right+aij); max(1,1,n) max(2,1,n) max(2,2,n) max(3,1,n) max(3,2,n) 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 重叠子问题：计算了 两次18的最大路径。 11 方法3 ：记忆化搜索 int a100100, f100100; int max(int i,int j,int n) int left,right; if (i=n)|(j=n) fij =aij; if (fij != -1) return fij; left=max(i+1,j,n); /左边 right=max(i+1,j+1,n); /右边 return (fij = (leftright)? (left+aij):(right+aij); n算法改进：存储中间计算结果。 该动态规划算法递归实现 记忆化搜索。 12 方法4：递推法 int max_ita(int n) for(int i=N-1;i=1;i-) for(int j=1;j=ai+1j+1)?(ai+1j):(ai+1j+1); return a11; 13 计算过程：动态规划 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 阶段5 阶段4 阶段3 阶段2 (21)(28)(19)(21) (38)(34)(29) (50)(49) (59) 决策 决策 决策 决策 阶段1 59 50 49 38 34 29 21 28 19 21 19 7 10 4 16 14 n动态规划基础（一）动态规划的基本思想 q重叠子问题：由于动态规划的问题有重叠子问题的 特点，为了减少重复计算，对每一个子问题只解一次 ，将其不同阶段的不同状态保存在一个二维数组中。 q多阶段决策：把求解的问题分成许多阶段或多个子 问题，然后按顺序求解各子问题，最后一个子问题就 是初始问题的解（递推求解）。 15 动态规划基础（二） 适用动态规划方法的前提条件 n动态规划算法的问题及决策应该具有两个性质：最优化 原理(或称为最佳原则、最优子结构)、 无后向性。 q无后向性(无后效性)：某阶段状态一旦确定以后， 就不受这个状态以后决策的影响。即某状态以后的过 程不会影响以前的状态，只与当前状态有关。 16 17 n问题的最优解包含着其子问题的最优解，这种性质称为最 优子结构性质。 n在分析问题的最优子结构性质时，所用的方法具有普遍性 ：首先假设由问题的最优解导出的子问题的解不是最优的 ，然后再设法说明在这个假设下可构造出比原问题最优解 更好的解，从而导致矛盾。 n利用问题的最优子结构性质，以自底向上的方式递归地从 子问题的最优解逐步构造出整个问题的最优解。 17 n最优化原理(最优子结构) q9-12-10-18-19 q显然12-10-18-19也是12到最后一层的最大和 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 n无后效性 q如，计算到12的最大和只要考虑到10的最大和与到 6的最大和哪个更大，而不要考虑到10的最大和或者到 6的最大和具体是哪几个数构成的。 18 动态规划基础（三） 动态规划特点：空间换取时间 n递归算法效率低的主要原因是因为进行了大量的重复计算 。而动态规划的基本动机就是充分利用重叠子问题 (Overlapping subproblems)。 n因为动态规划将以前（子问题）计算过的结果都记录下来 ，遇到使用子问题结果的时候只需查表。 n动态规划是一种用空间换取时间的方法。 n因此，动态规划常常因为空间消耗太大而难以实现。 19 备忘录方法和递推方法比较 q备忘录方法：把递归改成递推之后效率大增，但在递推的 程序中，必须要先弄清各问题之间的拓扑关系，有时需要 将无序的问题进行拓扑排序只有保证规模小的问题总 是在规模大的问题之前得以解决，才能进行递推工作。但 有些问题的拓扑排序工作将会十分繁琐，大大增加编程复 杂度。 动态规划基础（四） 20 q于是产生了一种较为折中的算法记忆化搜索。 记忆化搜索和递归一样利用子程序自身调用来实现 递归思想，只不过在工作的过程中模仿递推建立一 个存放答案的数组，把已得出的答案记录下来。这 样，算法既具有了递推的效率，又由于本质是递归 ，所以不用拓扑排序。 p备忘录算法与自底向上动态规划算法有相同的时间 复杂度。 21 动态规划基础（五）：算法设计步骤 n实际应用当中的简化步骤： q分析最优解的性质，并刻划其结构特征。 q递推地定义最优值。 q以自底向上的方式或自顶向下的记忆化方法(备忘 录法)计算出最优值。 q根据计算最优值时得到的信息，构造问题的最优解 。 22 例3. 多段图的最短路问题 因此可以从B反向递推最短路 一条从A到B的最短路径， 其中任何一段都是最短的 明显的阶段性 最优性原理 “最优策略的一部分也是最优的23 24 网络图表示某城市的局部道路分布图。一货运汽车 从S出发，最终到达目的地E。其中Ai(i1，2， 3),Bj(j1，2)和Ck(k1，2)是可供汽车选择的途 经站点，各点连线上的数字表示两个站点问的距离 。问此汽车应走哪条路线，使所经过的路程距离最 短? 24 25 某城市的局部道路分布图 25 26 0 5 8 11 14 17 19 18 21 26 27 结果从S到E最短距离为21共有三条最短路线： (1) (2) (3) 标号法不但给出起点到终点的最短路线和最短距 离，同时也给出每一状态到终点的最短路线及其 最短距离。 27 动态规划典型实例 28 例1. 求两个字符序列的最长公共字符子序列。 其中1i1是X和Y的长度为k十1的公共子序列 。这与Z是X和Y的一个最长公共子序列矛盾。因此，必有zk=xm=yn。 由此可知Zk-1是Xm-1和Yn-1的一个长度为k-1的公共子序列。若Xm-1和 Yn-1有一个长度大于k-1的公共子序列W，则将xm加在其尾部将产生X 和Y的一个长度大于k的公共子序列。此为矛盾。故Zk-1是Xm-1和Yn-1的 一个最长公共子序列。 n由于zkxm，Z是Xm-1和Y的一个公共子序列。若Xm-1和Y有一个长度大 于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列 。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的 一个最长公共子序列。 n这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的 前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构 性质。 33 n当xm = yn时，有一个子问题，即 ：找出Xm 1和Yn 1的最长 公共子序列 n当xm yn时，有两个子问题，即 q找出Xm 1和Y的最长公共子序列 q找出X和Yn 1的最长公共子序列 q两个子问题都包含了同一个子问题(Xm 1, Yn1) 。 因 此，本问题满足子问题重叠性质。 重复子问题 34 35 构造递归关系 n由最长公共子序列问题的最优子结构性质建立子问题最优 值的递归关系。用cij记录序列和的最长公共子序列的长 度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或 j=0时，空序列是Xi和Yj的最长公共子序列。故此时 Cij=0。其它情况下，由最优子结构性质可建立递归关 系如下： q 35 36 构造最长公共子序列（递归） n算法描述： int lcs1(char *str1,int i, char *str2,int j)/递归法 int a,b; if(i=0)|(j=0) return 0; if (str1i=str2j) return lcs1(str1,i-1, str2,j-1)+1; else a=lcs1(str1,i, str2,j-1); b=lcs1(str1,i-1, str2,j); return(ab?a:b); 36 int lcs2(char *str1,int i, char *str2,int j) /记忆化搜索 if (bij!=0) return bij; if(i=0)|(j=0) return bij=0; if (str1i-1=str2j-1) return bij=lcs2(str1,i-1, str2,j- 1)+1; else bij-1=lcs2(str1,i, str2,j-1); bi-1j=lcs2(str1,i-1, str2,j); bij=(bij-1bi-1j?bij-1:bi-1j); return(bij); 37 38 计算最优值（ 递推） n由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此 ，用动态规划算法自底向上地计算最优值能提高算法的效率。 int lcs3(char *str1, char *str2) /动态规划法 int m,n,i,j,i1,j1; m=strlen(str1); n=strlen(str2); for (i=0;i=bij-1)bij=bi-1j; else bij=bij-1; return bmn; 38 000000 000011 011112 012222 012223 012333 012344 算法LCS执行结果 A“zxyxyz“ B“xyyzx“ u 算法LCS可方便地修改成输出最长公共子序列。 u 由于计算表的每一项需要(1)时间，因此算法的时间复杂性 恰好是表的大小(nm)。 定理7.1 最长公共子序列问题的最优解可在(nm)时间得到。 0 1 2 3 4 5 0 1 2 3 4 5 6 A z x y x y z B x y y z x 39 n给定n个矩阵 ， 其中 与 是可乘 的， 。 考察这n个矩阵的连乘积 如何确定计算矩阵连乘积的计算次序，使得依此次序 计算矩阵连乘积需要的乘法次数最少。 例2 n个矩阵连乘问题 40 问题分析 n考察两个矩阵相乘：C=AB。如果矩阵A，B分别是pr和rq 矩阵，则它们的乘积C所用的数乘次数是prq。 n如果有至少3个以上的矩阵连乘，则涉及到乘积次序问题。 u例如：3个矩阵连乘的加括号方法有两种：(A1A2)A3和 A1(A2A3)。 u设A1，A2，A3分别是p0p1，p1p2，p2p3矩阵，则以上两 种乘法次序所用的数乘次数分别为：p0p1p2+p0p2p3和 p0p1p3+p1p2p3。 u如果p0=10, p1=100, p2=5, p3=50, 则两种乘法所用的数乘 次数分别为：7500和75000。可见，由于加括号的方法不同， 使得连乘所用的数乘次数有很大差别。 41 穷举搜索法 n穷举法：列举出所有可能的计算次序，并计算其需要的数 乘次数，从中找出一种数乘次数最少的计算次序。 n算法复杂度分析： q对于n个矩阵的连乘积，设其不同的计算次序为P(n) 。 q由于每种加括号方式都可以分解为两个子矩阵的加 括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推 式： q 42 矩阵连乘的方法数问题 看看矩阵连乘加括号的方法数有多少？ M1 M2 Mi Mi+1 Mn 考虑最后一次乘法的所在位置：可以是 M1 (M2 Mi Mi+1 Mn) 也可以是 (M1 M2)(M3 Mi Mi+1 Mn) 也可以是 也可以是 (M1 M2 Mi) (Mi+1 Mn) 也可以是 也可以是 (M1 M2 Mi Mi+1 Mn-1) Mn 即最后一次乘法的所在位置共有n-1个，按这n-1个位置分类： 43 矩阵连乘的方法数问题 设n个矩阵连乘加括号方法数为an，则a1=1，a2=1，a3=2 , 类型M1 (M2 Mi Mi+1 Mn) 中的方法数共有an-1种; 类型(M1 M2)(M3 Mi Mi+1 Mn)中的方法数共有an-2种; 类型(M1 M2 Mi) (Mi+1 Mn)中的方法数共有aian-i种; 类型(M1 M2 Mi Mi+1 Mn-1) Mn中方法数共有an-1种 故an为上述n-1类的总和：an=an-1+an-2+ +aian-i+ + an-1 令a0=0，则上式可写为an=a0an+a1an-1+a2an-2+ +aian-i+ +an-2a2+an-1a1+ana0 恰好是n阶Catalan数所满足的方程。 44 n4个矩阵相乘的情况。 A1(A2(A3A4) A1(A2A3)A4) (A1A2)(A3A4) A1(A2A3)A4 (A1A2)A3)A4 45 动态规划法 1.分析最优解的结构 q用Ai:j表示连乘积AiAi1Aj，ij。 q分析计算A1:n的最优计算次序。设这个计算次序在 矩阵Ak和Ak+1之间将矩阵链断开，ik0) return cij; if(i=j) return 0; k=i; u=lookupchain(i,i)+lookupchain(i+1,j)+ri*rk+1*rj+1; sij=k; for(k=i;k1;i-) jMax=min(wi-1,c); for(int j=0;j=w1) m1c=max(m1c,m2c-w1+v1); void Traceback(int m,int w,int c,int n,int x) /最优解 for (int i=1;in;i+) if (mic=mi+1c) xi=0; else xi=1; c-=wi; xi=(mnc)?1:0; 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 3 3 4 4 4 4 7 7 7 7 7 7 7 7 7 7 0 0 0 0 3 3 4 4 5 5 7 7 8 8 9 9 9 9 1 1 2 2 0 0