动态规划 张阜东
动态规划 张阜东
多阶段决策问题 动态规划研究对象:多阶段决策问题 多阶段决策问题 可以分为若干个相互联系的阶段,每个阶段 都要做出一个决策,这个决策即决定了本阶段 的效益,也决定了下一阶段的初始状态 每一个阶段的决策确定后,就得到一个决 策序列,称为策略。 多阶段决策问题就是求一个策略,使各个阶 段的效益总和达到最优
多阶段决策问题 动态规划研究对象：多阶段决策问题 多阶段决策问题： 可以分为若干个相互联系的阶段，每个阶段 都要做出一个决策，这个决策即决定了本阶段 的效益，也决定了下一阶段的初始状态。 当每一个阶段的决策确定后，就得到一个决 策序列，称为策略。 多阶段决策问题就是求一个策略，使各个阶 段的效益总和达到最优
应用条件 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的,我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划(用了会 得到错误的解) 子问题重叠性质 每次产生的子问题并不总是新问题,有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高
应用条件 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的，我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划（用了会 得到错误的解） 子问题重叠性质 每次产生的子问题并不总是新问题，有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算。 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高
应用条件 从起始点到终点最短距离 d,15 d,11 s1口6d939u22口T1 B1 色1 27u305d3 d,105 4A2 d, 5 s4口 u,43 最优子结构性质:任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质:任何中间节点到终点的距离都被前面的节点多次使用
应用条件 从起始点到终点最短距离 最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质：任何中间节点到终点的距离都被前面的节点多次使用
基本思想 分治 把大的问题化简成小的同类问题 把复杂的问题化简成多步计算问题 不包含公共的子问题 问题结构想象成一棵树 动态规划 也是划分问题为子问题 保留重复子问题的计算结果 ■问题结构想象成一个子问题(状态)图,这个图其 实就是我们发现了树的一些节点重复了,然后合并 这些节点
基本思想 分治 把大的问题化简成小的同类问题 把复杂的问题化简成多步计算问题 不包含公共的子问题 问题结构想象成一棵树 动态规划 也是划分问题为子问题 保留重复子问题的计算结果 问题结构想象成一个子问题（状态）图，这个图其 实就是我们发现了树的一些节点重复了，然后合并 了这些节点