动态规划算法.pptVIP

--动态规划算法算法设计与分析动态规划算法1、认识动态规划算法2、算法框架3、动态规划应用 在动态规划算法策略中: 体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策,并通过多阶段决策来最终解决问题。 在各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随即引起状态的转移。 一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。所以，这种多阶段决策最优化的解决问题的过程称为动态规划。1认识动态规划【例1】数塔问题 如图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。问题分析算法设计小结问题分析这个问题用贪婪算法有可能会找不到真正的最大和。以上图为例就是如此。用贪婪的策略，则路径和分别为：9+15+8+9+10=51（自上而下），19+2+10+12+9=52（自下而上）。都得不到最优解，真正的最大和是：9+12+10+18+10=59。算法设计动态规划设计过程如下：1.阶段划分：第一步对于第五层的数据，我们做如下决策：对经过第四层2的路径选择第五层的19，对经过第四层18的路径选择第五层的10，对经过第四层9的路径也选择第五层的10，对经过第四层5的路径选择第五层的16。以上的决策结果将五阶数塔问题变为4阶子问题，递推出第四层与第五层的和为:21(2+19),28(18+10),19(9+10),21(5+16)。用同样的方法还可以将4阶数塔问题,变为3阶数塔问题。……最后得到的1阶数塔问题，就是整个问题的最优解。2．存储、求解：1)原始信息存储原始信息有层数和数塔中的数据，层数用一个整型变量n存储，数塔中的数据用二维数组data，存储成如下的下三角阵:91215106821895197104162)动态规划过程存储必需用二维数组a存储各阶段的决策结果。二维数组a的存储内容如下：a[n][j]=data[n][j]j=1,2,……,n；i=n-1,n-2,……1，j=1,2,……,i；时a[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]最后a[1][1]存储的就是问题的结果。3)最优解路径求解及存储仅有数组data和数组a可以找到最优解的路径，但需要自顶向下比较数组data和数组a是可以找到。数组data数组a95912155049106838342921895212819211971041619710416数塔及动态规划过程数据总结动态规划=贪婪策略+递推(降阶)+存储递推结果贪婪策略、递推算法都是在“线性”地解决问题，而动态规划则是全面分阶段地解决问题。可以通俗地说动态规划是“带决策的多阶段、多方位的递推算法”。1.适合动态规划的问题特征动态规划算法的问题及决策应该具有三个性质：最优化原理、无后向性、子问题重叠性质。1)最优化原理(或称为最佳原则、最优子结构)。2)无后向性(无后效性)。3)有重叠子问题。2、算法框架

2.动态规划的基本思想动态规划方法的基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个子问题就是初始问题的解。由于动态规划的问题