北京大学：《数据结构与算法》课程教学资源（实习课件PPT）动态规划

动态规划 张阜东

动态规划 张阜东

多阶段决策问题 动态规划研究对象:多阶段决策问题 多阶段决策问题 可以分为若干个相互联系的阶段,每个阶段 都要做出一个决策,这个决策即决定了本阶段 的效益,也决定了下一阶段的初始状态 每一个阶段的决策确定后,就得到一个决 策序列,称为策略。 多阶段决策问题就是求一个策略,使各个阶 段的效益总和达到最优

多阶段决策问题 „ 动态规划研究对象：多阶段决策问题 „ 多阶段决策问题： 可以分为若干个相互联系的阶段，每个阶段 都要做出一个决策，这个决策即决定了本阶段 的效益，也决定了下一阶段的初始状态。 当每一个阶段的决策确定后，就得到一个决 策序列，称为策略。 多阶段决策问题就是求一个策略，使各个阶 段的效益总和达到最优

应用条件 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的,我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划(用了会 得到错误的解) 子问题重叠性质 每次产生的子问题并不总是新问题,有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高

应用条件 „ 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的，我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划（用了会 得到错误的解） „ 子问题重叠性质 每次产生的子问题并不总是新问题，有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算。 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高

应用条件 从起始点到终点最短距离 d,15 d,11 s1口6d939u22口T1 B1 色1 27u305d3 d,105 4A2 d, 5 s4口 u,43 最优子结构性质:任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质:任何中间节点到终点的距离都被前面的节点多次使用

应用条件 „ 从起始点到终点最短距离 最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质：任何中间节点到终点的距离都被前面的节点多次使用

基本思想 分治 把大的问题化简成小的同类问题 把复杂的问题化简成多步计算问题 不包含公共的子问题 问题结构想象成一棵树 动态规划 也是划分问题为子问题 保留重复子问题的计算结果 ■问题结构想象成一个子问题(状态)图,这个图其 实就是我们发现了树的一些节点重复了,然后合并 这些节点

基本思想 „ 分治 „ 把大的问题化简成小的同类问题 „ 把复杂的问题化简成多步计算问题 „ 不包含公共的子问题 „ 问题结构想象成一棵树 „ 动态规划 „ 也是划分问题为子问题 „ 保留重复子问题的计算结果 „ 问题结构想象成一个子问题（状态）图，这个图其 实就是我们发现了树的一些节点重复了，然后合并 了这些节点

步骤 将问题表示成多步判断 ■确定是否满足最优子结构性质—一必要条件 确定子问题的重叠性——估计算法效率 列出关于优化函数的递推方程(或不等式)和边 界条件 自底向上计算子问题的优化函数值--递归 的算法 备忘录方法记录中间结果 标记函数追踪问题的解

步骤 „ 将问题表示成多步判断 „ 确定是否满足最优子结构性质——必要条件 „ 确定子问题的重叠性——估计算法效率 „ 列出关于优化函数的递推方程(或不等式)和边 界条件 „ 自底向上计算子问题的优化函数值----非递归 的算法 „ 备忘录方法记录中间结果 „ 标记函数追踪问题的解

常见的实现形式 自底向上—递推 通过递推公式由小问题得到大问题的解,状态 就是递推公式的每个中间结果。 ■自顶向下—一备忘录 建立一个全局可以访问的状态表,把递归搜索 的结果保存起来,当下次达到状态时直接返回 结果。 第一种形式的程序更快更省空间 第二种形式有时候更直观,有助于理解

常见的实现形式 „ 自底向上——递推 通过递推公式由小问题得到大问题的解，状态 就是递推公式的每个中间结果。 „ 自顶向下——备忘录 建立一个全局可以访问的状态表，把递归搜索 的结果保存起来，当下次达到状态时直接返回 结果。 第一种形式的程序更快更省空间 第二种形式有时候更直观，有助于理解

搜索,备忘录,递推 搜索的方法 函数 shortPath返回一个节点到目标节点的最小路径 长度 shortPath(node) min inf. forG=i child begin o:j!= i.child. endo:++] t= shortPath j) if (t+ length(node, * j< min) min =t+ length(node, j; return min

搜索，备忘录，递推 „ 搜索的方法 „ 函数shortPath返回一个节点到目标节点的最小路径 长度 shortPath(node) { min = INF; for(j = i.child.begin(); j != i.child.end(); ++j) { t = shortPath(*j); if (t + length(node,*j) < min) min = t + length(node,*j) ; } return min; }

搜索,备忘录,递推 备忘录的方法 int graph[MAX_NODE_NUM] memset(graph, 0, sizeof(int *MAX_NODE_NUM); shortPath(node)t if (graph[node]= 0) return graph[node] min maXint for =i. child. begin o; j!= i. child. endo:++jt t= shortPath (j; if (t+ length(node, ])< min) min=t+ path(node, 1; graph[node]= min return min;

搜索，备忘录，递推 „ 备忘录的方法 int graph[MAX_NODE_NUM]; memset(graph,0,sizeof(int)*MAX_NODE_NUM); shortPath(node) { if (graph[node] != 0) return graph[node]; min = MAXINT; for(j = i.child.begin(); j != i.child.end(); ++j) { t = shortPath(*j); if (t + length(node,*j) < min) min = t + path(node,*j) ; } graph[node] = min; return min; }

搜索,备忘录,递推 递推的方法 递推式 shortPath i= min(shortPath(+ path(i]) 〔是i的子节点) shortPath()=0(为目标节点) 然后使用从递推式边界算起的方法递推 到上层

搜索，备忘录，递推 „ 递推的方法 „ 递推式 „ shortPath(i) = min(shortPath(j) + path(i,j)) (j 是i的子节点 ) „ shortPath(i) = 0 (i 为目标节点 ) „ 然后使用从递推式边界算起的方法递推 到上层