动态规划算法 Dynamic Programming

Presentation on theme: "动态规划算法 Dynamic Programming"— Presentation transcript:

1 动态规划算法 Dynamic Programming
万玲

2 1、概述 什么是动态规划? 它能解决哪些问题? 解决的步骤又是什么样的?

3 动态规划（dynamic programming）作为一种多阶段决策优化过程的通用方法，它是在20世纪50年代由一位卓越的美国数学家Richard Bellman所发明的。因此，这个技术名字中的programming是计划和规划的意思，不是代表计算机中的编程。 规划（programming）的含义意味着一系列的决策，而动态（dynammic）的含义则传递着这样一种思想，就是所作的决策可能依赖于当前状态，而与此前所作的决策无关。

4 3.2 举例：最短路径问题 为了找到由A到E的最短路线，可以将该问题分成A-B-C-D-E 4各阶段，在每个阶段都需要作出决策，即在A点需要决策下一步到B1还是B2或B3；同样，若到达第二阶段某个状态，比如B1,需要决定走向C1还是C2；依次类推，可以看出：各个阶段的决策不同，由A到E的路线就不同，当从某个阶段的某个状态发出一个决策，则这个决策不仅影响到下一各阶段的距离，而且直接影响后门各个阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条线路对应的线路最短。

5 算法总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题 n T(n/2) T(n) =

6 算法总体思想 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 n T(n) = n/2 T(n/4)

7 Why Divide and Conquer技术的问题 优化问题 子问题是相互独立的
如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低 优化问题 给定一组约束条件和一个代价函数,在解空间中搜索具有最小或最大代价的优化解 很多优化问题可以分解为多个子问题,子问题相互关联,子问题的解被重复使用

8 What 动态规划的特点 适用范围 把原始问题分为一系列子问题
求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复结算,节约计算时间 自底向上的计算 适用范围 一类优化问题:可分为多个相关子问题,子问题的解被重复使用

9 How 使用动态规划的条件 优化子结构 重叠子问题 当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构
缩小子问题的集合,只要哪些优化问题包含了优化子问题,降低实现复杂性 重叠子问题 在问题的求解过程中,很多子问题的解被多次重复使用

10 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。

11 3.3 矩阵连乘 完全加括号的矩阵连乘积可递归地定义为： 设有四个矩阵 ，它们的维数分别是： 总共有五中完全加括号的方式
设有四个矩阵 ，它们的维数分别是： 总共有五中完全加括号的方式 （1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000, 10500, 36000, 87500, 34500

12 矩阵连乘问题 给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积

13 矩阵连乘问题 给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：

14 矩阵连乘问题 穷举法 动态规划 将矩阵连乘积 简记为A[i:j] ，这里i≤j 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵
Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全 加括号方式为 计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量

15 分析最优解的结构 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

16 建立递归关系 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]
当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n 当i<j时， 可以递归地定义m[i,j]为： 这里 的维数为 的位置只有 种可能

17 计算最优值 对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有
由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法

18 用动态规划法求最优解 public static void matrixChain(int [] p, int [][] m, int [][] s) { int n=p.length-1; for (int i = 1; i <= n; i++) m[i][i] = 0; for (int r = 2; r <= n; r++) for (int i = 1; i <= n - r+1; i++) { int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;} } A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025

19 动态规划算法的基本要素 一、最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。 注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

20 二、重叠子问题 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

21 3.4 0/1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。

22 对于0/1背包问题，可以通过作出变量X1,X2,...,Xi的一个决策序列来得到它的解。而对变量X的决策就是决定它是取0值还是取1值。鉴定决策这些X的次序为Xn,Xn-1,...,X1。在对Xn作出决策之后，问题处于下列两种状态之一： 背包的剩余容量是X=M，没有产生任何价值； 剩余容量是X=M-wn，价值增长了pn。 显然，剩余下来对Xn,Xn-1,...,X1的决策相对于决策X所产生的问题状态应该是最优的，否则Xn,Xn-1,...,X1就不可能是最优决策序列。

23 背包问题的实例分析 考虑以下情况的背包问题， n=3,W=6, (w1,w2,w3)=(2,3,4), (p1,p2,p3)=(1,2,5)
f1(1)=max{f0(1),f0(1-w1)+p1}=0 f1(2)=max{f0(2),f0(2-w1)+p1}=p1=1 f1(3)到f1(6)与f1(2)相同 f2(1)=max{f1(1),f1(1-w2)+p2}=0 f2(2)=max{f1(2),f1(2-w2)+p2}=1 f2(3)=f2(4)=max{f1(3),f1(3-w2)+p2}=2 f2(5)=f2(6)=max{f1(5),f1(5-w2)+2}=3 f3(6)=max{f2(6),f2(6-w3)+p3}=max{3,f1(2)+4}=4

