tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

动态规划 刘汝佳


《算法艺术与信息学竞赛》 标准课件
动态规划(一): 经典问题 刘汝佳

目录
一、最长公共子序列O(mn) 二、最优排序二叉树O(n3) 三、最长上升子序列O(nlogn) 四、最优三角剖分O(n3) 五、最大m子段和O(mn) 六、0-1背包问题O(min{nc, 2n, n1.44n})

一、最长公共子序列<

br />? Longest Common Subsequence(LCS)

分析
? 考虑前缀x[1..i]和y[1..j], 定义 c[i,j] = |LCS(x[1..i], y[1..j])| ? 则c[m,n] = |LCS(x, y)|. 递推公式为

? 很直观. 考虑x[i]=y[j]的情形:

关键点一: 最优子结构
? 为了使用动态规划, 问题需具备最优子结构 (Optimal Substructure)

直接书写的程序

递归树分析

关键点二: 重叠子问题
? 为了让动态规划确实发挥功效, 问题应该包含尽 量多的重叠子问题(overlapping subproblems)

解决方法: 记忆化
? 注意memoization不是memorization

自底向上递推

空间优化
? 如果只需要最优值, 可以用滚动数组实现 ? 按照i递增的顺序计算, d[i,j]只和d[i-1,j]和 d[i,j-1]以及d[i-1,j-1]有关系,因此只需要保 留相邻两行, 空间复杂度为O(min{m,n}) ? 更进一步的, 可以只保留一行, 每次用单独 的变量x保留d[i-1,j], 则递推方程为 If(i==j) d[j]=x; else { x = d[j]; d[j]=max{d[j-1], d[j]} };

变形. 回文词
? 给一个字符串a, 保持原字符的顺序不变, 至 少要加几个字符才能变成回文词? ? 例: abfcbfa ? afbcfcbfa

分析
? 红、绿色表示原字符, 白色为新增字符 ? 显然, s和s’在任何一个位置不可能都是白色(不 需要加那个字符!) ? 应该让红色字符尽量多! 相当于求s和逆序串s’ 的LCS, 让LCS中的对应字符(红色)对齐, 中间的 每个绿色字符都增加一个字符和它相等

二、最优排序二叉树
? 给n个关键码和它们的频率,构造让期望比 较次数最小的排序二叉树

分析
? 定理:最优排序二叉树的子树也是最优排 序二叉树 ? 给出关键码-频率对照表(升序排列) ? 问题:把哪个关键码做为根?则左右子树 可以递归往下做
A B C D E F G H I J K L M N O P ..
23 10 8 12 30 5 14 18 20 2 4 11 7 22 22 10 ..

分析
? 用递归来思考,但用递推来做 ? 先考虑两个结点的情形

分析
? 可以用矩阵来保存结果 ? C[j,k]表示从j到k的关键码组成的最优排序二叉树 ? Root[j,k]记录这棵排序二叉树的根

分析
? 考虑三个结点的情形 ? 最优值放在C[B,D]中,根放在root[B,D]中

分析
? 类似地,更新所有C[j-2,j]和root[j-2,j]

分析
? 四个结点的情形(如A-D)

分析
? 最终计算结果为

分析
? 可以利用root矩阵递归地构造出最优树

分析
? 时间复杂度:计算每个C[i,j]和root[i,j]需要 枚举根结点,故为O(n3) ? 空间复杂度:需要两个n*n矩阵,O(n2)

三、最长上升子序列
? 最长上升子序列问题(LIS)给一个序列, 求它的一个递增子序列,使它的元素个数 尽量多。例如序列1,6,2,5,4,7的最长上升子 序列是1,2,5,7(还有其他的,这里略去)

分析
? 定义d[i]是从第1个元素到第i个元素为止的最长子 序列长度, 则状态转移方程为

? 直接使用这个方程得到的是O(n2)算法 ? 下面把它优化到O(nlogn)

状态的组织
? d值相同的a值只需要保留最小的, 因此用数 组g[i]表示d值为i的数的a最小值, 显然 g[1]<=g[2]<=…<=g[k] ? 计算d[i]: 需要在g中找到大于等于a[i]的第 一个数j, 则d[i]=j ? 更新g: 由于g[j]>a[i], 需要更新g[j]=a[i]

代码
? 使用STL的lower_bound可以直接求出比a[i] 大的第一个数, 用二分查找实现, 每次转移 时间O(logn), 总时间O(nlogn)
fill(g, g + n, infinity); for(int i = 0; i < n; i++){ int j = lower_bound(g, g + n, a[i]) - g; d[i] = j + 1; g[j] = a[i]; }

变形1: 航线问题
? 有两行点, 每行n个. 第一行点和第二行点是一一 对应的, 有线连接, 如下图所示 ? 选择尽量多的线, 两两不交叉

