动态规划教程
需积分: 13 13 浏览量
2012-12-12
21:03:50
上传
评论
收藏 465KB DOC 举报
动态规划经典教程
引言：本人在做过一些题目后对 有些感想，就写了这个总结：
第一节动态规划基本概念
一，动态规划三要素：阶段，状态，决策。
他们的概念到处都是，我就不多说了，我只说说我对他们的理解：
如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就
是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一
个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策
后产生的）。
下面举个例子：
要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工
后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不
同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由
液态变成固态）。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是
一个决策。
一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就
是状态转移方程。
经过这个例子相信大家对动态规划有所了解了吧。
下面在说说我对动态规划的另外一个理解：
用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向
边，状态转移的代价就是边上的权。这样就形成了一个有向无环图 网（为什么无环呢？往下看）。
对这个图进行拓扑排序，删除一个边后同时出现入度为 的状态在同一阶段。这样对图求最优路径就是
动态规划问题的求解。
二，动态规划的适用范围
动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？
一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：
最优子结构（最优化原理）
无后效性
最优化原理在下面的最短路径问题中有详细的解答；
什么是无后效性呢？
就是说在状态 求解时用到状态 而状态 就解有用到状态 …状态 。
而求状态 时有用到了状态 这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用
图论理解动态规划中形成的图无环的原因。
也就是说当前状态是前面状态的完美总结，现在与过去无关。。。
当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。
三，动态规划解决问题的一般思路。
拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考
虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：
（）模型匹配法：
最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直
接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后
行。这些基本模型在先面的分类中将一一介绍。
（）三要素法
仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同：
剩余58页未读，继续阅读
资源评论
