动态规划算法课件.ppt

1、1 动态规划动态规划3.1 动态规划的设计思想动态规划的设计思想3.2 动态规划的设计要素动态规划的设计要素3.3 动态规划算法动态规划算法的典型应用的典型应用 3.3.1 投资问题投资问题 3.3.2 背包问题背包问题 3.3.3 最长公共子序列最长公共子序列LCS 3.3.4 图像压缩图像压缩 3.3.5 最大子段和最大子段和 3.3.6 最优二分检索树最优二分检索树 3.3.7 生生物信息学中的动态规划算法物信息学中的动态规划算法20-1背包问题的建模背包问题的建模一、一、问题描述问题描述：有有n 个物品，它们有各自的重量和价值，现个物品，它们有各自的重量和价值，现有给定容量的背包，如何

2、让背包里装入的物品具有最大的价值有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？总和？二、二、总体思路总体思路：根据动态规划解题步骤（问题抽象化、建根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填写备忘录表、寻找解组成）找出与小问题的递推关系式、填写备忘录表、寻找解组成）找出0-1背包问题的最优解以及解组成；背包问题的最优解以及解组成；30-1背包问题的建模背包问题的建模实例实例：物品的个数为物品的个数为4个，总重量不超过个，总重量不超过8；i1234重量（重量（

3、w）2345价值（价值（v）34564子问题的界定和计算顺序子问题的界定和计算顺序子问题的界定：有参数子问题的界定：有参数i和和j来界定来界定 i:表示物品的个数表示物品的个数 j :背包总的装重量背包总的装重量原始输入：原始输入：i=4，j=8子问题的计算顺序：子问题的计算顺序：对于给定的对于给定的i=1，看，看j=1,2,3,4.,8的情况的情况; i=2，看，看j=1,2,3,4.,8的情况的情况;50-1背包问题求解过程背包问题求解过程（1） 把背包问题抽象化（把背包问题抽象化（X1，X2，Xn，其中，其中 Xi 取取0或或1，表示第，表示第 i 个物品选或不选），个物品选或不选），V

4、i表示第表示第 i 个物品的价值，个物品的价值，Wi表示第表示第 i 个物品的重量；个物品的重量；（2）建立模型，即求）建立模型，即求max(V1X1+V2X2+VnXn)； （3）约束条件，）约束条件，W1X1+W2X2+WnXn总重量；总重量； （4）定义）定义Fi(j)：当前背包容量：当前背包容量 j，前，前 i 个物品最佳组合对应个物品最佳组合对应的价值；的价值；6寻找递推关系式，面对当前商品有两种可能性：寻找递推关系式，面对当前商品有两种可能性：第一：包的容量比该商品体积小，装不下，此时的价值与第一：包的容量比该商品体积小，装不下，此时的价值与前前i-1个的价值是一样的，即：个的价值

