《浅析非完美算法在信息学竞赛中的应用》由会员分享，可在线阅读，更多相关《浅析非完美算法在信息学竞赛中的应用（29页珍藏版）》请在金锄头文库上搜索。
1、非完美算法非完美算法 在信息学竞赛中的应用 浅析计算机科学中非完美的例子计算机科学中非完美的例子图片、音频、视频的压缩图片、音频、视频的压缩很多压缩率比较高的压缩方法都是有损压缩很多压缩率比较高的压缩方法都是有损压缩很多压缩率比较高的压缩方法都是有损压缩很多压缩率比较高的压缩方法都是有损压缩密码验证密码验证很多都是多对一，通过验证的不一定是正确的很多都是多对一，通过验证的不一定是正确的很多都是多对一，通过验证的不一定是正确的很多都是多对一，通过验证的不一定是正确的搜索引擎搜索引擎不一定能搜索到所有匹配的内容不一定能搜索到所有匹配的内容不一定能搜索到所有匹配的内容不一定能搜索到所有匹配的内容较小
2、的磁盘空间安全、实用方便、快捷非完美算法非完美算法在信息学乃至整个计算机科学领域，不一在信息学乃至整个计算机科学领域，不一定绝对正确的算法就是最好的算法，有可定绝对正确的算法就是最好的算法，有可能一个在绝大多数情况下正确的算法能一个在绝大多数情况下正确的算法( (非非完美算法完美算法) )比一个完全正确的算法更有前比一个完全正确的算法更有前途。途。时间使用较少时间使用较少时间使用较少时间使用较少空间使用较少空间使用较少空间使用较少空间使用较少实现较容易实现较容易实现较容易实现较容易容易被接受容易被接受容易被接受容易被接受 非完美算法的一些常见方法非完美算法的一些常见方法随机贪心随机贪心抽样测试
3、抽样测试部分忽略部分忽略周咏基论随机化算法的原理与设计 (*)(*)抽样测试法抽样测试法抽样：从统计总体中，任意抽出一部分单抽样：从统计总体中，任意抽出一部分单位作为样本，并以其结果推算总体的相应位作为样本，并以其结果推算总体的相应指标。指标。抽样测试法抽样测试法s满足条件A具有性质P抽样测试法抽样测试法10000个元素100个满足条件只要少量抽样就能取 得较高的正确率抽样测试法抽样测试法在抽样测试时，有时总体中存在一些特殊在抽样测试时，有时总体中存在一些特殊的元素，这些元素满足条件的概率往往与的元素，这些元素满足条件的概率往往与其他元素满足条件的概率相差较大。如果其他元素满足条件的概率相差较
4、大。如果特别的在这些元素中抽取一些进行测试，特别的在这些元素中抽取一些进行测试，则可以加快出解的速度或增大解的正确率。则可以加快出解的速度或增大解的正确率。特殊抽样抽样测试法抽样测试法特殊抽样特殊抽样=A,B,C,Z总体：的所有子集条件：含A,B,C,G的集合取特殊元素即满足条件！质数判定质数判定朴素的质数判定方法：朴素的质数判定方法：用用用用22试除。试除。试除。试除。O O( (n n) )抽样测试法：抽样测试法：在在在在22中抽取中抽取中抽取中抽取k k个试除。个试除。个试除。个试除。Strong Pseudoprime对于奇数对于奇数n和正整数和正整数a，设，设n-1=d2s(d为奇为
5、奇数数)，若：，若：a ad d1 (mod 1 (mod n n) )或或或或存在存在存在存在0 0 r r s s，使，使，使，使 -1 (mod -1 (mod n n) )则称则称n是以是以a为底的为底的强伪质数强伪质数(Strong Pseudoprime)。判断： O(log2n)质数测试质数测试当当a不是不是n的整数倍时，质数的整数倍时，质数n必然是以必然是以a为底为底的强伪质数。的强伪质数。在所有可能的在所有可能的a中，一个合数至多有的机会中，一个合数至多有的机会为强伪质数。为强伪质数。抽样测试：随机抽取抽样测试：随机抽取k个不同的个不同的a进行测试。进行测试。正确率大于正确率
6、大于正确率大于正确率大于1 14 4k k时间复杂度为时间复杂度为时间复杂度为时间复杂度为O O( (k kloglog2 2n n) )。抽样测试质数测试质数测试抽样测试抽样测试特殊抽样：让特殊抽样：让a取最小的若干个质数。取最小的若干个质数。只用只用只用只用2 2测试：最小的强伪质数为测试：最小的强伪质数为测试：最小的强伪质数为测试：最小的强伪质数为20472047，在小于，在小于，在小于，在小于2.5102.5101010中有中有中有中有48424842个强伪质数。个强伪质数。个强伪质数。个强伪质数。只用只用只用只用2,32,3测试：最小强伪质数大于测试：最小强伪质数大于测试：最小强伪质
7、数大于测试：最小强伪质数大于1.3101.3106 6。只用只用只用只用2,3,52,3,5测试：最小强伪质数大于测试：最小强伪质数大于测试：最小强伪质数大于测试：最小强伪质数大于2.5102.5107 7。只用只用只用只用2,3,5,72,3,5,7测试：最小强伪质数大于测试：最小强伪质数大于测试：最小强伪质数大于测试：最小强伪质数大于3.2103.2109 9。质数测试质数测试抽样测试抽样测试一般情况下，只要用一般情况下，只要用2,3,5,7进行测试就能进行测试就能正确的判断一个数是否为质数。正确的判断一个数是否为质数。时间复杂度：时间复杂度：O(log2n)抽样测试法抽样测试法明显降低时
8、间复杂度！抽样测试法部分忽略法部分忽略法在信息学中，可能会遇到这样情况：一个在信息学中，可能会遇到这样情况：一个题的分类非常多，同时某些情况的处理非题的分类非常多，同时某些情况的处理非常复杂，但这些情况往往不是主要情况常复杂，但这些情况往往不是主要情况(即即出现的概率很小或不处理这些情况对答案出现的概率很小或不处理这些情况对答案不会造成很大的影响不会造成很大的影响)。有时，忽略这些复。有时，忽略这些复杂却对结果影响不大的情况仍然可以达到杂却对结果影响不大的情况仍然可以达到令人满意的结果。令人满意的结果。部分忽略法部分忽略法ProblemABD30%40%正确率：99%C29%1%少多少非常多情
9、况 出现率 处理用时判断点是否在多边形内判断点是否在多边形内给出一个点和一个简单多边形给出一个点和一个简单多边形(设点不在多设点不在多边形的边上边形的边上)，判断点是否在多边形内。，判断点是否在多边形内。方法：方法：判断点是否在多边形内判断点是否在多边形内特殊情况：特殊情况：忽略特殊情况 ！？ABCD判断点是否在多边形内判断点是否在多边形内射线经过多边形的顶点是一种非常特殊的射线经过多边形的顶点是一种非常特殊的情况。情况。而我们取的是一条非常特殊的射线而我们取的是一条非常特殊的射线与与x轴平行的射线。轴平行的射线。经验表明，特殊的射线经过多边形的顶点经验表明，特殊的射线经过多边形的顶点的几率会
10、大于一般的射线！的几率会大于一般的射线！解决方法：解决方法：取一条一般的射线！判断点是否在多边形内判断点是否在多边形内ABCD判断点是否在多边形内判断点是否在多边形内多取几条！将出现次数最多的结果作为正确结果设取一条射线，其经过多边形顶点的概率为x，取n条，所得结果的正确率不小于1-xn/2部分忽略部分忽略部分忽略法能减轻我们的思维负担和编程部分忽略法能减轻我们的思维负担和编程复杂性。复杂性。部分忽略法通常要加入一些小小的技巧。部分忽略法通常要加入一些小小的技巧。使使被忽略的情况对结果影响尽量小！非完美算法非完美算法共同点：共同点：不完全性不完全性不完全性不完全性优点 时空消耗低 编程复杂度低
11、思维复杂度低 能减少编程错误 缺点 不完全正确总结总结在信息学竞赛以及实际应用中，并不是完在信息学竞赛以及实际应用中，并不是完全正确的算法就一定比非完美的算法表现全正确的算法就一定比非完美的算法表现得好，因为非完美算法的不完全性，反而得好，因为非完美算法的不完全性，反而使非完美算法在一些方面比正确算法表现使非完美算法在一些方面比正确算法表现得更好。因此，得更好。因此，合理的使用合理的使用非完美算法能非完美算法能取得非常令人满意的结果。取得非常令人满意的结果。 忠告忠告在能用完全正确的算法时要尽量使用完全正在能用完全正确的算法时要尽量使用完全正确的算法，只有当确实难想到很好的方法或确的算法，只有当确实难想到很好的方法或时间比较紧时才使用非完美算法。时间比较紧时才使用非完美算法。结束语结束语想了解更多，欢迎阅读我的论文。里面还想了解更多，欢迎阅读我的论文。里面还有一些更好玩的例子，如：有一些更好玩的例子，如：NOIP2003的的传染病控制传染病控制、ACM的的直觉主义逻辑直觉主义逻辑以及以及IOI2004的的Polygon。谢谢