24 0-1背包问题 设所给0-1背包问题的子问题 的最优值为m(i，j)，即m(i，j)是背包容量为j，在前i各物体中，能够装入载重量为j的背包中的物体的最大价值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。

25 动态规划求解0/1背包的算法描述 template<class Type>
Type knapsack_dynamic(int w[],Type p[],int n,int m,BOOL x[]){ int I,j,k; Type v,(*optp)[m+1]=new Type[n+1][m+1]; for(i=0;i<=n;i++){ optp[i][0]=0;x[i]=FALSE;} for(i=0;i<=m;i++) optp[0][i]=0; //初始化

26 动态规划０／１背包算法 for(i=1;i<=n;i++){ ／／计算optp[i[]j] for(j=1;j<=m;j++){
optp[i][j]=optp[i-1][j]; if((j>=w[i])&&(optp[i-1,j-w[i]]+p[i])>optp[i-1][j]) optp[i][j]=optp[i-1,j-w[i]]+p[i]; } j=m; //递推装入背包的物体 for(i=n;i>0;i--){ if(optp[i][j]>optp[i-1][j]){ x[i]=FALSE; j=j-w[i]; } v=optp[n][m]; Delete optp; Return v; }//结束

27 例题 0/1背包问题 有五个物体，其重量分别为2，2 ，6 ，5 ，4，价值分别是6，3，5，4，6，背包的载重量为10，求装入背包的物体及其总价值表。 1 2 3 4 5 6 7 8 9 10 11 14 13 12 15 答案是11001

28 3.5 最长公共子序列 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

29 最长公共子序列的结构 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则
(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

30 子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：

31 计算最优值 由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
Algorithm lcsLength(x,y,b) 1: mx.length-1; 2: ny.length-1; 3: c[i][0]=0; c[0][i]=0; 4: for (int i = 1; i <= m; i++) 5: for (int j = 1; j <= n; j++) 6: if (x[i]==y[j]) 7: c[i][j]=c[i-1][j-1]+1; 8: b[i][j]=1; 9: else if (c[i-1][j]>=c[i][j-1]) 10: c[i][j]=c[i-1][j]; 11: b[i][j]=2; 12: else 13: c[i][j]=c[i][j-1]; 14: b[i][j]=3; 构造最长公共子序列 Algorithm lcs(int i,int j,char [] x,int [][] b) { if (i ==0 || j==0) return; if (b[i][j]== 1){ lcs(i-1,j-1,x,b); System.out.print(x[i]); } else if (b[i][j]== 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b);

32 动态规划 最长公共子序列 例题 求A=xyxzyxyzzy,B=xzyzxyzxyzxy的最长公共子序列。
解：用两个表，来分别用来存放搜索过程中所得到的子序列的长度c[i][j]和状态b[i][j]. 最终得到的最长公共子序列是A(1,2,3,4,6,7,8,10)=xyxzxyzy

33 最长公共子序列的两个存储表 1 2 3 4 5 6 7 8 9 10 11 12 子序列的长度表

34 最长公共子序列的状态表及搜索 1 2 3 4 5 6 7 8 9 10 11 12 ↖ ← ↖ ← ↖ ← ↖ ↑ ↖ ↖ ↖ ← ↑ ↖

35 3.6最大子段和 给定由n个整数(可能为负整数)组成的序列a1,a2,…,an，
求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。 例如，当（a1,a2,a3,a4,a5,a6）={-2,11,-4,13,-5,-2}时，最大子段和为20。

36 简单算法 int MaxSum(int n,int* a) { int max=0; for (int i=1;i<=n;i++)
由题意直接求解，用数组a[]存储给定的n个整a1,a2,…,an。 int MaxSum(int n,int* a) { int max=0; for (int i=1;i<=n;i++) for (int j=I;j<=n;j++) int tmp=0; for (int k=i;k<=j;k++) tmp+=a[k]; if (tmp>max) max=tmp; } return max; 时间复杂度为O(n^3)

37 动态规划算法 若记b[j]为从第i个数加到第j个数的最大值。那么最大字段和就是b[1], b[2],…,b[n]中的最大值。
由b[j]的定义易知，当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。 由此可得计算b[j]的动态规划递归式 b[j]=max{b[j-1]+a[j],a[j]}, 1<=j<=n

38 动态规划代码 int MaxSum(int n,int* a) { int max=0,b=0;
for (int i=1;i<=n;i++) if (b>0) b+=a[i]; else b=a[i]; if (b>max) max=b; } return max;