动态规划思想纲要动态规划概念动态规划思路——顺推和逆推状态压缩的动态规划树型动态规划动态规划优化四边形不等式剪枝队列优化*凸单调性优化动态规划算法的适用范围最优子结构最优决策序列的字序列也是最优的无后效性决策只取决于当前状态的特征因素,而和到达此状态的方式无关递推——将最优性变成统计的动态规划递推同样需要状态的划分和无后效性但是递推的转移函数(状态转移方程)通常不包括max和min,而是一些统计函数——如求和递推的难点通常在状态建模和转移函数的确定综上所述,将递推看成动态规划的一种形式是没问题的因此,接下来的内容将不区别动态规划和递推思路核心思想——提取信息的共性,将影响到今后状态决策的信息提取出来。提取的信息要尽可能精简,信息提取的思路可以从搜索开始设想寻找一个合适的顺序去求得每个状态——弱化阶段的概念一个简单例子——排队(2008年北京网络预赛题)n个小朋友排队(每个小朋友都不一样高)。两个小朋友a和b能够互相看见当且仅当排在它们中间的小朋友比a和b都要矮。已知队伍中一共有m对小朋友可以互相看见,问有可能有多少种排队方式。数据范围:n<=80,m<=10000一个简单例子——排队(2008年北京网络预赛题)思路方式——怎么提取信息的共性(无从下手)创造一种方式——从下一步做起提取共性——信息的冗余,去除冗余信息后,原来的若干搜索状态合并为一个一个简单例子——排队(2008年北京网络预赛题)是否存在更好的方法?换一种顺序思考提取信息的共性从上面的分析可以看出,动态规划可以看成是对搜索的一种记忆化优化动态规划需要尽量使得搜索的状态保存的信息尽可能的精简——说白了就是搜索的总状态数越少越好。这一点和搜索是相同的和搜索不同的是,动态规划会需要按照某种特定的顺序寻找合适的顺序这里讲的顺序分为两种,第一种是按照什么样的顺序求出每个状态的值,第二种是按照什么样的顺序来进行状态转移——或者说,状态转移方程的写法
动态规划思想 来自淘豆网m.daumloan.com转载请标明出处.
