多阶段决策问题 动态规划研究对象:多阶段决策问题 动态规划 多阶段决策问题 可以分为若干个相互联系的阶段,每个阶段 都要做出一个决策,这个决策即决定了本阶段 张阜东 的效益,也决定了下一阶段的初始状态 当每一个阶段的决策确定后,就得到一个决 策序列,称为策略。 多阶段决策问题就是求一个策略,使各个阶 段的效益总和达到最优 应用条件 应用条件 ■最优子结构性质 从起始点到终点最短距离 如果问题的最优解所包含的子问题的解也是最优 的,我们就称该问题具有最优子结构性质 子结构性质则不能使用动态规划(用了会 cOK 口72 ■子问题重叠性质 多次。保存中间计算结果而不是重复计 的题重性质则使用动态规划不能带米算法 最优子结构性质:任何最短路径的子路径都是相对于子路径的始点和终点 子问题重叠性质:任何中问节点到终点的距高都被前面的节点多次使用 基本思想 步骤 将问题表示成多步判断 把大的问题化简成小的同类问题 确定是否满足最优子结构性质——一必要条件 不包含公共的子问题 确定子问题的重叠性——估计算法效率 列出关于优化函数的递推方程(或不等式)和边 ■动态规划 界条件 也是划分问题为子问题 ■自底向上计算子问题的优化函数值--非递归 保留重复子问题的计算结果 的算法 蘊鬏糈踐了酹回蹬銮¤圄.蒸倉黁葺 备忘录方法记录中间结果 标记函数追踪问题的解
1 动态规划 张阜东 多阶段决策问题 动态规划研究对象：多阶段决策问题 多阶段决策问题： 可以分为若干个相互联系的阶段，每个阶段 都要做出一个决策，这个决策即决定了本阶段 的效益，也决定了下一阶段的初始状态。 当每一个阶段的决策确定后，就得到一个决 策序列，称为策略。 多阶段决策问题就是求一个策略，使各个阶 段的效益总和达到最优。 应用条件 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的，我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划（用了会 得到错误的解） 子问题重叠性质 每次产生的子问题并不总是新问题，有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算。 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高 应用条件 从起始点到终点最短距离 最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质：任何中间节点到终点的距离都被前面的节点多次使用 基本思想 分治 把大的问题化简成小的同类问题 把复杂的问题化简成多步计算问题 不包含公共的子问题 问题结构想象成一棵树 动态规划 也是划分问题为子问题 保留重复子问题的计算结果 问题结构想象成一个子问题（状态）图，这个图其 实就是我们发现了树的一些节点重复了，然后合并 了这些节点 步骤 将问题表示成多步判断 确定是否满足最优子结构性质——必要条件 确定子问题的重叠性——估计算法效率 列出关于优化函数的递推方程(或不等式)和边 界条件 自底向上计算子问题的优化函数值----非递归 的算法 备忘录方法记录中间结果 标记函数追踪问题的解
常见的实现形式 搜索,备忘录,递推 ■自底向上 通过递推公式由小问题得到大问题的解,状态 函数 shortPath返回一个节点到目标节点的最小路径 就是递推公式的每个中间结果 自顶向下一一备忘录 建立一个全局可以访问的状态表,把递归搜索 ford= Lchild begin; jl= i child. endo: ++D) 的结果保存起来,当下次达到状态时直接返回 第一种形式的程序更快更省空间 第二种形式有时候更直观,有助于理解 搜索,备忘录,递推 搜索,备忘录,递推 graph[MAX_NODE_NUM]: 递推的方法 emset(graph, O, sizeof(int) MAX_ NODE_NUM); 递推式 shortPath(= min(shortPath(+ path (i,D)) aph[nodel 〔是的子节点) d begin(;jI= i.child. end(:++)( shortPath()=0(为目标节点) if(t+ length(node, 1)< min) ■然后使用从递推式边界算起的方法递推 到上层 搜索,备忘录,递推 0-1背包问题(1) ■搜索算法最直观,最容易想到 0-1背包问题 ■发现有重复的搜索节点就使用备忘录保 问题描述: 存节点信息。 有一个最多能用m公斤的背包,现 手件的重量分别是 ■得到递推方程一般可以转化为递推的算 法,节省函数递归的开销。 C1,C2,mCn求旅行者能获得的最大总价值。 特点: 每种物品仅有一件,可以选择放或不放
2 常见的实现形式 自底向上——递推 通过递推公式由小问题得到大问题的解，状态 就是递推公式的每个中间结果。 自顶向下——备忘录 建立一个全局可以访问的状态表，把递归搜索 的结果保存起来，当下次达到状态时直接返回 结果。 第一种形式的程序更快更省空间 第二种形式有时候更直观，有助于理解 搜索，备忘录，递推 搜索的方法 函数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) { 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(j) + path(i,j)) (j是i的子节点) shortPath(i) = 0 (i 为目标节点) 然后使用从递推式边界算起的方法递推 到上层 搜索，备忘录，递推 搜索算法最直观，最容易想到。 发现有重复的搜索节点就使用备忘录保 存节点信息。 得到递推方程一般可以转化为递推的算 法，节省函数递归的开销。 0-1背包问题（1） 0-1背包问题 问题描述： 一个旅行者有一个最多能用m公斤的背包，现 在有n件物品，每件的重量分别是 W1,W2,...,Wn, 每件的价值分别为 C1,C2,...,Cn。求旅行者能获得的最大总价值。 特点： 每种物品仅有一件，可以选择放或不放
0-1背包问题(2) 最长子序列(1) 抽象子问题:求前件物品恰放入一个容量为v 的背包可以获得的最大价值f[v] 最长上升子序列问题 ■若第件物品不放入背包中 给定一个整数序列AA2A3…An求它 fo[v]=f[i-1]] 的一个递增子序列,使子序列的元素个 若第i件物品放入背包中 数尽量多 [v=f[r-1yc+w可 例 ■故有递推公式 otv=max f[i-1[v, f[i-1[]+woy 1635427的最长上升子序列为1347 最长子序列(2) 最长子序列(3) ■设F[i]表示以第i个数结尾的上升子序列 ■方程的意义 的长度 找出能够接在后面的最长的上升子串 ■对于1635427来说 显然前面可能有多个子串都可以使A[达 ■F[i]分别为1223324 到同样F[ ■对于F[i+1],有方程 FLi]= max1, FLj] +11 假设有两个元素A区]和A[y],满足 (j=1,2, 1,且A[j]<A[i]) F[x]= Fly]= k 算法复杂度0(n2) 选min(Ax]A[y])结束的子串比较好 最长子序列(4) 邮局问题(1) 设D[k]=min(A[x]Ay]) ■问题描述 得j期量最的度列,保行这能够达到 条直线上坐标互不相同的n个村 ■对1635427来说,F]分别为1223324 庄,要求从中选择p个村庄建立邮局,每 D[1]=1D[2]=2D[3]=4D[4]=7 个村庄使用离它最近的那个邮局,使得 加入这个序列增长了一位,变成16354275 所有村庄到各自所使用的邮局的距离总 则找到最大的DK]=4<5,则而=k+1 然后更新DKk+1],D[4]更新成5 和最小 利用二分查找D算法复杂度提高到 o(nlogn)
3 0-1背包问题（2） 抽象子问题：求前i件物品恰放入一个容量为v 的背包可以获得的最大价值f[i][v] 若第i件物品不放入背包中 f[i][v] = f[i-1][v] 若第i件物品放入背包中 f[i][v] = f[i-1][v-c[i]] + w[i] 故有递推公式 f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]} 最长子序列（1） 最长上升子序列问题： 给定一个整数序列A1A2A3…An。求它 的一个递增子序列，使子序列的元素个 数尽量多 例： 1635427 的最长上升子序列为1347 最长子序列（2） 设F[i]表示以第i个数结尾的上升子序列 的长度 对于1635427来说 F[i]分别为1223324 对于F[i+1]，有方程 F[i] = max{1, F[j] + 1} (j=1,2,...,i-1,且A[j]<A[i]) 算法复杂度O(n2) 最长子序列（3） 方程的意义 找出能够接在后面的最长的上升子串 显然前面可能有多个子串都可以使A[i]达 到同样F[i] 假设有两个元素A[x]和A[y]，满足 F[x] = F[y] = k 选min(A[x],A[y])结束的子串比较好 最长子序列（4） 设D[k] = min(A[x],A[y]) 可以知道D[k]是递增的序列，保存这能够达到 长度k的序列里最小的数 对1635427来说，F[i]分别为1223324 D[1] = 1 D[2] = 2 D[3] = 4 D[4] = 7 加入这个序列增长了一位，变成16354275 则找到最大的D[k] = 4 < 5，则F[i] = k+1 然后更新D[k+1]，D[4]更新成5 利用二分查找D算法复杂度提高到O(nlogn) 邮局问题（1） 问题描述： 一条直线上坐标互不相同的n个村 庄，要求从中选择p个村庄建立邮局，每 个村庄使用离它最近的那个邮局，使得 所有村庄到各自所使用的邮局的距离总 和最小
邮局问题(2) 状态选择 心表示在前个村庄建立个邮局的最 mp]n]就是最后的结果 ■状态选择是动态规划最重要的步骤,也 设w为从第到第个村庄间设立一个邮局 是难点,需要在实践中体会状态选择的 技巧 m[10]= w[10](1<=D m[00]= min(m[i-1(k]+ wk+1D ■可能可以选择不同的状态,导致算法复 其中-1<=k<=j1 杂度不同 ■即找出一个划分点k,第个邮局安排在k+1 ■如果可以尽早知道某些状态是无用的 个村庄安排-1个邮局,总 距离最少。 就可以提高程序的效率,并且节省空间 状态选择 时间与空间的权衡 ■对于背包问题 本质上说动态规划是用空间换取时间的 每新增一件物品f[j[v]总是只与fi 算法 1]u]相关,即f-2][u]的状态已经没有用 可以扔掉。 ■记录中间节点状态就是为了不做重新计 ■对于最长上升子序列问题 算,但这增加了空间的消耗 ■当内存不足时可能需要用时间换回空间 使用D[]状态代替F[状态实际上是我 们保留了最佳状态而扔掉了不够好的状 这时候可能需要考虑哪些状态是常用的 状态予以保留,不常用的状态抛弃 学习动态规划的方法 ■多思考 例题为什么这样选择状态,是怎样列出方 蠢刻态废好的 检验自己是否 ■不明白的时候多查资料 google, baidu ■《算法导论》是入门的好书
4 邮局问题（2） 假设m[i][j]表示在前j个村庄建立i个邮局的最 小距离和，m[p][n]就是最后的结果 设w[i][j]为从第i到第j 个村庄间设立一个邮局 需要的最小距离 m[1][j] = w[1][j] (1 <= j) m[i][j] = min(m[i-1][k] + w[k+1][j]) 其中i-1 <= k <= j-1 即找出一个划分点k，第i个邮局安排在k+1与j 之间，从第1到第k个村庄安排i-1个邮局，总的 距离最少。 状态选择 状态选择是动态规划最重要的步骤，也 是难点，需要在实践中体会状态选择的 技巧 可能可以选择不同的状态，导致算法复 杂度不同 如果可以尽早知道某些状态是无用的， 就可以提高程序的效率，并且节省空间 状态选择 对于背包问题 每新增一件物品f[i][v]总是只与f[i- 1][u]相关，即f[i-2][u]的状态已经没有用 了，可以扔掉。 对于最长上升子序列问题 使用D[]状态代替F[]状态实际上是我 们保留了最佳状态而扔掉了不够好的状 态 时间与空间的权衡 本质上说动态规划是用空间换取时间的 算法 记录中间节点状态就是为了不做重新计 算，但这增加了空间的消耗 当内存不足时可能需要用时间换回空间 这时候可能需要考虑哪些状态是常用的 状态予以保留，不常用的状态抛弃 学习动态规划的方法 多思考 思考例题为什么这样选择状态，是怎样列出方 程的 多动手 把动态规划方程变成程序是一个检验自己是否 真的理解动态规划思想的很好的过程 不明白的时候多查资料 google，baidu 《算法导论》是入门的好书
