规模化问题的解题策略.DOC

1、 规模化问题的解题策略 长沙市一中谢婧- 1 -规模化问题的解题策略湖南省长沙市第一中学 谢婧【关键字】 规模化 策略 算法【摘要】问题规模化是近来信息学竞赛的一个新趋势，它意在通过扩大数据量来增加算法设计和编程实现的难度，这就向信息学竞赛的选手提出了更高层次的要求，本文试图探索一些解决此类问题的普遍性的策略。开始，本文给出了“规模化”一词的定义，并据此将其分为横向扩展和纵向扩展两种类型，分别进行论述。在探讨横向扩展问题的解决时本文是以谋划策略的“降维”思想为主要对象的；而重点讨论的是纵向扩展问题的解决，先提出了两种策略分解法和精简法，然后结合一个具体例子研究“剪枝”在规模化问题中的应用。问题

2、规模化是信息学竞赛向实际运用靠拢的一个体现，因此具有不可忽视的意义。【正文】一 引 论（一）背景分析分析近年来国际、国内中学生信息学竞赛试题，可以看出信息学竞赛对于选手的要求已经不再仅仅局限于“算法设计” ，它同时在编程实现方面加强了考察力度，由侧重于考察理论知识转向理论考察与实践考察并重。这一命题宗旨的转变，给信息学竞赛注入了新的机能，为命题者开拓了另一个领域。其一体现有：试题由精巧型(这类试题的难度主要体现在精妙算法的构造，属于一点即通的类型) 向规模型发展，从而使得问题的实现复杂化。（二）对“规模化”的理解规模一词在字典中的含义是：事物所具有的格式、形式或范围。在信息学竞赛中，问题的规模

3、具体是指待处理数据量的大小，通常可以通过一组规模参数(S 1,S2, Sk)来表示。例如下列问题 1 的规模就是 (100)，而问题 2 的规模是(100,100)。问题 1：求数列的前 100 项之和。问题 2：求 100*100 的矩阵中的各项之和。问题 3：求数列的前 1000 项之和。规模化问题的解题策略 长沙市一中谢婧- 2 -“规模化”即扩展问题的规模，它具体是指增加规模参数的个数或扩大规模参数的数值范围。我们知道，如果撇开计算机的硬件、软件等环境因素，可以认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模，或者说，它是问题规模的函数，程序的执行时间与存储量需求直接受到问题

4、规模的影响。由于种种现行条件的制约，随着规模扩展，问题的实际解法集便会缩小，甚至变为空集，这有时会使问题规模扩展后无法用原来小规模时的理想模型解决。如 NOI99 生日蛋糕一题，理论上可以用动态规划的方法求解，但因其空间耗费过大，多数人是用搜索来实现的。从“规模化”一词的定义不难看出，它包括横向扩展和纵向扩展。横向扩展是指增加规模参数的个数，如由问题 1 扩展至问题 2，即我们通常说的多维化；纵向扩展是指扩大规模参数的数值范围，如由问题 1 扩展至问题 3。下文将分别探讨这两类问题的一般性解题策略。二 横向扩展问题的解题策略（一）构造策略的思想横向扩展问题一般具有维数高、难于构想的特点，所以谋

5、划解决这一类问题的策略，通常采用“降维” 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),使得SiSi(i=1.n),且 TiTi(i=1.n), Si、Ti (i=1.n)也是整数，则称 Q是 P 的子 n 维体。现给定一个 n 维体(0,A1),(0,A2)，(0

6、,An),求它所有子 n 维体的阶积和。问题分析：如果泛泛地从 n 维体入手，会觉得无所适从，根据要求“所有子 n 维体的阶积和” ，我们可以枚举所有的子 n 维体，其时间复杂度高达 O(m2n)（其中 m表示 Ai(i=1.n)的一般规模） ，效率不高的主要原因是数学模型不够抽象，而好的数学模型是建立在问题本质基础上的。所以说，如果我们对问题缺乏认识或认识不深，就不可能高效地解决它。这就是笼统的考虑横向扩展问题的弊病。下面我们根据上文提到的“降维”思想来解决此题。第一步：降低问题的规模。我们先从简单模型入手，来看一看 n=1 时的情况，我们把一维体（0，A1） ）体现在在下图所示的一根数轴上

