规模化问题的解题策略

规模化问题的解题策略【关键字】规模化策略算法【摘要】问题规模化是近来信息学竞赛的一个新趋势，它意在通过扩大数据量来增加算法设计和编程实现的难度，这就向信息学竞赛的选手提出了更高层次的要求，本文试图探索一些解决此类问题的普遍性的策略。开始，本文给出了“规模化”一词的定义，并据此将其分为横向扩展和纵向扩展两种类型，分别进行论述。在探讨横向扩展问题的解决时本文是以谋划策略的“降维”思想为主要对象的；而重点讨论的是纵向扩展问题的解决，先提出了两种策略——分解法和精简法，然后结合一个具体例子研究“剪枝”在规模化问题中的应用。问题规模化是信息学竞赛向实际运用靠拢的一个体现，因此具有不可忽视的意义。【正文】一引论（一）背景分析分析近年来国际、国内中学生信息学竞赛试题，可以看出信息学竞赛对于选手的要求已经不再仅仅局限于“算法设计”，它同时在编程实现方面加强了考察力度，由侧重于考察理论知识转向理论考察与实践考察并重。这一命题宗旨的转变，给信息学竞赛注入了新的机能，为命题者开拓了另一个领域。其一体现有：试题由精巧型(这类试题的难度主要体现在精妙算法的构造，属于一点即通的类型)向规模型发展，从而使得问题的实现复杂化。（二）对“规模化”的理解规模一词在字典中的含义是：事物所具有的格式、形式或范围。在信息学竞赛中，问题的规模具体是指待处理数据量的大小，通常可以通过一组规模参数(S1,S2,…,Sk)来表示。例如下列问题1的规模就是(100)，而问题2的规模是(100,100)。问题1：求数列的前100项之和。问题2：求100*100的矩阵中的各项之和。问题3：求数列的前1000项之和。“规模化”即扩展问题的规模，它具体是指增加规模参数的个数或扩大规模参数的数值范围。我们知道，如果撇开计算机的硬件、软件等环境因素，可以认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模，或者说，它是问题规模的函数，程序的执行时间与存储量需求直接受到问题规模的影响。由于种种现行条件的制约，随着规模扩展，问题的实际解法集便会缩小，甚至变为空集，这有时会使问题规模扩展后无法用原来小规模时的理想模型解决。如NOI’99《生日蛋糕》一题，理论上可以用动态规划的方法求解，但因其空间耗费过大，多数人是用搜索来实现的。从“规模化”一词的定义不难看出，它包括横向扩展和纵向扩展。横向扩展是指增加规模参数的个数，如由问题1扩展至问题2，即我们通常说的多维化；纵向扩展是指扩大规模参数的数值范围，如由问题1扩展至问题3。下文将分别探讨这两类问题的一般性解题策略。二横向扩展问题的解题策略（一）构造策略的思想横向扩展问题一般具有维数高、难于构想的特点，所以谋划解决这一类问题的策略，通常采用“降维”[1]的思想：分析低维问题，找到解法，推广至高维的情况。下面我们就来看一个具体例子。问题一：对于一个n维体P((S1,T1),(S2,T2)，…，(Sn,Tn)),Si、Ti(i=1..n)均为整数，我们定义其阶积=(T1-S1)*(T2-S2)*…*(Tn-Sn)，并称(Ti-Si)是P的一个要素i。如果存在另一个n维体Q((S1`,T1`),(S2`,T2`)，…，(Sn`,Tn`)),使得Si`≥Si(i=1..n),且Ti`≤Ti(i=1..n),Si`、Ti`(i=1..n)也是整数，则称Q是P的子n维体。现给定一个n维体((0,A1),(0,A2)，…，(0,An)),求它所有子n维体的阶积和。〖问题分析〗：如果泛泛地从n维体入手，会觉得无所适从，根据要求“所有子n维体的阶积和”，我们可以枚举所有的子n维体，其时间复杂度高达O(m2n)（其中m表示Ai(i=1..n)的一般规模），效率不高的主要原因是数学模型不够抽象，而好的数学模型是建立在问题本质基础上的。所以说，如果我们对问题缺乏认识或认识不深，就不可能高效地解决它。这就是笼统的考虑横向扩展问题的弊病。下面我们根据上文提到的“降维”思想来解决此题。第一步：降低问题的规模。我们先从简单模型入手，来看一看n=1时的情况，我们把一维体（（0，A1））体现在在下图所示的一根数轴上，这里不妨把一维体看成一条线段,其阶积就是线段的长度。01234A1-1A1第二步：在低维问题中求找规律。试想把长度相同的子线段归类统计，那么对于长度为L的线段(s,s+L)：∵s+L≤A1∴s≤A1-L又∵s≥0，∴0≤s≤A1-L，这样的子线段共有A1+1-L条。所以，一维体（(0,A1)）的所有子一维体的阶积和为Σi*(A1+1-i){i=1..A1}，设为Fg(A1)。第三步：将规律推广至高维问题。我们将模型稍加推广，看看n=2时的情况。这时我们可将二维体看成一个矩形，其阶积就是矩形的面积。在上图中，我们把一个矩形嵌入平面直角坐标系。这里我们按照子矩形不同的长(x轴上的距离)、宽(y轴上的距离)来统计。我们先提取矩形中一个宽为1的单位矩形带(如上图的阴影部分)，然后讨论矩形的长。根据解决一维体时的规律，我们知道在这个单位矩形带中长为L的矩形共有A1+1-L个，所以在单位矩形带中，所有子矩形的面积和为Fg(A1)。由于宽为1的单位矩形带在原矩形中共有A2个，所有宽为1的子矩形的面积之和为1*A2*Fg(A1)。同理，所有宽为2的子矩形的面积之和为2*(A2-1)*Fg(A1)，因此所有宽为W的子矩形的面积之和为W*(A2+1-W)*Fg(A1)。由此可知二维体所有子二维体的阶积之和是Fg(A2)*Fg(A1)。逐步推广，可以得知求n维体（(0,A1),(0,A2)，…，(0,An)）所有子n维体的阶积和为Fg(A1)*Fg(A2)*…*Fg(An)。其中，Fg(a)=(1+2+…+a)+(1+2+…+a-1)+…+(1)=１—２[(a+1)a+a(a-1)+(a-1)(a-2)+…+2]=１—６[(a+2)(a+1)a-(a+1)a(a-1)+(a+1)a(a-1)-a(a-1)(a-2)+…+6-0]=１—６a(a+1)(a+2)至此，问题得到圆满解决，时间复杂度已经降到O(n)，足够满足维数高的y(A1,A2)单位矩形(A2-1)个宽为2的单位矩形带x(0,0)情况。（二）小结当然了，大多数横向扩展问题最终并不能如此轻松地解决，实际竞赛中的问题是非常复杂的，上面列举的例子没有涉及其他方面的知识点，是为了集中说明具体如何运用“降维”思想来分析问题。横向扩展问题的难度主要体现在思维上，所以我们应当从低维的简单情况入手，通过挖掘低维问题与高维问题的相通之处来寻找规律，找到规律后不能机械地推广到高维模型，要注意灵活、变通，真正使它发挥作用。三纵向扩展问题的解题策略（一）分解法问题二：求正整数N和M之间具有最多真因子的数。本题中的真因子是这样定义的：如果RP而且R能整除P，我们就称R是P的真因子，对于特殊整数1，我们认为1是1的真因子。参数范围：1≤N＜M≤999999999；M-N＜999999；时限：10s。我们很容易得到下列两个方法：方法一顺序查找法．．．．．：依次统计规定范围内的各整数的真因子个数，记录最优解。由于，分解质因数的算法时间复杂度为平方根级的，因此这个算法的时间复杂度为O((m-n)*m0.5)。方法二标号法．．．：枚举不同的因数，标记它们的倍数。如果不仔细分析，会认为两种方法的算法时间复杂度一样，实际上后者的时间复杂度是0((m-n)*(1+1/2+1/3…+1/[m0.5]))，还不到O((m-n)*[log2m0.5]){[x]表示[x,x+1)间的整数}。证明如下：先用数学归纳法证明1+1/2+1/3+1/4+1/5+…+1/(2n-1)≤n。当n=1时，左边=1，右边=n=1；1≤1，不等式成立。假设当n=k时，不等式成立，则有1+1/2+1/3+1/4+1/5+…+1/2k-1≤k现证明n=k+1时，不等式依然成立，∵1/2k+1/(2k+1)+1/(2k+2)+…+1/(2k+1-1)﹤1/2k+1/2k+…+1/2k=(2k+1-1-2k+1)/2k=1∴1+1/2+1/3+…+1/2k-1+1/2k+1/(2k+1)+…+1/(2k+1-1)≤k+1即1+1/2+1/3+1/4+1/5+…+1/2k+1-1≤k+1故命题成立。所以，1+1/2+1/3+1/4+1/5+…+1/n≤[log2n]方法二之所以在时间复杂度上大有降低，是因为它采用了“空间换时间”的模式，由于在标号的全过程中必须保存当前各整数的真因子个数，因此空间复杂度是0(m-n)，从参数范围可知，实际情况下无法满足这一需求。它仅仅停留在理论基础上，无法用程序实现。方法一虽然空间耗费小，具有可行性，但时间耗费却难以满足要求。于是我们得到：方法三分段统计法．．．．．：将给定区间分成不重复且不遗漏的若干个子区间，然后按方法二统计。由于方法一每次处理单一元素，因此时间耗费高，方法二将所有元素统一处理，因此空间需求大，而方法三则综合前两种方法的优点，在充分利用空间的情况下，得到较高的时间效率。方法三实质就是分解法的应用，由此我们将“分解法”定义如下：以一定的算法为原型，将大规模的问题分解成若干个不遗漏且尽量不重复的相对独立的子问题，使得所有子问题解集的全集就是原问题的解集。分解法的原理和适用范围：解决某些纵向扩展问题的时候，常常会出现理论需求与实际承受能力之间的“矛盾”，它主要体现在时空需求互相制约的关系上。如本题中的时空关系可以用下图所示的曲线（双曲线的某一支的一部分）来表示，其中曲线的两个端点分别代表方法一与方法二的时空需求。这时若把问题分解成若干规模较小的子问题，套用原有的算法解决，就能有效地中和时空需求的矛盾。通常，我们以实际空间承受能力作为划分子问题的规模标准，这样才能令时间效率得到最大提高。下图中，虚线位置表示实际空间承受能力的上限，它与曲线的交点就是时空需求分配的最优方案。（二）精简法我们对“精简法”定义如下：忽略问题的表面因素，只提取具有实质性联系的特殊信息，以节省空间适应问题的规模。下面我们结合一个具体例子说明这一解题方法：问题三：最长词链问题。给定一个仅包含小写字母的英文单词表，其中的每个单词包含至少1个字时间（方法一，空间耗费趋近于零）（方法二，时间耗费最小）实际可承受空间空间母，至多75个字母，且按字典顺序由小到大排列（不会重复）。所有单词所含的字母个数总和不超过2,000,000个。如果在一张由一个词或多个词组成的表中，每个单词（除最后一个）都被其后一个单词所包含（是其前缀），则称此表为一个链。现要求从单词表中找到一个包含单词数最多的最长词链。〖问题分析〗问题的实质是在一定的序列中，求找相邻元素（字串）间存在特定关系（包含）的最长子序列。解决这类问题，通常会用到动态规划的办法。这在求“数列的最长非降子序列”和IOI’99《隐藏的码字》一题中都有所运用。我们令num(i)表示以第i个单词为链尾的最长词链，则num(i)=max{num(j)}+1{j＜i，且单词j是单词i的前缀}所以，空间复杂度为O(n){n为所包含的单词个数}，本题的数据量过大，显然无法满足这一存储量需求。仔细考虑“字典顺序”和“前缀”的关系可以得出这样的结论：两个单词w1、w2，如果w2包含w1，且有一个单词w3满足，w1w3，w3w2，那么w3必定包含w1。简证如下：令w2=L1L2L3..LLW2，w3=L1`L2`L3`..LLW3`，则w1=L1L2L3..LLW1(Li或Li`为字母)。假设w3不包含w1，由于w1w3，则必存在一个i值(i≤Lw1，i≤Lw3)，使得Lj=Lj`(0＜j＜i)，Li＜Li`，所以w3w2，这与w3w2矛盾，因此假设不成立。所以某个单词的(单词表中存在的)前缀，必定被其前驱单词所包含或者就是其前驱单词。于是我们可将单词的所有前缀(每个单词也可视为自身的前缀)标记出来，来为后面的单词传递信息。如下表：i；int；integer；intern；internet；integerinterninternet首先