多阶段决策问题 动态规划研究对象:多阶段决策问题 动态规划 多阶段决策问题 可以分为若干个相互联系的阶段,每个阶段 都要做出一个决策,这个决策即决定了本阶段 张阜东 的效益,也决定了下一阶段的初始状态 当每一个阶段的决策确定后,就得到一个决 策序列,称为策略。 多阶段决策问题就是求一个策略,使各个阶 段的效益总和达到最优 应用条件 应用条件 ■最优子结构性质 从起始点到终点最短距离 如果问题的最优解所包含的子问题的解也是最优 的,我们就称该问题具有最优子结构性质 子结构性质则不能使用动态规划(用了会 cOK 口72 ■子问题重叠性质 多次。保存中间计算结果而不是重复计 的题重性质则使用动态规划不能带米算法 最优子结构性质:任何最短路径的子路径都是相对于子路径的始点和终点 子问题重叠性质:任何中问节点到终点的距高都被前面的节点多次使用 基本思想 步骤 将问题表示成多步判断 把大的问题化简成小的同类问题 确定是否满足最优子结构性质——一必要条件 不包含公共的子问题 确定子问题的重叠性——估计算法效率 列出关于优化函数的递推方程(或不等式)和边 ■动态规划 界条件 也是划分问题为子问题 ■自底向上计算子问题的优化函数值--非递归 保留重复子问题的计算结果 的算法 蘊鬏糈踐了酹回蹬銮¤圄.蒸倉黁葺 备忘录方法记录中间结果 标记函数追踪问题的解1 动态规划 张阜东 多阶段决策问题 „ 动态规划研究对象：多阶段决策问题 „ 多阶段决策问题： 可以分为若干个相互联系的阶段，每个阶段 都要做出一个决策，这个决策即决定了本阶段 的效益，也决定了下一阶段的初始状态。 当每一个阶段的决策确定后，就得到一个决 策序列，称为策略。 多阶段决策问题就是求一个策略，使各个阶 段的效益总和达到最优。 应用条件 „ 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的，我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划（用了会 得到错误的解） „ 子问题重叠性质 每次产生的子问题并不总是新问题，有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算。 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高 应用条件 „ 从起始点到终点最短距离 最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质：任何中间节点到终点的距离都被前面的节点多次使用 基本思想 „ 分治 „ 把大的问题化简成小的同类问题 „ 把复杂的问题化简成多步计算问题 „ 不包含公共的子问题 „ 问题结构想象成一棵树 „ 动态规划 „ 也是划分问题为子问题 „ 保留重复子问题的计算结果 „ 问题结构想象成一个子问题（状态）图，这个图其 实就是我们发现了树的一些节点重复了，然后合并 了这些节点 步骤 „ 将问题表示成多步判断 „ 确定是否满足最优子结构性质——必要条件 „ 确定子问题的重叠性——估计算法效率 „ 列出关于优化函数的递推方程(或不等式)和边 界条件 „ 自底向上计算子问题的优化函数值----非递归 的算法 „ 备忘录方法记录中间结果 „ 标记函数追踪问题的解