分析
? 设与第1行第i个点对应的是第2行第f[i]个点 ? 假设i<j, 两条线(i, f[i])和(j, f[j])的充要条件是 f[i]<f[j], 因此问题变成了 求f的最长上升子序列 ? 时间复杂度为O(nlogn)

变形2: 两排列的LCS
? 给1~n的两个排列p1, p2 ? 求p1和p2的最长公共子序列 ? 例: 1 5 3 2 4 ? 5 3 4 2 1

分析
? 算法一: 直接套用LCS算法, 时间O(n2) ? 算法二: 注意到把两个排列做相同的置换, LCS不变, 可以先把p1排列为1,2,3…,n 15324 ? 12345 ? 即映射5?2, 2?4, 4?5, p2作同样置换 53421?23541 ? 与1,2,3..n的LCS显然是最长上升子序列, 时 间降为O(nlogn)

推广: DAG上的最短路
? “上升”依赖于序关系<=, 它具有一般性 ? DAG(有向无环图)的最长路径问题: 把有向 边看成偏序关系, 则本题的算法一仍然适用, 时间复杂度为O(n2). 如果图的边数m比较, 可进一步优化到O(m), 因为每条边恰好考虑 一次(用邻接表或前向星, 而不是邻接矩阵) ? 算法二不再适用! 因为d值相同的a不一定可 以两两相互比较, 不一定存在最小值.

四、最优三角剖分
? 给一个n个顶点的凸多边形, 有很多方法对它进行 三角剖分(polygon triangulation) ? 每个三角形有一个权计算公式(如周长, 顶点权和), 求总权最小(大)的三角剖分方案

分析
? 用d[i,j]表示由顶点i, i+1, …, j组成的多边形 (注意i可以大于j) 的最小代价
– 方案一: 枚举三个顶点, 组成一个三角形, 决策 是O(n3)的 – 方案二: 边(i,j)一定属于一个唯一的三角形, 设第 三个顶点为k, 则决策仅为O(n)

? 采用方案二, 状态O(n2), 决策O(n), 总O(n3)

分析
? 确定k后, 最优方案应该是d[i,k]+d[k,j]+w(i,k,j) ? 因此转移方程d[i,j]=max{d[i,k]+d[k,j]+w(i,k,j)}

变形1: 最优矩阵乘法链
? 需要计算n个矩阵的乘积A1A2…An ? 由于矩阵乘法满足结合律, 可以有多种计算 方法. 例如A1是10*100, A2是100*5, A3是 5*50, 则
– 顺序1: (A1A2)A3, 代价为 10*100*5+10*5*50=7500 – 顺序2: A1(A2A3), 代价为 100*5*10+10*100*50=75000

? 求代价最小的方案(加括号方法)

共同的结构
? 用二叉树(binary tree)可以表示两个问题相同的 结构, 每个结点表示一个区间(结点区间 / 矩阵区 间), 左子树和右子树表示分成的两个序列 ? 如果在原问题中让d[i,j]表示i-1~j的最优值,则在 方程形式上也完全等价

变形2. 决斗
? 编号为1~n的n个人按逆时针方向排成一圈, 他们要决斗n-1场。每场比赛在某相邻两人 间进行,败者退出圈子,紧靠败者右边的 人成为与胜者直接相邻的人。 ? 任意两人之间决斗的胜负都将在一矩阵中 给出(如果A[i,j]=1则i与j决斗i总是赢,如果 A[i,j]=0则i与j决斗时i总是输), ? 求出所有可能赢得整场决斗的人的序号

分析
? 首先把圈想象成一条链

? 设d[i,j]表示i是否能和j相遇, 则相遇的充要条件是 存在k, i和k, k和j都能相遇, 且i或j能打败k

? 同样是O(n2)个状态, 决策O(n), 总O(n3)

五、最大m子段和
? 给一个序列a1, a2, …, an ? 求m个不相交(可以相接)的连续序列, 总和 尽量大 ? 例如m=2, 1 2 -3 4 5 -6 7

分析
? 设d[i,j]为以j项结尾的i段和的最大值, 则需要 枚举此段开头y和上一段结尾x, 即 d[i,j]=max{d[i-1,x] + a[y..j]} ? 每次需要枚举x<y<=j, 决策量为O(n2), 状态 为O(nm), 共O(n3m) ? 注意到如果a[j-1]也是本段的, 答案变成为 d[i,j-1]+a[j], 因此方程优化为 d[i,j]=max{d[i,j-1]+a[j], d[i-1,x]+a[j]}, x<j

分析
? 优化后状态仍然是二维的,但决策减少为 O(n), 总O(n2m) ? 可以继续优化. 注意到时间主要耗费在对x 的枚举上, 计算max{d[i-1,x]}. 这个值… ? 我们把d的第一维称为”阶段”, 则本题是 典型的多阶段决策问题
– 计算一个阶段时, 顺便记录本阶段最大值 – 只保留相邻两个阶段(滚动数组)

