动态规划最优化原理

大榕树 \ Pascal语言 \ 算法与技巧

动态规划最优化原理

原文链接：http://www.mydrs.org/program/list.asp?id=244
    作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何，对以前的决策所形成的状态而言，余下的诸决策必须构成最优策略。（无论过程的初始状态/初始决策是什么，其余决策活动必须相对于初始决策所产生的状态构成一个最优决策序列，才可能使整个决策活动构成最优决策序列。）

    简单地说，一个整体过程的最优策略的子策略一定是最优策略。

    利用这个原理，可以把多阶段决策问题的求解过程看成是一个连续的逆推过程。由后向前逐步推算。在求解时，各种状态前面的状态和决策，对后面的子问题，只不过相当于其初始条件而己，不影晌后面过程的最优策略。原理的证明可用反证法。在此把它略去。

作者：
来源：淮安教学科研网
时间：2001-10-14

上一篇：
下一篇：动态规划的定义