《算法艺术与信息学竞赛标准.ppt》由会员分享，可在线阅读，更多相关《算法艺术与信息学竞赛标准.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法艺术与信息学竞赛标准课件动态规划(一):经典问题刘汝佳目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)五、最大m 子段和O(mn)六、0-1 背包问题O(minnc,2n,n1.44n)一、最长公共子序列 Longest Common Subsequence(LCS)分析 考虑前缀x1.i 和y1.j,定义ci,j=|LCS(x1.i,y1.j)|则cm,n=|LCS(x,y)|.递推公式为 很直观.考虑xi=yj 的情形:关键点一:最优子结构 为了使用动态规划,问题需具备最优子结构(Optimal Substruct
2、ure)直接书写的程序递归树分析关键点二:重叠子问题 为了让动态规划确实发挥功效,问题应该包含尽量多的重叠子问题(overlapping subproblems)解决方法:记忆化 注意memoization 不是memorization自底向上递推空间优化 如果只需要最优值,可以用滚动数组实现 按照i 递增的顺序计算,di,j 只和di-1,j 和di,j-1 以及di-1,j-1 有关系，因此只需要保留相邻两行,空间复杂度为O(minm,n)更进一步的,可以只保留一行,每次用单独的变量x保留di-1,j,则递推方程为If(i=j)dj=x;else x=dj;dj=maxdj-1,dj;变形
3、.回文词 给一个字符串a,保持原字符的顺序不变,至少要加几个字符才能变成回文词?例:abfcbfa afbcfcbfa分析 红、绿色表示原字符,白色为新增字符 显然,s 和s 在任何一个位置不可能都是白色(不需要加那个字符!)应该让红色字符尽量多!相当于求s 和逆序串s的LCS,让LCS 中的对应字符(红色)对齐,中间的每个绿色字符都增加一个字符和它相等二、最优排序二叉树 给n 个关键码和它们的频率，构造让期望比较次数最小的排序二叉树分析 定理：最优排序二叉树的子树也是最优排序二叉树 给出关键码-频率对照表（升序排列）问题：把哪个关键码做为根？则左右子树可以递归往下做A B C D E23 1
4、0 8 12 30F G H I J K L M N O P.5 14 18 20 2 4 11 7 22 22 10.分析 用递归来思考，但用递推来做 先考虑两个结点的情形分析 可以用矩阵来保存结果 Cj,k 表示从j 到k的关键码组成的最优排序二叉树 Rootj,k 记录这棵排序二叉树的根分析 考虑三个结点的情形 最优值放在CB,D 中，根放在rootB,D 中分析 类似地，更新所有Cj-2,j 和rootj-2,j分析 四个结点的情形（如A-D）分析 最终计算结果为分析 可以利用root 矩阵递归地构造出最优树分析 时间复杂度：计算每个Ci,j和rooti,j 需要枚举根结点，故为O(n
5、3)空间复杂度：需要两个n*n 矩阵，O(n2)三、最长上升子序列 最长上升子序列问题（LIS）给一个序列，求它的一个递增子序列，使它的元素个数尽量多。例如序列1,6,2,5,4,7 的最长上升子序列是1,2,5,7（还有其他的，这里略去）分析 定义di 是从第1 个元素到第i 个元素为止的最长子序列长度,则状态转移方程为 直接使用这个方程得到的是O(n2)算法 下面把它优化到O(nlogn)状态的组织 d 值相同的a 值只需要保留最小的,因此用数组gi 表示d 值为i 的数的a 最小值,显然g1=g2=ai,需要更新gj=ai代码 使用STL 的lower_bound 可以直接求出比ai大的
6、第一个数,用二分查找实现,每次转移时间O(logn),总时间O(nlogn)fill(g,g+n,infinity);for(inti=0;in;i+)intj=lower_bound(g,g+n,ai)-g;di=j+1;gj=ai;变形1:航线问题 有两行点,每行n 个.第一行点和第二行点是一一对应的,有线连接,如下图所示 选择尽量多的线,两两不交叉分析 设与第1 行第i 个点对应的是第2 行第fi 个点 假设ij,两条线(i,fi)和(j,fj)的充要条件是fifj,因此问题变成了求f 的最长上升子序列 时间复杂度为O(nlogn)变形2:两排列的LCS 给1n 的两个排列p1,p2 求
7、p1和p2的最长公共子序列 例:1 5 3 2 4 5 3 4 2 1分析 算法一:直接套用LCS 算法,时间O(n2)算法二:注意到把两个排列做相同的置换,LCS 不变,可以先把p1排列为1,2,3,n1 5 3 2 4 1 2 3 4 5 即映射5 2,2 4,4 5,p2作同样置换5 3 4 2 1 2 3 5 4 1 与1,2,3.n 的LCS 显然是最长上升子序列,时间降为O(nlogn)推广:DAG 上的最短路“上升”依赖于序关系=,它具有一般性 DAG(有向无环图)的最长路径问题:把有向边看成偏序关系,则本题的算法一仍然适用,时间复杂度为O(n2).如果图的边数m 比较,可进一步
8、优化到O(m),因为每条边恰好考虑一次(用邻接表或前向星,而不是邻接矩阵)算法二不再适用!因为d 值相同的a 不一定可以两两相互比较,不一定存在最小值.四、最优三角剖分 给一个n 个顶点的凸多边形,有很多方法对它进行三角剖分(polygon triangulation)每个三角形有一个权计算公式(如周长,顶点权和),求总权最小(大)的三角剖分方案分析 用di,j 表示由顶点i,i+1,j 组成的多边形(注意i 可以大于j)的最小代价 方案一:枚举三个顶点,组成一个三角形,决策是O(n3)的 方案二:边(i,j)一定属于一个唯一的三角形,设第三个顶点为k,则决策仅为O(n)采用方案二,状态O(n
9、2),决策O(n),总O(n3)分析 确定k后,最优方案应该是di,k+dk,j+w(i,k,j)因此转移方程di,j=maxdi,k+dk,j+w(i,k,j)变形1:最优矩阵乘法链 需要计算n 个矩阵的乘积A1A2An 由于矩阵乘法满足结合律,可以有多种计算方法.例如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)可以表示两个问题相同的结构,每个结点
10、表示一个区间(结点区间/矩阵区间),左子树和右子树表示分成的两个序列 如果在原问题中让di,j 表示i-1j 的最优值，则在方程形式上也完全等价变形2.决斗 编号为1 n 的n 个人按逆时针方向排成一圈，他们要决斗n-1 场。每场比赛在某相邻两人间进行，败者退出圈子，紧靠败者右边的人成为与胜者直接相邻的人。任意两人之间决斗的胜负都将在一矩阵中给出（如果A i,j=1 则i 与j 决斗i 总是赢，如果A i,j=0 则i 与j 决斗时i 总是输），求出所有可能赢得整场决斗的人的序号分析 首先把圈想象成一条链 设di,j 表示i 是否能和j 相遇,则相遇的充要条件是存在k,i 和k,k 和j 都能
11、相遇,且i 或j 能打败k 同样是O(n2)个状态,决策O(n),总O(n3)五、最大m 子段和 给一个序列a1,a2,an 求m 个不相交(可以相接)的连续序列,总和尽量大 例如m=2,1 2-3 4 5-6 7分析 设di,j 为以j 项结尾的i 段和的最大值,则需要枚举此段开头y和上一段结尾x,即di,j=maxdi-1,x+ay.j 每次需要枚举xy=j,决策量为O(n2),状态为O(nm),共O(n3m)注意到如果aj-1 也是本段的,答案变成为di,j-1+aj,因此方程优化为di,j=maxdi,j-1+aj,di-1,x+aj,xj分析 优化后状态仍然是二维的，但决策减少为O(
12、n),总O(n2m)可以继续优化.注意到时间主要耗费在对x的枚举上,计算maxdi-1,x.这个值 我们把d 的第一维称为”阶段”,则本题是典型的多阶段决策问题 计算一个阶段时,顺便记录本阶段最大值 只保留相邻两个阶段(滚动数组)则时间降为O(nm),空间降为O(n)六、0-1 背包问题 给定n 种物品和一个背包,物品i 的重量是wi,价值是vi,背包容量为c 对于每个物品，要么装背包，要么不装 选择装背包的物品集合，使得物品总重量不超过背包容量c,且价值和尽量大分析 设di,j 为背包容量为j 时,只考虑前i 个物品时的最大价值和 如果装第i 个物品,背包容量只剩j-wi 如果不装,背包容量
13、不变 因此di,j=maxdi,j-wi+vi,di-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,如果wivj,则j是不需要保存的,因此按重量排序好以后也是按价值排序的 考虑后一半元素时,每得到一个重量w,用二分查找得到重量不超过c-w 的最大元素,则它的价值也最大.预处理时间复杂度2n/2log2n/2,每个重量w 二分查找时间为log2n/2,因此总2n/2log2n/2=O(n1.414n)