7、，这里不妨把一维体看成一条线规模化问题的解题策略 长沙市一中谢婧- 3 -段,其阶积就是线段的长度。第二步：在低维问题中求找规律。试想把长度相同的子线段归类统计，那么对于长度为 L 的线段(s,s+L) ：s+L A1 s A1-L 又s0，0sA1-L ，这样的子线段共有 A1+1-L 条。所以，一维体（(0,A1)）的所有子一维体的阶积和为 i*(A1+1-i)i=1.A1，设为 Fg(A1)。第三步：将规律推广至高维问题。我们将模型稍加推广，看看 n=2 时的情况。这时我们可将二维体看成一个矩形，其阶积就是矩形的面积。在上图中，我们把一个矩形嵌入平面直角坐标系。这里我们按照子矩形不同的长

8、(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)*

9、 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)+20 1 2 3 4 A1-1 A1y (A1,A2)单位矩形(A2-1)个宽为 2 的单位矩形带x(0,0)规模化问题的解题策略 长沙市一中谢婧- 4 -= (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) 至此，问题得到圆满解决，时间复

10、杂度已经降到 O(n)，足够满足维数高的情况。（二）小 结当然了，大多数横向扩展问题最终并不能如此轻松地解决，实际竞赛中的问题是非常复杂的，上面列举的例子没有涉及其他方面的知识点，是为了集中说明具体如何运用“降维”思想来分析问题。横向扩展问题的难度主要体现在思维上，所以我们应当从低维的简单情况入手，通过挖掘低维问题与高维问题的相通之处来寻找规律，找到规律后不能机械地推广到高维模型，要注意灵活、变通，真正使它发挥作用。三 纵向扩展问题的解题策略（一）分解法问题二：求正整数 N 和 M 之间具有最多真因子的数。本题中的真因子是这样定义的：如果 R 顺序查找法：依次统计规定范围内的各整数的真因子个数

11、，记录最优解。由于，分解质因数的算法时间复杂度为平方根级的，因此这个算法的时间复杂度为 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；11，不等式成立。假设当 n=k 时，不等式成立，则有1+1/2+1/3+1/4+1/5+1/2k-1k 现证明 n

12、=k+1 时，不等式依然成立， 1/2 k+1/(2k+1)+1/(2k+2)+1/(2k+1-1)1/2 k+1/2k+1/2k规模化问题的解题策略 长沙市一中谢婧- 5 -=(2k+1-1-2k+1)/2k=1 1+1/2+1/3+1/2 k-1+1/2k+1/(2k+1)+1/(2k+1-1)k+1即 1+1/2+1/3+1/4+1/5+1/2 k+1-1k+1故命题成立。所以，1+1/2+1/3+1/4+1/5+1/nlog 2n方法二之所以在时间复杂度上大有降低，是因为它采用了“空间换时间”的模式，由于在标号的全过程中必须保存当前各整数的真因子个数，因此空间复杂度是 0(m-n)，从

13、参数范围可知，实际情况下无法满足这一需求。它仅仅停留在理论基础上，无法用程序实现。方法一虽然空间耗费小，具有可行性，但时间耗费却难以满足要求。于是我们得到：分段统计法：将给定区间分成不重复且不遗漏的若干个子区间，然后按方法二统计。由于方法一每次处理单一元素，因此时间耗费高，方法二将所有元素统一处理，因此空间需求大，而方法三则综合前两种方法的优点，在充分利用空间的情况下，得到较高的时间效率。方法三实质就是分解法的应用，由此我们将“分解法”定义如下：以一定的算法为原型，将大规模的问题分解成若干个不遗漏且尽量不重复的相对独立的子问题，使得所有子问题解集的全集就是原问题的解集。分解法的原理和适用范围：