? 则时间降为O(nm), 空间降为O(n)

六、0-1背包问题
? 给定n种物品和一个背包, 物品i的重量是wi, 价值是vi, 背包容量为c ? 对于每个物品,要么装背包,要么不装 ? 选择装背包的物品集合,使得物品总重量 不超过背包容量c, 且价值和尽量大

分析
? 设d[i,j]为背包容量为j时, 只考虑前i个物品时 的最大价值和
– 如果装第i个物品, 背包容量只剩j-wi – 如果不装, 背包容量不变

? 因此d[i,j]=max{d[i,j-wi]+vi, d[i-1,j]} ? 状态有nc个, 每个状态决策只有两个, 因此 总时间复杂度为O(nc). 用滚动数组后, 空间 复杂度只有O(c)

分析
? 当c大时, 算法效率非常低. 事实上,由于c 是数值范围参数, 一般不把它看作输入规模. 这样的O(nc)只是一个伪多项式算法 ? 事实上, 如果物品重量和背包容量都是实数 时, 算法将失败, 因为看起来物品的重量和 可以是”任何实数”. ? 但事实是: 物品重量和只有2n种可能的取值, 并不是无限多种

分析
? 算法一: 枚举2n个子集合, 再计算, 枚举2n, 计算n, 共n2n ? 算法二: 采用递归枚举, 共2n ? 算法三: 先考虑一半元素, 保存2n/2个和. 再 考虑后一半元素, 每计算出一个和w, 查找重 量<=c-w的元素中价值的最大值. 下面考虑实现细节

算法三
? 前一半元素的2n/2个和按重量从小到大排序后放在 表a里. 对于任何两个和i, j, 如果wi<wj且vi>vj, 则j是 不需要保存的, 因此按重量排序好以后也是按价值 排序的 ? 考虑后一半元素时, 每得到一个重量w, 用二分查 找得到重量不超过c-w的最大元素, 则它的价值也 最大. ? 预处理时间复杂度2n/2log2n/2, 每个重量w二分查找 时间为log2n/2, 因此总2n/2log2n/2=O(n1.414n)


推荐相关:

acm动态规划总结

动态规划题目总结( Pku acm 1163 the Triangle 动态规划题目总结(一) 题目:http...刘汝佳《算法艺术和信息学竞赛》中 115 页讲到自底向上的递推,这个例子就非常...


动态规划的斜率优化

动态规划的斜率优化_电子/电路_工程科技_专业资料。斜率优化数形结合的运用 ——...【参考文献】 参考文献】《算法艺术与信息学竞赛》——刘汝佳、黄亮,清华大学...


动态规划加速原理

动态规划加速原理_数学_自然科学_专业资料。动态规划加速原理赵明阳 【摘要】 本...【参考资料】 1、 《算法艺术与信息学竞赛》刘汝佳、黄亮著 清华大学出版社 2...


动态规划训练专题

动态规划训练专题_计算机软件及应用_IT/计算机_专业资料。动态规划训练专题一、要求...算法艺术与信息学竞赛 刘汝佳 清华大学出版社 3. 佳 清华大学出版社 挑战编程:...


ACM培训计划

先掌握搜索,动态规划,贪心这些思想方法 然后学习各种技巧 ACM 基本算法分类 ACM 基本算法分类、推荐学习资料和配套 pku 习题一.动态规划 参考资料: 刘汝佳《算法艺术...


1-递归在算法设计中的应用剖析

动态规划以及回溯等角度进行了算法 设计, 对递归这一算法设计中极为常用方法和...参考文献 [1] 殷建平等译,算法导论,北京,机械工业出版社,2013 [2] 刘汝佳等,...


李开复说算法

动态规划, 图论等) 技术(编程) 队员能力上的互补 某论坛,一无聊男 yy 的中国"梦之队" 钱文杰( ) 反应奇快,擅长随机化,贪心,NOI 贪心王 刘汝佳 or 吴嘉之 见...


最长公共上升子序列(LCIS)的平方算法

最长公共上升子序列(LCIS)的 O(n^2)算法预备知识:动态规划的基本思想,LCS,...max); } } 最长公共上升子序列(LCIS)的平方算法@我们都爱刘汝佳 2011-2-18...


ACM队员应掌握的知识及POJ 题目推荐

《算法艺术与信息学竞赛》的习题提示在网上可搜到 一.动态规划 参考资料: 刘汝佳《算法艺术与信息学竞赛》 《算法导论》 推荐题目: http://poj.org/problem?id...


ACM算法推荐书籍

=== ACM 基本算法分类、推荐学习资料和配套 pku 习题 一.动态规划 参考资料: 刘汝佳《算法艺术与信息学竞赛》 《算法导论》 推荐题目: http://acm.pku.edu.cn...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com