《算法分析》7动态规划1分析

1、学习要点学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。通过应用范例学习动态规划算法设计策略。（1）最短路径问题（2）最长公共子序列；（3）矩阵连乘问题（4）图的任意两点间的最短距离（5）流动推销员问题（6）背包问题（7）整数规划问题（8）流水作业调度动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T

2、(n)=但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)问题

3、对象n这一强有力的算法设计技术，广泛应用于求解组合最优化问题。n它不递归调用自身，但问题的基本解通常是用递归函数的形式来说明。n而分治法是直接实现递推的结果，往往会导致不止一次的递归调用n动态规划采用自底向上的方式递推求值，并把中间结果存储起来以便以后用来计算所需要求的解。（事实上是采用了空间换时间的算法）n动态规划可以设计出特别有效的解决许多组合最优化问题。n比如：旅行商问题n有n个城市，城市之间有不等长的道路连接，一个旅行商要走遍所有城市，请找到一条最短的步行方法？n用蛮力算法需要O(n!)n用动态规划可以在O(n2 2n)内解决。简单例子1：Fibonacci序列 无穷数列1，1，2，3

4、，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：110)2() 1(11)(nnnnFnFnF简单例子1：Fibonacci序列第n个Fibonacci数可递归地计算如下：int fibonacci(int n) if (n =3n显然有：T(n)=f(n)，即求f(n) 的时间是f(n)，n而f(n)(n), =1.618.n用自上而下的方法用的是指数时间求出f(n).用自底向上的方法：nint f(int n)n int x=1,y=1,z,j;n for(j=2;j=n;j+) n z=x+y;n x=y;y=z;n n return z;n用自底向上的

5、方法：n 时间复杂度为：O(n),空间复杂度为O(1);n而用递归的自上到下的方法的空间复杂度为0.n即：用O(1)的空间，把复杂度从指数级降到线性。求二项式系数(n,k)n容易证明，求(n,k)的时间复杂度为指数级。n可以用杨辉三角形的方法，求出(n,k)，时间复杂度降为O(n 2)，n为什么？空间复杂度哪？nkknknkknkn0,1110, 1若或杨辉三角形nn=1 1 1nn=2 1 2 1n 1 3 3 1n 1 4 6 4 1n 1 5 10 10 5 1nn=6 1 6 15 20 15 6 1n .nk= 0 1 2 3 4 5 6杨辉三角形nn=1 1 1nn=2 1 2 1

6、n 1 3 3 1n 1 4 6 4 1n 1 5 10 10 5 1nn=6 1 6 15 20 15 6 1n .nk= 0 1 2 3 4 5 6C:nint f(int n,int k)n int x,y,an+1,bn+1;n if (n=0|k0) return 1;n if(k=0|k=n) return 1;n for(x=0;xn+1;x+) ax=bx=0;n a0=1;a1=1;n for(x=1;xn;x+) /* ?*/n a0=b0=1;n for(y=1;y n;y+) /* ?*/n by=ay-1+ay;n n for(y=0;yn+1;y+) ay=by;n

7、 n return bk;n常用名词：n状态：对于一个问题，所有可能到达的情况n状态变量：对每个状态K关联一个状态变量Sk ，n它的值表示状态K所对应的问题的当前解值。n决策：是一种选择，对于每一个状态，都可以选择一种方法，从而到达下一个状态n决策变量：在状态K下的决策变量Dk的值表示状态K当前所做出的决策n策略：一个决策 的集合，满足某些最优条件的策略称为最优策略n状态转移函数(T)：从一个状态到另一个状态，可以依据一定的规则来前进，我们用一个函数T来描述这样的规划，它将状态I和决策变量Dij映射到另一个状态j n状态转移方程：n注意：有限个状态变量，每个状态变量取有限个不同的值。这样，总的

8、状态个数为有限。n毕竟：人类只能处理有限的事物（有限时间）最优化原理：n1951年，美国数学家R.Bellman等人，提出 了最优化原理：n 一个最大优策略的子策略，对于它的初态和终态而言也必是最优的。n动态规划思想利用了最优化原理。n最优化原理是动态规划的基础。使用动态规划算法的条件n可用动态规划来解决的问题，要符合如个条件：n1.满足最优化原理n2.状态满足无后效性n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。n动态规划的两种不同的思维法：n逆向思维法n正向思维法最短路径问题n从A0点出发，要铺设一条管道

9、到A6点。中间必须经过5个中间站，每个中间站都有若干个候选站，第一站可以从A1，B1两地中任选 一个，第二站从A2，B2,C2，D2中任选一个，第三站从A3，B3，C3中任选一个，第四站从A4，B4，C4中任选一个，第五站从A5，B5中任选一个，连接两地间距离的连线上数字表示，求总距离最短？A0B1A1D2C2B2A2C3B3A3C4B4A4B5A5A6特征分析n有指定的起点与终点，中间站之间的先后顺序是固定的n每个中间站有若干个中间站n最短路径上的每个点到终点都是最短的穷举法分析n用穷举法：n 状态空间数：1*2*3*2*2*2*1=48n 计算48条，每条的包含5个线段，所以要进行240次

10、加法n 从48条中，找到最短的一条，要进行47次比较。动态规划法：nf(Ai)表示从 Ai点到终点站A6的最短距离n其中：0=i5nf(A5)=4， f(B5)=3nf(A4)=mind(A4,A5)+ f(A5),d(A4,B5)+ f(B5)n =min3+4,5+3n =min7,8n =7nf(B4)= mind(B4,A5)+ f(A5),d(B4,B5)+ f(B5)n =min5+4,2+3=5nf(C4)=9nf(A3)=7nf(B3)=8nf(C3)=8nf(A2)=13nf(B2)=10nf(C2)=9nf(D2)=12nf(A1)=13nf(B1)=16nf(A0)=18A0-18A1-16A1-13A2-12A2-9A2-10A2-13A3-8A3-6A3-7A4-9A4-5A4-7A5-3A5-4A6-0复杂度分析：(0,0)(m,n)对坐标系 ，从原点（0，0）到（M，N）的最短的路经?n蛮力法（穷举法）：n求出每条路径的长度，通过比较，找出最短的一条路径。n问