5、是一样的，即：Fi(j)=Fi-1(j)；第二：还有足够的容量可以装该商品，但装了也不一定达第二：还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，到当前最优价值，所以在装与不装之间选择最优的一个，即：即：Fi(j)=maxFi-1(j)，Fi-1(j-w(i)+v(i);0-1背包问题求解过程背包问题求解过程表示不装第表示不装第i个物品个物品装了第装了第i个商品，背个商品，背包容量减少了包容量减少了w(i),但价值增加了但价值增加了v(i)；7由此可以得出递推关系式：由此可以得出递推关系式：（1） j=w(i) ：Fi(j)=maxFi-1(j)，

6、Fi-1(j-w(i)+v(i) ;0-1背包问题求解过程背包问题求解过程8备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i01234567801234考虑初始状考虑初始状态是什么？态是什么？F0(j)=Fi(0)=09备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i012345678000000000010203040考虑初始状考虑初始状态是什么？态是什么？F0(j)=Fi(0)=0100-1背包问题求解过程背包问题求解过程具体分析：具体分析：当当i=1时：时： j=1, w(1)=2, j=w(1), F1(2)=maxF0(2),F0(

7、2-2)+v(1) =max0,0+3=3; j=3, w(1)=2, j=w(1), F1(3)=maxF0(3),F0(3-2)+v(1) =max0,0+3=3; j=4, w(1)=2, j=w(1), F1(4)=maxF0(4),F0(4-2)+v(1) =max0,0+3=3; 11备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i01234567800000000001003333333203040考虑初始状考虑初始状态是什么？态是什么？F0(j)=Fi(0)=0120-1背包问题求解过程背包问题求解过程当当i=2时：时： j=1, w(2)=3, jw

8、(2), F2(1)=F1(1)=0; j=2, w(2)=3, j=w(2), F2(3)=maxF1(3),F1(3-3)+v(2) =max3,0+4=4; j=4, w(2)=3, j=w(2), F2(4)=maxF1(4),F1(4-3)+v(2) =max3,0+4=4;j=5, w(2)=3, j=w(2), F2(5)=maxF1(5),F1(5-3)+v(2) =max3,3+4=7; 13备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i0123456780000000000100333333320034477773040考虑初始状考虑初始状态是什

9、么？态是什么？F0(j)=Fi(0)=014备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i012345678000000000010033333332003447777300345789940考虑初始状考虑初始状态是什么？态是什么？F0(j)=Fi(0)=015备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i012345678000000000010033333332003447777300345789940034578910如何从备忘如何从备忘录得出问题录得出问题的解？的解？16备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求

10、解过程 j i012345678000000000010033333332003447777300345789940034578910如何从备忘如何从备忘录得出问题录得出问题的解？的解？171) 当当Fi(j)=Fi-1(j)时，说明没有选择第时，说明没有选择第i 个商品，则个商品，则回到回到Fi-1(j) ；2) 否则：否则： Fi(j)=Fi-1(j-w(i)+v(i)时，说明装了第时，说明装了第i个个商品，该商品是最优解组成的一部分，随后我们商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到得回到装该商品之前，即回到Fi-1(j-w(i)；3) 一直遍历到一直遍历到i0

11、结束为止，所有解的组成都会结束为止，所有解的组成都会找到。找到。寻解方式：寻解方式：18备忘录表填写：备忘录表填写：0-1背包问题求解过程背包问题求解过程 j i012345678000000000010033333332003447777300345789940034578910第第4个选个选择择第第3个不个不选选第第2个选个选择择第第1个不个不选选解：解：19动态规划算法动态规划算法:0-1背包问题背包问题20动态规划算法动态规划算法:0-1背包问题背包问题21X 的子序列的子序列 Z ：设序列：设序列 X, Z, 若存在若存在 X 的元素构成的下标严格递增序列的元素构成的下标严格递增序列

12、使得使得 ， 则称则称 Z 是是 X 的的子序列子序列X 与与 Y 的的公共子序列公共子序列 Z ：Z 是是 X 和和 Y 的子序列的子序列子序列的长度子序列的长度：子序列的元素个数：子序列的元素个数相关概念相关概念3.3.3 最长公共子序列最长公共子序列 LCS22给定序列给定序列 X=, Y=求求 X 和和 Y 的最长公共子序列的最长公共子序列实例实例问题描述问题描述X: A B C B D A BY: B D C A B A23给定序列给定序列 X=, Y=求求 X 和和 Y 的最长公共子序列的最长公共子序列实例实例问题描述问题描述X: A B C B D A BY: B D C A B

13、 A一个最长公共子序列一个最长公共子序列: B C B A24蛮力算法蛮力算法25子问题边界：子问题边界： X和和Y 起始位置为起始位置为1，X的终止位置是的终止位置是 m，Y 的终止位置是的终止位置是 n，记作，记作 Xi=，Yj=依赖关系：依赖关系： X=, Y=, Z=， 子问题的界定子问题的界定26子问题的依赖关系子问题的依赖关系27令令 X 与与 Y 的子序列的子序列 Xi = ， Yj = Ci,j： Xi 与与 Yj 的的 LCS 的长度的长度递推方程递推方程优化函数的递推方程优化函数的递推方程28标记函数：标记函数：Bi, j, 其值为字符其值为字符 、 ，标记函数标记函数算法

14、算法3.4 LCS(X,Y,m,n) 1. for i1 to m do /行行1-4边界情况边界情况 2. Ci,00 3. for i1 to n do 4. C0,i0 5. for i1 to m do 6 for j1 to n do 7. if Xi=Yj 8. then Ci,jCi 1,j 1+1 9. Bi,j 10. else if Ci 1,j Ci,j 1 11. then Ci,jCi 1,j 12. Bi,j 13. else Ci,jCi,j 1 14. Bi,j29动态规划算法伪代码表示动态规划算法伪代码表示初值初值子问题子问题Xi,Yj30利用标记函数构造解利

15、用标记函数构造解算法算法3.5 Structure Sequence(B, i, j)输入：输入：Bi,j输出：输出：X与与Y的最长公共子序列的最长公共子序列 1. if i=0 or j=0 then return /一个序列为空一个序列为空 2. if Bi,j =“ ” 3. then 输出输出Xi 4. Structure Sequence(B, i1, j1) 5. else if Bi,j=“ ” then Structure Sequence (B, i1, j) 6. else Structure Sequence (B, i, j1) 输入：输入：X=, Y=，优化函数函数：

16、优化函数函数：实例的优化函数表实例的优化函数表实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A01A2B3C4B5D6A7B初始状态是初始状态是什么？什么？实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=02BC2,0=03CC3,0=04BC4,0=05DC5,0=06AC6,0=07BC7,0=0初始状态是初始状态是什么？什么？实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,

17、3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=03CC3,0=04BC4,0=05DC5,0=06AC6,0=07BC7,0=0实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=04BC4,0=05DC5,0=06AC6,0=07BC7,0=0实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0

18、,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=05DC5,0=06AC6,0=07BC7,0=0实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=06AC6,0=07BC

19、7,0=0实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=07BC7,0=0实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1

20、 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=0实例的优化函数表实例的优化函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2

21、 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=011 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0

22、,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=011 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1

23、 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D

24、3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01

25、 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3

26、 3 4 7BC7,0=01 2 2 3 4 4 标记函数表标记函数表Bi,j01 B2 D3 C4 A5 B6 A0C0,0=0C0,1=0 C0,2=0 C0,3=0C0,4=0C0,5=0C0,6=01AC1,0=00 0 0 1 1 1 2BC2,0=01 1 1 1 2 2 3CC3,0=01 1 2 2 2 2 4BC4,0=01 1 2 2 3 3 5DC5,0=01 2 2 2 3 3 6AC6,0=01 2 2 3 3 4 7BC7,0=01 2 2 3 4 4 如何追如何追踪解？踪解？标记函数：标记函数：解：解：X2,X3, X4, X6, 即即 B, C, B, A 实例

27、实例1234561B1,1= B1,2= B1,3= B1,4= B1,5= B1,6= 2B2,1= B2,2= B2,3= B2,4= B2,5= B2,6= 3B3,1= B3,2= B3,3= B3,4= B3,5= B3,6= 4B4,1= B4,2= B4,3= B4,4= B4,5= B4,6= 5B5,1= B5,2= B5,3= B5,4= B5,5= B5,6= 6B6,1= B6,2= B6,3= B6,4= B6,5= B6,6= 7B7,1= B7,2= B7,3= B7,4= B7,5= B7,6= 50算法的时间、空间复杂度算法的时间、空间复杂度51S= 1, 2

28、, 3, 4, 5, 6设集合设集合 S 为排好序的为排好序的 n 个元素个元素 x1x2xn，将这些元素存，将这些元素存储在一棵二叉树的结点上，以查找储在一棵二叉树的结点上，以查找 x 是否在这些数中是否在这些数中. 如果如果 x 不在，确定不在，确定 x 在那个空隙在那个空隙(方结点方结点). 实例：实例：3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L352S= 1, 2, 3, 4, 5, 6，x=3.5检索方法：检索方法：1. 初始，初始，x与根元素比较；与根元素比较；2. x根元素，递归进入右子树；根元素，递归进入右子树；4. x=根

29、元素，算法停止，输出根元素，算法停止，输出x；5. x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不在数组中不在数组中. 3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L353S= 1, 2, 3, 4, 5, 6，x=3.5检索方法：检索方法：1. 初始，初始，x与根元素比较；与根元素比较；2. x根元素，递归进入右子树；根元素，递归进入右子树；4. x=根元素，算法停止，输出根元素，算法停止，输出x；5. x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不在数组中不在数组中. 3.3.6 最优二叉检索树最优二叉检索树42

30、 6 531 L0 L1 L2 L4 L5 L6 L354S= 1, 2, 3, 4, 5, 6，x=3.5检索方法：检索方法：1. 初始，初始，x与根元素比较；与根元素比较；2. x根元素，递归进入右子树；根元素，递归进入右子树；4. x=根元素，算法停止，输出根元素，算法停止，输出x；5. x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不在数组中不在数组中. 3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L355S= 1, 2, 3, 4, 5, 6，x=3.5检索方法：检索方法：1. 初始，初始，x与根元素比较；与根元素比较；2

31、. x根元素，递归进入右子树；根元素，递归进入右子树；4. x=根元素，算法停止，输出根元素，算法停止，输出x；5. x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不在数组中不在数组中. 3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L356S= 1, 2, 3, 4, 5, 6，x=3.5检索方法：检索方法：1. 初始，初始，x与根元素比较；与根元素比较；2. x根元素，递归进入右子树；根元素，递归进入右子树；4. x=根元素，算法停止，输出根元素，算法停止，输出x；5. x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不

32、在数组中不在数组中. 3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L3 3.557空隙：空隙： (- , x1), (x1, x2), , (xn 1, xn), (xn,+ ) , x0= - , xn+1= 给定序列给定序列 S = , x 在在 xi 的概率为的概率为bi , x 在在 (xi , xi+1) 的概率为的概率为ai , S的存取概率分布如下：的存取概率分布如下： P = 数据元素存取概率分布数据元素存取概率分布实例：实例：S=1,2,3,4,5,6P=检索数据的平均时间检索数据的平均时间42 6 531 L0 L1 L2 L4 L5 L6 L3T1m(T1)=1*0.1+2*(0.2+0.05)+3*(0.1+0.2+0.1) +3*(0.04+0.01+0.05+0.02+0.02+0.07)+2*0.04 = 1.8+0.71 =2.51在数据结点在数据结点上的情况上的情况在间隙的情况在间隙的情况检索数据的平均时间检索数据的平均时间216354 L0 L1 L2 L4 L5 L6 L3m(T2)= 1*0.1+2*0.2+3*0.1+4*(0.2+0.05)+5*0.1 +1*0.04+2*0.01+4*(0.05+0.02+0.04)+5*(0.02+0.07) = 2.3+0.95=3.25 T2