算法合集之《浅析非完美算法在信息学竞赛中的应用》

非完美算法在信息学竞赛中的应用胡伟栋第1页，共17页浅析非完美算法在信息学竞赛中的应用湖南省长沙市长郡中学胡伟栋【目录】摘要2关键字2正文2引言2非完美算法的一些基本方法3随机贪心法3抽样测试法4部分忽略法8完美算法的依据——RP类问题与Monte-Carlo算法11非完美算法的共性11非完美算法的优点与缺点12总结13感谢13参考文献13附录13非完美算法在信息学竞赛中的应用胡伟栋第2页，共17页【摘要】非完美算法就是用算法正确性的少量损失来换取时间、空间效率以及编程复杂度的算法。本文介绍了非完美算法的几种重要方法及非完美算法的优缺点，从中，可以看出：并不是完全正确的算法就一定好过非完美算法，有可能因为非完美算法的不完全性，反而使不正确的算法在很多方面比正确算法表现得更好。【关键字】非完美算法随机化贪心法抽样测试法部分忽略法【正文】一、引言在平时，我们研究的算法基本都是完全正确的算法，我们所追求的，也是尽量使我们的算法正确。但在实际应用中，有很多情况都不会对数据进行天衣无缝的正确处理。如：图片、音频、视频的压缩存储，很多压缩率比较高的方法都是有损压缩；很多密码验证的方法都是采用多对一的运算方法，通过验证的不代表密码真正正确；搜索引擎所提供的搜索，并不能将所有满足条件的都找到……显然，我们不会因为它们的不完美而不使用它们，它们的存在，有着它们的实际意义：图片、音频、视频的压缩存储，如果不损失一些，不可能将文件压缩得很小；密码验证虽是多对一，但找到两个所对的是同一个何尝容易；搜索引擎虽不能搜索到100%的结果，但其方便、快捷是无以伦比的……那么，在信息学竞赛中是否也可以用非完美算法解题呢？本文试图介绍一些比较有用的常见非完美算法，并希望读者能从此得到一些启发。在开始此文前，希望读者能认同一点：在信息学乃至整个计算机科学领域，不一定绝对正确的算法就是最好的算法，有可能一个在绝大多数情况下正确的算法(非完美算法)比一个完全正确的算法更有前途。或者，由于它没有完全正确的非完美算法在信息学竞赛中的应用胡伟栋第3页，共17页算法考虑得全面，而使得它的空间或时间使用得较少；或者，由于它没有正确的算法那么严谨，使得编程实现时较容易；或者，由于所用的知识没有正确算法那么深奥，使得它更容易被接受。二、非完美算法的一些基本方法1.1随机化贪心①法随机化贪心是目前用得较广泛的一种非完美算法。特别是对求较优解的题目，这种方法可以说是首选。随机贪心，就是用随机与贪心结合，在算法的每一步，都尽量使决策取得优，但不一定是最优决策。通过多次运行，使得算法能取得一个较优的解。有时，由于决策的优劣判断较复杂，直接用多次随机也能得到较优的结果。例：传染病控制②题目大意给出一棵传染病传播树，其中根结点是被感染结点。每个时刻，被感染结点都会将传染病传播到它的子结点。但是，如果某时刻t切段A与其父结点B之间的边，则时刻t以后，传染病不会从B传染给A(即A不会患病)。每个时刻，只能切断一条传播途径。问每个时刻怎样切段传播途径，使最少的人被感染。说明本题的标准算法是搜索。关于如何用搜索解决此题，请参见附件《传染病控制解题报告》，此解题报告由周戈林同学提供。分析显然，如果某个结点已被感染，则以后没有必要切断它与它的父结点之间的传播途径，因为这样和不切断没有区别(即切断已被感染的结点与其父结点之间的传播途径是无效的)；如果在一个时刻，切断A与A的父结点之间的传播途径是有效的，切断B与B的父结点之间的传播途径也是有效的，同时，B是A的①随机化贪心在周咏基前辈的《论随机化算法的原理与设计》中有写过，为了此文的完整性，这里将通过一个实例简要的说明。②题目来源：NOIP2003，原题请见附录。非完美算法在信息学竞赛中的应用胡伟栋第4页，共17页子孙结点，则切断A与A的父结点的传播途径优于切断B与B的父结点的传播途径。由于第t时刻被感染的显然只可能是前t层的。因此可得到，第t时刻切断的必然是第t层与第t+1层之间的传播途径。本题可以用随机贪心来做。根据经验，每次将一个结点数最多的子树从原树中切开，结果会比较好。但这样并不能适应所有情况，有时，选结点数第二多的或第三多的反而能使以后的最终结果要好一些。所以，可以多次贪心，每次都随机的选一个能切断的结点数较多的方案切(或者说每次使能切断的结点数多的方案数被切的几率大一些)，这样，虽然大多数情况下其结果都比贪心要差，但只要随机到一定的数量，这中间出现正确答案的概率就很大了。上面加概率的随机贪心有一点难处理的就是怎样设置每种情况被选择的概率。其实，对于此题，只要将每种情况被选到的概率都设成同样大(即被选中的概率与其子结点数无关)就可以了。这样，这种方法就变成了纯粹的随机法，这种方法也能使此题得到满分。小结随机贪心是信息学竞赛中的一个重要工具，由于一般情况下它都是基于简单的贪心，所以往往编程复杂性会比较低，同时运行的时间复杂度也会比较低。随机多次是随机贪心的一个重要手段，通过多次运行，往往能使程序得到非常优的结果。1.2抽样测试法抽样，即从统计总体中，任意抽出一部分单位作为样本，并以其结果推算总体的相应指标。在某些题目中，题设会给出一系列需要测试的测试元(总体)S，若存在某一个测试元满足某个条件A，则说S满足性质P，若所有测试元都不满足条件A，则说S不满足性质P。对于这个总体S，判断它是否满足性质P，通常要将S中所有的测试元全部列举出来才能知道。如果不列举出全部(哪怕只有一个没有列举到)且当前已测试的测试元都不满足条件A，则不敢保证剩下的测试元不满足条件，也就不能断定非完美算法在信息学竞赛中的应用胡伟栋第5页，共17页S是否满足性质P。但是，若总体具有下面的性质：它或者不含满足条件的测试元，或者满足条件的测试元的个数比较多。这时，只要选取一些具有代表性的很少一部分测试元进行测试，就是保证结果基本正确。所谓有代表性，就是指取一些很特殊的测试元，同时取一些不特殊的测试元——就像问卷调查一样，从各种工作岗位、各种年龄阶段的人群中取得的问卷调查结果往往比在同一个工作岗位且年龄相仿的人群中取得的调查结果更让人信服。下面，我们来看一个例子：一个总体S中含有10000个测试元，其中有100个测试元满足条件A，现在，若从S中取出100个测试元进行测试，则检查出S满足性质P的概率约为：63.6%，若取200个测试元，则检查出的概率为86.9%，若取300个，则检查出的概率可达95.3%。下图中给出了取的个数与正确率之间的关系(注意：这里只画了取0至800个时的图像，当取800个以上时，由于其正确率太接近100%，其图像近似一条水平直线而没有再画出的意义)：从图中还可以看出，只要抽样大约70个，就有50%的正确率，抽样大约230个，就有90%的正确率。再看一个例子：如果总体S是{’A’,’B’,…,’Z’}的所有子集，而条件A是同时含有’A’~’G’的子集。按照上面，根据上面一例，可以想到，如果取一定量的子集测试，效果也会比较好，但好，对于总体S，它存在一些特殊的子集——如空集、全集{’A’,’B’,…,’Z’}、只含一个元素的集合{’A’},{’B’}……这些都是我们认为比较特殊的集合，如果从这些特殊的集合中先取出几个测试，则可能在这些非完美算法在信息学竞赛中的应用胡伟栋第6页，共17页集合中就能找到满足条件A的，如此例中取全集显然就会满足条件。下面看一个具体的实例：例：IntuitionisticLogic(直觉主义逻辑)③题目大意给定一个有向无环图G=(V,E)，在顶点V之间建立一些偏序关系：对于x,yV，定义x≤y当且仅当x到y之间存在路径(可能长度为0)。对于一个顶点集合S，定义Max(S)为S中所有最大元素的集合(即Max(S)中的任意一个顶点都不可能通过一条或多条E中的边到达S中的其他顶点)，写成表达式的形式为：Max(S)={xS|不存在yS,x≠y,x≤y}令β为所有满足Max(S)=S的集合所组成的集合，即：β={S|Max(S)=S}令0=Max(V)，1=，显然0和1都属于β定义β中元素的一些操作：P=Q={xQ|不存在yP,x≤y},PQ=Max(P∪Q),PQ=Max({xV|存在yP,zQ,x≤y,x≤z}),P=(P=0),P≡Q=((P=Q)(P=Q))问题：对于一个含有变量的表达式，问是否无论变量如何在β中取值，其运算结果都是1？数据范围：其中|V|≤100；|E|≤5000；对于同一个图，要处理k个表示式，k≤20；每个表达式长度不超过254个字符；|β|≤100；6110jvjkH(vj是在第j个表达式中用到的变量个数)分析本题的最后一个数据范围6110jvjkH其实暗示了我们，此题可以用枚举来做，即枚举所有变量的所有可能取值。显然，如果要求完全正确，变量取值的总方案数是不可能减少的，即可能达到106，这时，就得设法减少计算的复杂度。显然，上面的基本运算都是O(|V|)或O(|E|)或更高的，而计算一个表达式可能要③题目来源：ACMICPC2002-2003,NortheasternEuropeanRegion,NorthernSubregion，原题请见附件。非完美算法在信息学竞赛中的应用胡伟栋第7页，共17页使用上百次基本运算，这样，尽管此题有5秒的时限，这样的枚举也是很难出解的。由|β|≤100，可以想到，将β中的每一个元素先用一个整数代替，并计算出对这些数进行上面的基本运算所得的值(当然也用整数表示)。对这些值列一个表，以后计算时就只要从表中查找结果了。这样，基本运算的复杂度就可以降到O(1)，总的复杂度就可以降为1(*||)jvjkOHB。此题还有一种解决方法，那就是抽样。将变量取β中一些比较特殊的值(如0，1，……)看作特殊样品，其它的看作一般样品。抽取一些特殊样品和一些一般样品，对它们进行测试，如果对于一个式子，所有的样品都满足条件，则说明式子满足条件，否则说式子满足条件。实践证明，只要抽取不到1000个样品即可得到比较高的正确率。当然，对于这类多测试数据的题目，要基本保证一个测试点对，每组测试数据的正确概率必须更高一些。如：对于有20个组测试数据的测试点，如果保证每组数据的正确概率为95%，则整个测试点的正确概率只有0.9520，还不到36%；如果保证每组数据的正确概率为99%，整个测试点的正确概率才82%；如果每组数据正确概率达到99.9%，则整个测试点的正确概率就会有98%。这里特别要说明的是：一般情况下，抽样的数目应该尽量多(在保证不超时的前提下)，这样才能保证正确概率较大。抽样法的实际运用：在测试质数时，抽样法是一个非常有用的工具。下面给出一种质数判定方法：对于待判定的整数n。设n-1=d*2s(d是奇数)。对于给定的基底a，若1(mod)dan或存在0≤rs使*21(mod)rdan则称n为以a为底的强伪质数(StrongPseudoprime)。利用二分法，可以在O(log2n)的时间内判定n是否为以a为底的强伪质数。对于合数c，以小于c的数为底，c至多有1/4的机会为强伪质数(Monier1980,Rabin1980)。非完美算法在信息学竞赛中的应用胡伟栋第8页，共17页根据这条，判断一个数n是否为质数，可以随机地抽取小于n的k个数为底。这样，正确的概率不小于1-4-k。显然，这已经非常优秀了，通常只要取几十组就可以保证基本正确。如果不是随机抽样，而是抽样特殊情况——最小的几个质数，则：④如果只用2一个数进行测试，最小的强伪质数(反例)是2047(所以一个数显然不够)；如果用2和3两个数进行测试，最小的强伪质数大于106；如果用2,3,5进行测试，最小的强伪质数大于2×107；如果用2,3,5,7进行测试，最小的强伪质数大于3×109，已经比32位带符号整数的最大值(Pascal中的Maxlongint)还大了。可见，通常只要抽取2,3,5,7这几个固定的数进行测试就能保证测试的正确性了。我们知道，最朴素的质