14、解决某些纵向扩展问题的时候，常常会出现理论需求与实际承受能力之间的“矛盾” ，它主要体现在时空需求互相制约的关系上。如本题中的时空关系可以用下图所示的曲线（双曲线的某一支的一部分）来表示，其中曲线的两个端点分别代表方法一与方法二的时空需求。这时若把问题分解成若干规模较小的子问题，套用原有的算法解决，就能有效地中和时空需求的矛盾。通常，我们以实际空间承受能力作为划分子问题的规模标准，这样才能令时间效率得到最大提高。下图中，虚线位置表示实际空间承受能力的上限，它与曲线的交点就是时空需求分配的最优方案。时间（方法一，空间耗费趋近于零）（方法二，时间耗费最小）实际可承受空间 空间规模化问题的解题策略

15、长沙市一中谢婧- 6 -（二）精简法我们对“精简法”定义如下：忽略问题的表面因素，只提取具有实质性联系的特殊信息，以节省空间适应问题的规模。下面我们结合一个具体例子说明这一解题方法：问题三：最长词链问题。给定一个仅包含小写字母的英文单词表，其中的每个单词包含至少 1 个字母，至多 75 个字母，且按字典顺序由小到大排列（不会重复） 。所有单词所含的字母个数总和不超过 2,000,000 个。如果在一张由一个词或多个词组成的表中，每个单词（除最后一个）都被其后一个单词所包含（是其前缀） ，则称此表为一个链。现要求从单词表中找到一个包含单词数最多的最长词链。问题分析问题的实质是在一定的序列中，求找

16、相邻元素（字串）间存在特定关系（包含）的最长子序列。解决这类问题，通常会用到动态规划的办法。这在求“数列的最长非降子序列”和 IOI99隐藏的码字一题中都有所运用。我们令 num(i)表示以第 i 个单词为链尾的最长词链，则num(i)=maxnum(j)+1ji，且单词 j 是单词 i 的前缀所以，空间复杂度为 O(n)n 为所包含的单词个数，本题的数据量过大，显然无法满足这一存储量需求。仔细考虑“字典顺序”和“前缀”的关系可以得出这样的结论：两个单词w1、w2，如果 w2 包含 w1，且有一个单词 w3 满足， w1w2，这与 w3 记录下每行中包括首元素在内的下限一定的最大线性区域长度，

17、然后查找下限一定的面积最大区域。(为方便讨论，在示意图中行、列的排列按从上至下，从左至右的顺序)以左图的一个 4*4 的矩形为例（C=4）：从（1,1）格开始，下限为 36（上限为36+C）的线性区域可延伸至（1,2）格；同理，从（2,1） ， （3,1） ， （4,1）格开始，下限为 36 的线性区域分别可延伸至（2,4） ，（3,2） ， （4,4）格。 所以下限为 36 的面积最大区域为（1,1,4,2） 。我们注意到，统计每行的最大线性区域时，由于必须包括首元素，因此下限值与首位元素值不会超过 C。由于 C 的取值范围是0,10，空间需求可以满足，该算法具有可行性，其算法复杂度为 O(

18、uv2C)。由于 u、v 的上限是 700，尽管试题规定的最大时限长达一分钟，仍然无法满足这一时间耗费。将矩阵进行横向压缩，得到一系列单位区域，然后求最长的连续单位区域。我们可以得到如下算法：可以看出，上述算法的时间复杂度是 O(100uv2)。如果从时间复杂度来看两种方法，前者肯定比后者好。但如果对于后者加上好的剪枝条件，结果就不一样了。由于我们求找面积最大的矩形区域会不断更新当前的最优值，所以，如果某次计算所能得到的最大面积不超过当前的最优值，则这样的计算毫无意义，可以省略。38 38 33 3939 40 39 3939 40 41 3836 39 39 391 确定西界限；2 确定东界

19、限（西界限+100） ； 3 对从西界限至东界限的每个单位区域进行统计；4 确定北界限5 找到最小的南界限；38 38 33 3939 40 39 3939 40 41 3836 39 39 3938 38 33 3939 40 39 3939 40 41 3836 39 39 3938 38 33 3939 40 39 3939 40 41 3836 39 39 39规模化问题的解题策略 长沙市一中谢婧- 9 -我们仍然以原来 4*4 的矩形为例，以上三个矩形中分别用粗线条框出了西界限为 1，东界限为 2、3、4 时的面积最大区域。我们可以发现南北界限的差别呈递减趋势，事实上，这并不是偶然的

