《算法设计 教学课件 ppt 作者 郑宇军 石海鹤 陈胜勇 算法设计（第5章）》由会员分享，可在线阅读，更多相关《算法设计 教学课件 ppt 作者 郑宇军 石海鹤 陈胜勇 算法设计（第5章）（35页珍藏版）》请在金锄头文库上搜索。
1、第5章 动态规划法,动态规划法的基本思想 序列和数组问题的动态规划算法 图中的动态规划算法,动态规划法的基本思想 重叠子问题 最优性原则,5.1 动态规划法的基本思想,重叠子问题,Fib(5),斐波那契数列的递归算法,Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(1),Fib(2),Fib(1),5.1 动态规划法的基本思想,重叠子问题,斐波那契数列的动态规划算法,Fib(3),Fib(2),Fib(1),Fib(4),Fib(5),5.1 动态规划法的基本思想,重叠子问题 最优性原则,一个问题的最优解必然包含其子问题的最优解,首尔,北京,上海,西安,成都,重庆
2、,九寨沟,800,820,980,1100,1200,1250,900,1190,500,550,480,5.1 动态规划法的基本思想,重叠子问题 最优性原则,min(首尔,北京) = 800 min(首尔,上海) = 820,首尔,北京,上海,西安,成都,重庆,九寨沟,800,820,980,1100,1200,1250,900,1190,500,550,480,一个问题的最优解必然包含其子问题的最优解,5.1 动态规划法的基本思想,重叠子问题 最优性原则,min(首尔,北京) = 800 min(首尔,上海) = 820 min(首尔,西安) = 1780 min(首尔,重庆) = 172
3、0 min(首尔,成都) = 2000,首尔,北京,上海,西安,成都,重庆,九寨沟,800,820,980,1100,1200,1250,900,1190,500,550,480,一个问题的最优解必然包含其子问题的最优解,5.1 动态规划法的基本思想,重叠子问题 最优性原则,min(首尔,北京) = 800 min(首尔,上海) = 820 min(首尔,西安) = 1780 min(首尔,重庆) = 1720 min(首尔,成都) = 2000 min(首尔,九寨沟) = 2270,首尔,北京,上海,西安,成都,重庆,九寨沟,800,820,980,1100,1200,1250,900,11
4、90,500,550,480,一个问题的最优解必然包含其子问题的最优解,5.2 计算二项式系数,5.2 计算二项式系数,重叠子问题,C(n,k),C(n1,k),C(n1,k1),C(n2,k),C(n2,k1),C(n2,k1),C(n2,k2),C(n3,k),C(n3,k1),C(n3,k1),C(n3,k2),C(n3,k1),C(n3,k2),C(n3,k2),C(n3,k3),5.2 计算二项式系数,重叠子问题,序列和数组问题的动态规划算法 最长连续上升子序列问题 最大子段和问题 最长公共子序列问题,5.3 最长连续上升子序列问题,输入: 一组可比较元素组成的序列 输出: 元素连续
5、上升的最长一段子序列,18,15,12,10,20,16,8,14,24,18,5.3 最长连续上升子序列问题,18,15,12,10,20,16,8,14,24,18,lis(A0n1) = (Max (i,j): 0ijn AiAi+1Aj: |Aij|),O(n2),5.3 最长连续上升子序列问题,18,15,12,10,20,16,8,14,24,18,lis(A0n1) = (Max i: 0in AiAi+1An1: |Ain1|),1,2,1,2,3,1,2,1,2,1,lis(A0n1) = (Max (i,j): 0ijn AiAi+1Aj: |Aij|),O(n2),O(n
6、),5.3 最长连续上升子序列问题,动态规划算法 Algorithm LongestIncSubseq(A: T) begin let n = |A|, lis = lis = 1; for i = 0 to n-2 do if (AiAi+1) then lis 1; else lis lis + 1; if (lislis) then lis lis; return lis; end,5.4 最大子段和问题,输入: 数组A0n1 输出: 元素之和最大的一段子数组,rs(A0n1) (Max i: 0in: sum(Ain1),lis(A0n1) = (Max (i,j): 0ijn: su
7、m(Aij),O(n2),O(n),5.4 最大子段和问题,动态规划算法 Algorithm MaxSum(A: int) begin let n = |A|, a = b = 0; for i = 0 to n-1 do if (b0) then b Ai; else b b + Ai; if (ba) then a b; return a; end,5.4 最大子段和问题,扩展: 二维数组（矩阵）的最大子段（子矩阵）和,5.5 最长公共子序列问题,输入: 序列Am和Bn 输出: 两个序列的最长公共子序列,5.5 最长公共子序列问题,5.5 最长公共子序列问题,Algorithm Longe
8、stComSubseq(A,B: T) begin let m = |A|, n = |B|, X = new Tm; for i = 0 to m do /初始化第0行 if (Ai=B0) then Xi B0; else Xi ; for i = 1 to n1 do /迭代计算第1n行 let Y = new Tm; if (Bi=A0) then Y0 A0 else Y0 ; for j = 1 to m1 do if (Bi=Aj) then Yj (Xj1 Bi); else if (|Xj| = |Yj1|) then Yj Xj; else Yj Yj1; X Y; ret
9、urn Xm-1; end,5.6 矩阵连乘问题,输入: n个矩阵，其中矩阵Ai的行数和列数分别为Mi和Mi+1。 输出: 矩阵连乘所需的最少数乘操作次数,5.6 矩阵连乘问题,A0,A1,A0A1,A2,A3,A1A2,A2A3,A0A1A2,A1A2A3,A0A1A2A3,5.6 矩阵连乘问题,Algorithm MatrixChain(M: int) begin let n = |M|1, S = new intn,n; for i = 0 to n1 do Si,i 0; for i = 1 to n do for j = 0 to ni do Sj,j+i ; for k = 0 t
10、o i1 do Sj,j+i min(Sj,j+i, Sj,j+k + Sj+k+1,j+i + Mj*Mj+k+1*Mj+i+1); return S0,n1; end,图中的动态规划算法 Floyd算法 Warshall算法 Kleen抽象算法,5.7.1 Floyd算法,完全最短路径问题 输入: 一个无向加权图G（以邻接矩阵W表示） 输出: 距离矩阵D，其中Di,j表示图中从顶点i到顶点j的最短距离,5.7.1 Floyd算法,不经过任何中间顶点的最短路径距离,5.7.1 Floyd算法,可经过顶点0为中间顶点的最短路径距离,5.7.1 Floyd算法,可经过顶点0,1为中间顶点的最短路
11、径距离,5.7.1 Floyd算法,可经过顶点0,1,2为中间顶点的最短路径距离,5.7.1 Floyd算法,可经过顶点0,1,2,3为中间顶点的最短路径距离,5.7.1 Floyd算法,Algorithm Floyd(W: int,) begin let n = |W|, D = W; for k = 0 to n1 do for i = 0 to n1 do for j = 0 to n1 do Di,j min(Di,j, Di,k+Dk,j); return D; end,D(k+1)i,j = min(D(k)i,j, D(k)i,k+D(k)k,j), 0kn,5.7.2 Wars
12、hall算法,Algorithm Floyd(W: int,) begin let n = |W|, D = W; for k = 0 to n1 do for i = 0 to n1 do for j = 0 to n1 do Di,j min(Di,j, Di,k+Dk,j); return D; end,D(k+1)i,j = min(D(k)i,j, D(k)i,k+D(k)k,j), 0kn,R(k+1)i,j = R(k)i,j (R(k)i,kR(k)k,j), 0kn,Algorithm Warshall(A: bool,) begin let n = |A|, R = A;
13、for k = 0 to n1 do for i = 0 to n1 do for j = 0 to n1 do Ri,j Ri,j (Ri,k Rk,j); return R; end,5.7.3 抽象Kleen算法,D(k+1)i,j = min(D(k)i,j, D(k)i,k+D(k)k,j), 0kn,R(k+1)i,j = R(k)i,j (R(k)i,kR(k)k,j), 0kn,Algorithm Kleen(A: T,; ,: T*TT) begin let n = |A|, R = A; for k = 0 to n1 do for i = 0 to n1 do for j = 0 to n1 do Ri,j Ri,j (Ri,k Rk,j); return R; end,
