动态规划浅谈

《动态规划浅谈》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划浅谈动态规划(dynamicprogramming)算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题,然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪

2、准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。1、最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。2、子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法

3、正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时,只是在表格中简单地査看一下结果，从而获得较高的解题效率。当我们己经确定待解决的问题需要用动态规划算法求解时，通常可以按照以下步骤设计动态规划算法：1、分析问题的最优解，找出最优解的性质，并刻画其结构特征；2、递归地定义最优值；3、采用自底向上的方式计算问题的最优值；4、根据计算最优值时得到的信息，构造最优解。1〜3步是动态规划算法解决问题的基本步骤，在只需要计算最优值的问题中，完成这三个基本步骤就可以了。如果问题需要

4、构造最优解，还要执行第4步；此时，在第3步通常需要记录更多的信息，以便在步骤4中，有足够的信息快速地构造出最优解。下面通过几个经典例子来演示一下动态规划的具体思想.例1：数字三角形如下所示的数字三角形：10从顶向下找出一条权值最小的路径。(路径的权值等于路径上各结点的值的和)用f(i,j)表示位置i,j上最优的权值。则很容易得出递归公式：x=f(i+1,j)+a[i,j]y=f(i+,j+l)+a[i,j]f(i,j)=x

5、){intx,y;if(i==n)returnarray[i][j]:x=search(i+1,j)+airay[i][j];y=search(i+1,j+l)+array[i][j];if(x

6、以了。于是动态规划的状态转移方程就被描述了出来：f(i,j)=a[i,j]+min(f(i+1,j),f(i+1,j+1))我们产取至底向上的求解过程，即先将子问题的最优解按照转移方程求解出来，再按照转移方程的要求构造出上级问题的解。算法如下：for(i=n-2;i>=0;i—){for(j=0;j<=i;j++){x=array[i][j]+array[i+1][j]:y=array[i][j]+array[i+1][j+1];array[i][j]=x

7、记忆化，将己求解的子问题的解记下来以避免重复计算。所以动态规划的题目必须满足重叠子问题的条件。例2：某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，并依次输岀被拦截的导弹飞来时候的高度。SAMPLEINPUT:3892071

8、5530029917015865SAMPLEOUTPUT:638930029917015865因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，