Skip to content

lang710/DynamicProgramming

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 

Repository files navigation

动态规划是解决多阶段决策最优化问题的一种思想方法,我们可以从很多方面来体会它的思想。
动态规划思路产生的两种方法。分别用递归思想和多阶段决策思想阐明了动态规划思路的两种产生方法。

这两种思路是对称的:用递归思路建立模型,容易算出状态的前趋,适合顺推;用多阶段决策建立模型,容易 算出状态后继,适合逆推。 无后效性和最优子结构。它们的本质一样,即利用无后效性定义状态,进一步根据最优子结构定义状态的 指标函数并进行状态转移。重叠子问题越多,动态规划的优越性也就越明显。状态和状态转移是动态规划的精 髓。 状态表示。动态规划方法的核心是状态表示。状态的可定义性来源于问题的无后效性。由于状态是人为规 定的,可以通过增加维数的方法来消除后效性,也可以在保持无后效性的前提下改变状态定义,以得到更多的 重叠子问题。 状态转移。有了状态定义之后,思考的重点在于状态转移。状态转移的可定义性来源于问题的最优子结构。 而当问题不具备最优子结构的时候,通常通过增加维数的办法来解决。但值得注意的是,这样的结果有可能使得 子问题不重叠,从而使动态规划变得没有意义。 动态规划的两种实现方式。即递推和记忆化搜索。递归很灵活(它可以避免无用的状态,而且书写简单,可 以自顶向下“剪枝”),但无法用后面用到的很多优化如滚动数组减少空间消耗,状态合理组织降低时间复杂度等。

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages