算法艺术与信息学竞赛标准

《算法艺术与信息学竞赛标准》由会员分享，可在线阅读，更多相关《算法艺术与信息学竞赛标准（47页珍藏版）》请在装配图网上搜索。

1、算法艺术与信息学竞赛标准课件动态规划(一):经典问题刘汝佳目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)五、最大m子段和O(mn)六、0-1背包问题O(minnc,2nn)一、最长公共子序列 Longest Common Subsequence(LCS)分析 考虑前缀x1.i和y1.j,定义ci,j=|LCS(x1.i,y1.j)|则cm,n=|LCS(x,y)|.递推公式为 很直观.考虑xi=yj的情形:关键点一:最优子结构 为了使用动态规划,问题需具备最优子结构最优子结构(Optimal Substructure)直

2、接书写的程序递归树分析关键点二:重叠子问题 为了让动态规划确实发挥功效,问题应该包含尽量多的重叠子问题重叠子问题(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个关键码和它们的频率，构造让期望比较次数最小的排序二叉树分析 定理：定理：最优排序二叉树的子树也是最优排序二叉树 给出关键码-频率对照表（升序排列）问题：把哪个关键码做为根？则左右子树可以递归往下做ABC

4、DE23 10812 30FGHIJKLMNOP.514 18 202411722 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(n3)空间复杂度：需要两个n*n矩阵，O(

5、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 求p1和p2的最长公共子序列

7、 例: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 即映射52,24,45,p2作同样置换5 3 4 2 1 2 3 5 4 1 与1,2,3.n的LCS显然是最长上升子序列,时间降为O(nlogn)推广:DAG上的最短路“上升”依赖于序关系=,它具有一般性 DAG(有向无环图)的最长路径问题:把有向边看成偏序关系,则本题的算法一仍然适用,时间复杂度为O(n2).如果图的边数m比较,可进一步优化到O(m),因为每条边恰好考虑

8、一次(用邻接表或前向星,而不是邻接矩阵)算法二不再适用算法二不再适用!因为d值相同的a不一定可以两两相互比较,不一定存在最小值.四、最优三角剖分 给一个n个顶点的凸多边形,有很多方法对它进行三角剖分(polygon triangulation)每个三角形有一个权计算公式(如周长,顶点权和),求总权最小(大)的三角剖分方案分析 用di,j表示由顶点i,i+1,j组成的多边形(注意i可以大于j)的最小代价 方案一:枚举三个顶点,组成一个三角形,决策是O(n3)的 方案二:边(i,j)一定属于一个唯一的三角形,设第三个顶点为k,则决策仅为O(n)采用方案二,状态O(n2),决策O(n),总O(n3)

9、分析 确定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.决斗 编号为1n的n个人按逆时针方向排成一圈圈，他们要决斗n-1场。每场比赛在某相邻两人间进行，败者退出圈子，紧靠败者右边的人成为与胜者直接相邻的人。任意两人之间决斗的胜负都将在一矩阵中给出（如果Ai,j=1则i与j决斗i总是赢，如果Ai,j=0则i与j决斗时i总是输），求出所有可能可能赢得整场决斗的人的序号分析 首先把圈想象成一条链 设di,j表示i是否能和j相遇,则相遇的充要条件是存在k,i和k,k和j都能相遇,且i或或j能打败k 同样是O(n2)个状态,决策O(n),总

11、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(n),总O(n2m)可以继续优化.注意到时间主要耗费在对x的枚举上,计算m

12、axdi-1,x.这个值 我们把d的第一维称为”阶段”,则本题是典型的多阶段决策问题 计算一个阶段时,顺便记录顺便记录本阶段最大值 只保留相邻两个阶段(滚动数组)则时间降为O(nm),空间降为O(n)六、0-1背包问题 给定n种物品和一个背包,物品i的重量是wi,价值是vi,背包容量为c 对于每个物品，要么装背包，要么不装 选择装背包的物品集合，使得物品总重量不超过背包容量c,且价值和尽量大分析 设di,j为背包容量为j时,只考虑前i个物品时的最大价值和 如果装第i个物品,背包容量只剩j-wi 如果不装,背包容量不变 因此di,j=maxdi,j-wi+vi,di-1,j 状态有nc个,每个状

13、态决策只有两个,因此总时间复杂度为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/2n)