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

算法艺术与信息学竞赛标准课件动态规划(一):经典问题刘汝佳目录一、最长公共子序列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 Substructure)直接书写的程序递归树分析关键点二:重叠子问题为了让动态规划确实发挥功效,问题应该包含尽量多的重叠子问题重叠子问题(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;变形.回文词给一个字符串a,保持原字符的顺序不变,至少要加几个字符才能变成回文词?例:abfcbfa afbcfcbfa分析红、绿色表示原字符,白色为新增字符显然,s和s在任何一个位置不可能都是白色(不需要加那个字符!)应该让红色字符尽量多!相当于求相当于求s和逆序串和逆序串s的的LCS,让LCS中的对应字符(红色)对齐,中间的每个绿色字符都增加一个字符和它相等二、最优排序二叉树给n个关键码和它们的频率，构造让期望比较次数最小的排序二叉树分析定理：定理：最优排序二叉树的子树也是最优排序二叉树给出关键码-频率对照表（升序排列）问题：把哪个关键码做为根？则左右子树可以递归往下做ABCDE23 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(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大的第一个数,用二分查找实现,每次转移时间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的最长公共子序列例: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),因为每条边恰好考虑一次(用邻接表或前向星,而不是邻接矩阵)算法二不再适用算法二不再适用!因为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)分析确定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)可以表示两个问题相同的结构,每个结点表示一个区间(结点区间/矩阵区间),左子树和右子树表示分成的两个序列如果在原问题中让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),总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的枚举上,计算maxdi-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个,每个状态决策只有两个,因此总时间复杂度为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)