网站公告列表     学友堂,成就你我!  [admin  2006年11月29日]        
加入收藏
设为首页
联系站长
您现在的位置: 学友堂 >> 教育 >> 论文 >> 文章正文
  动态规划的适用条件           
动态规划的适用条件
作者:佚名 文章来源:不详 更新时间:2007-11-10 23:03:08

动态规划的适用条件
任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

1.最优化原理(最优子结构性质)
最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。



图2

例如图2中,若路线I和J是A到C的最优路径,则根据最优化原理,路线J必是从B到C的最优路线。这可用反证法证明:假设有另一路径J'是B到C的最优路径,则A到C的路线取I和J'比I和J更优,矛盾。从而证明J'必是B到C的最优路径。

最优化原理是动态规划的基础,任何问题,如果失去了最优化原理的支持,就不可能用动态规划方法计算。动态规划的最优化理在其指标函数的可分离性和单调性中得到体现。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。

可以看出,例1是满足最优化原理的。

2.无后向性
将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

如果用前面的记号来描述无后向性,就是:对于确定的xk,无论p1,k-1如何,最优子策略pkn*是唯一确定的,这种性质称为无后向性。

2天前 - 0个意见 - 检举
文章录入:admin    责任编辑:admin 
  • 上一篇文章:

  • 下一篇文章:
  • 【字体: 】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口
    最 新 热 门
    最 新 推 荐
    相 关 文 章
    什么是线性规划?
    五五普法规划三个进一步…
    商业空间动态展示设计方…
    ★规划人生目标★
    职业规划如何收费
    职业规划如何收费
    物流系统规划与设计的主…
    信息化规划的核心内容