文档介绍：动态规划思想
北京大学信息科学技术学院
陈峰宏
1001213658
纲要
动态规划概念
动态规划思路——顺推和逆推
状态压缩的动态规划
树型动态规划
动态规划优化
四边形不等式剪枝
队列优化
*凸单调性优化
动态规划概念——多阶段决策问题
阶段
状态
决策
转移方程
边界条件
B1 3 C1 1 D1
2 1
3 4 2
A1 C2 E1
2 1 2
3
B2 5 C3 1 D2
问题：求从A1到E1的最短路径长度。
A B C D E
阶段
状态
f(i)=min{f(j)+g(i, j)}，
f(i)表示到从起点到节点i的最短路径长度
f(A1)=0
思考：如果定义“路径长度”为实际长度模3的余数，为了求A1到E1的最短“路径长度”，还能用上述方法吗？
动态规划算法的适用范围
最优子结构
最优决策序列的字序列也是最优的
无后效性
决策只取决于当前状态的特征因素，而和到达此状态的方式无关
递推——将最优性变成统计的动态规划
递推同样需要状态的划分和无后效性
但是递推的转移函数（状态转移方程）通常不包括max和min，而是一些统计函数——如求和
递推的难点通常在状态建模和转移函数的确定
综上所述，将递推看成动态规划的一种形式是没问题的
因此，接下来的内容将不区别动态规划和递推
思路
核心思想——提取信息的共性，将影响到今后状态决策的信息提取出来。
提取的信息要尽可能精简，信息提取的思路可以从搜索开始设想
寻找一个合适的顺序去求得每个状态——弱化阶段的概念
一个简单例子——排队（2008年北京网络预赛题）
n个小朋友排队（每个小朋友都不一样高）。两个小朋友a和b能够互相看见当且仅当排在它们中间的小朋友比a和b都要矮。已知队伍中一共有m对小朋友可以互相看见，问有可能有多少种排队方式。
数据范围：n<=80,m<=10000
一个简单例子——排队（2008年北京网络预赛题）
思路方式——怎么提取信息的共性（无从下手）
创造一种方式——从下一步做起
提取共性——信息的冗余，去除冗余信息后，原来的若干搜索状态合并为一个
一个简单例子——排队（2008年北京网络预赛题）
是否存在更好的方法？
换一种顺序思考
提取信息的共性
从上面的分析可以看出，动态规划可以看成是对搜索的一种记忆化优化
动态规划需要尽量使得搜索的状态保存的信息尽可能的精简——说白了就是搜索的总状态数越少越好。这一点和搜索是相同的
和搜索不同的是，动态规划会需要按照某种特定的顺序