20、，可以用反证法证明，西界限一定，而东界限逐步扩展，也即矩形的宽度增加时，最大面积矩形区域的长度是（非严格）递减的。我们令 Max_widewno,eno表示东西界限为 eno 和 wno 时的最大区域长度，那么 Max_widewno,eno Max_widewno,eno-1。所以我们可以得到下列两个剪枝条件：If 最大宽度（ Min100,u）* Max_widewno,eno-1当前最大面积 Then 扩展西界限；If (eno- wno+1)* Max_widewno,eno-1当前最大面积 Then 扩展东界限；下面我们就将方法一（land_1.pas） 、方法二（land_2.pa

21、s）及结合剪枝条件后的方法二（land_3.pas）进行测试时间的对照：运 行 时 间输入数据 数据规模 (U,V,C)Land_1.pas Land_2.pas Land_3.pas1 20，20，0 0.05s 0.05s 0.05s2 30，41，5 0.05s 0.49s 0.05s3 100，100，2 0.22s 0.94s 0.11s4 100，500，7 1.26s 2.20s 0.90s5 300，300，10 9.23s 10.33s 2.47s6 500，400，10 20.99s 98.52s 7.25s7 600，500，5 1.54s 25.73s 4.89s8 7

22、00，700，9 99.89s 56.87s 9.78s9 700，700，10 168.85s 1695.93s 34.12s（运行环境：pentium 166MHz/16MB）注：数据是按规模从大到小进行排列的。规模化问题的解题策略 长沙市一中谢婧- 10 -测试结果分析：除数据 7 的运行时间与数据规模不相称外，程序一的运行时间与数据规模相对稳定，那主要是由于数据 7 中相邻正方形的高度差大多大于阈值 C。所以 O(uv2C)是本算法的平均时间复杂度，它能够较为准确地反映其时间耗费。对于规模递增的数据，程序二的运行时间波动很大，尤其是数据 8 与数据 9，两数据规模相差无几，而运行结果却

23、大相径庭。这说明了 O(100uv2)仅仅是算法最坏情况下的时间复杂度。由于程序二的实际时间耗费对于数据规模的依赖性大，因此难以用时间复杂度较准确地反映。剪枝效果分析：一旦确定剪枝条件，每次统计都会执行一次判断操作，所以不精准的剪枝会带来很大的负面影响，再则剪枝条件的效果常常被认为存在很大的偶然性。所以它常常被人们冷落。在上表中，相对于程序二，程序三的运行速度大大提高，且普遍优于程序一，对比说明剪枝条件还是起到了很好的筛减作用。从其运行时间中，我们还能够大致看出数据规模，尽管我们并不能精准地估计出剪枝条件的效用到底有多大，但这一相对稳定性足以说明，使用优秀的剪枝条件或者综合使用多方面的剪枝条件

24、，收益良好也就是“偶然”中的必然了。尽管剪枝不能降低算法的时间复杂度，但却对降低实际时间耗费有着非同小可的作用。尤其是规模化问题，时间耗费大，如果注意分析问题，找到约束信息，必将起到事半功倍的效果。（四）小 结由于纵向扩展问题具有很大的灵活性，很难像多维化问题那样总结出一个统一的谋划策略的思想，也难以归纳出较为完整的策略集，以上仅仅是我根据平时练习的经验总结出的自认为有一定推广意义的一些策略，其中也提到了剪枝在纵向扩展问题中的应用，尽管它不是一个具体的策略，但对于规模化问题也有普遍意义，这已经在上文中有所提及。总而言之，我们研究各种策略的目的是一致的，那就是要有效地解决问题。相信通过不断的学习，并与其他同学以及教练们进行交流探讨，一定会探索出更多，更具价值的策略。四 结 语我们知道，无论算法如何优化，所解决的问题规模终究是有限的，因此解决规模化问题时，首先应明确问题的实际规模，然后量“体”裁“衣” ，设计适用的算法。有时题中还会对问题规模加上了一定的限制条件，例如 IOI99隐藏的码字中，文本的最大长度为 1,000,000，而“右侧最小”覆盖序列的总数却不超过 10,000 个，这就使得问题的实际规模大大降低。所以，审好题是解决规模化问题的第一步。