动态的规划设计.ppt

引入问题:求最短路径;Dijkstra算法 优点：适用性强，适用于所有图 缺点：效率低，时间复杂度为O(N*N) 出于本题的特殊性，我们可以采用动态规划思想 特殊性：可分为五个阶段 动态规划方程： 如果用f[i]表示到达第i个节点的最短路径长度，则 f[i]=min{f[i],f[j]+v[i,j]} 其中j表示i的前一个结点，v[i,j]中存放边的长度 ; 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。 1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。; 动态规划与分治法类似，也是要将 要求解的问题逐层分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按照层次关系构成一棵子问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 简单所来：动态规划就是一类大问题最优解包含子问题最优解的问题。;最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。; 动态规划常常以其特殊的策略解决过程大大优化有哪些信誉好的足球投注网站的时间复杂度，降低数量级。 相比之下，一般的有哪些信誉好的足球投注网站技术，对于某个子问题，不管是否已经解决过，只要遇上，就会再次对它求解，因而影响了解题的效率，而动态规划则是很好的利用了已经求解过的结果，利用这些结果缩短当前的最优解有哪些信誉好的足球投注网站次数，因此，很多情况下动态规划是一种以空间换时间的算法。;条件：同时满足最优子结构性质与无后向性。 步骤： （1）选择适当的问题状态表示，并分析最优解的性质 （2）递归地定义最优值（即建立递归方程或状态转移方程） （3）以自底向上的方式计算出最优值 （4）根据计算最优值时得到的信息，构造一个最优解 步骤（1）~（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略。若要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3） 中计算最优值是，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。;例：01背包 题目描述：;基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 ; 注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。 ; 优化空间复杂度;for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 Vijos p1104就是一道基于背包的题目，感兴趣的同学可以去自己练一下;;分析： 这个问题我们很容易得到如下结论：若路线经过当前方格，则路线必然经过其左边方格和上边的方格，换句话说，路线走到当前方格的最优值是左边方格和上边方格最优值中较优的