动态规划及递推.pdf

北京大学陈峰宏 动态规划和递推 多阶段决策问题 B1 3 C1 1 D1  阶段 2 1 3 4 2  状态 A1 C2 E1 2 1 2  决策 3 B2 5 C3 1 D2  转移方程  边界条件 问题：求从A1 到E1的最短路径长度。 f(i)=min{f(j)+g(i, j)} ， A B C D E 状态阶段 f(i)表示到从起点到节点i的最短路径长度 思考：如果定义“路径长度”为实际长度模3 f(A1)=0 的余数，为了求A1 到E1的最短“路径长度”， 还能用上述方法吗？ 动态规划算法的适用范围  最优子结构  最优决策序列的字序列也是最优的  无后效性  决策只取决于当前状态的特征因素，而和到达此 状态的方式无关 递推——将最优性变成统计的动态规划  递推同样需要状态的划分和无后效性  但是递推的转移函数（状态转移方程）通常不 包括max和min ，而是一些统计函数——如求和  递推的难点通常在状态建模和转移函数的确定  综上所述，将递推看成动态规划的一种形式是 没问题的  因此，接下来的内容将不区别动态规划和递推 一个简单例子——排队（2008年北京网络预赛题）  n个小朋友排队（每个小朋友都不一样高）。 两个小朋友a和b能够互相看见当且仅当排在它 们中间的小朋友比a和b都要矮。已知队伍中一 共有m对小朋友可以互相看见，问有可能有多 少种排队方式。  数据范围：n=80,m=10000 一个简单例子——排队（2008年北京网络预赛题）  出题者想考察的是什么？  那么，有什么问题是不太需要考虑的？  由此可以发现什么？ 动态规划的实质  从上面的分析可以看出，动态规划可以看成是对有哪些信誉好的足球投注网站 的一种记忆化优化  动态规划就是将有哪些信誉好的足球投注网站时重复结算的状态保存下来，以 空间换时间。  记忆化有哪些信誉好的足球投注网站往往是按自顶向下的方向求解，而我们平 常所写的动态规划往往是自底向上的方向求解。  故实质上可以看成是记忆化有哪些信誉好的足球投注网站的一种非递归形式 动态规划建模——ACM3718 （08年杭州赛题）  有n个灯， 个开关，每个开关恰好控制3个灯 （摁下去则改变那3个灯的状态），且任意两 个开关控制的灯都不完全相同  给定n个灯的初始状态和目标状态  你需要打开恰好m个开关，达到目标状态  一开始所有的开关都是关着的  共有多少种方案（输出方案数模10007）？  数据范围(n=1000,m=1000) ACM3718分析——原始想法  先来个原始的想法  F(I,j)表示打开i个开关，到达状态j （j 不是一个 数，而是表示一个状态，可能需要一个长度为 n的二进制数）的方案数  问题  每个开关只能打开一次——无后效性？？？  时间和空间复杂度！！！！ ACM3718分析——减少状态数  观察——对于初始状态和目标状态，输入中用 个2n个数来描述  根据对称性，只需要知道两者有多少个灯有区 别即可——需要一个数来描述  问题可以转化成，输入n ，m ，k （需要改变k 个灯的状态），输出方案数  顺其自然，可以想到状态的表示，也可以如此