奥林匹克竞赛论文-《用改进算法的思想解决规模维数增大的问题》参考文件.docVIP

从1到2，从2到3——用改进算法的思想解决规模维数增大的问题 广东省韶关一中 张伟达 PAGE PAGE 4 用改进算法的思想解决规模维数增大的问题 广东韶关一中 张伟达 【关键字】 增大规模 改进算法 降维 分析 构造 【摘要】 我们常常会遇到一些特殊的问题，它们把我们能够解决的问题改了一改，增加了一维，或者增加了一个因素，从1到2或者是从2到3，本文把它们统称规模维数增大的问题。 解决这类问题可以用改进算法的思想：本文第一部分先是概述这种思想；第二部分则从一道有趣的IQ题目说起，引入改进算法的基本思路和基本途径；第三部分则用多个例子解释说明如何改进算法；最后一部分是总结改进算法的思想。 【目录】 TOC \o 1-4 \h \z 一、概述 2 二、引子：从一道IQ题说起 2 三、改进算法的途径 3 (1)直接增加算法的规模，解决问题 3 【例一】街道问题及其扩展。（经典问题） 3 (2)用枚举处理增加的规模，从而解决问题 4 【例二】旅行（广东省奥林匹克竞赛2001） 4 【例三】炮兵阵地。（NOI2001） 5 (3)用贪心解决增加的规模，从而解决问题 5 【例四】求网络的最小费用最大流。（经典问题） 5 (4)多种途径的综合运用 6 【例五】Team Selection (Balkan OI 2004 Day1) 6 四、总结 9 【感谢】 9 【参考文献】 10 【附录】 11 A.旅行(广东省奥林匹克竞赛2001) 11 B.炮兵阵地（NOI2001） 12 C.Team Selection (BalkanOI 2004 Day 1 Task 2) 13 一、概述 每个学习信息学奥林匹克的选手总是要先学习一些基本的算法，然后才能把算法应用到题目当中去。但是，题目形式多种多样，这些算法往往是不能够直接套用的。有的时候我们分析到某个问题好像可以用某种方法解决，但是这个问题却与之前见过的问题有些不同，例如本文所讨论的情况：问题的规模维数比原问题大，一维的变二维的，二维的变三维的，等等。我们不妨把这类问题叫做规模维数增大的问题，解决这一类问题，往往需要观察问题的特殊性，改进原有算法，从而解决实际问题。 二、引子：从一道IQ题说起 【IQ题题目】在走入正题之前，还是让我们来玩一道IQ题(据说是IBM公司招聘面试用过的题目)：有两根完全相同但分布不均匀的香（提示：不妨假设是蚊香，一圈圈的那种），每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间？ 【……】（思考中） 【思路】在公布答案之前，还是让我们来循序渐进地思考下去吧。 要确定45分钟的时间，而每根香烧完的时间是一个小时，现在应该有三个模型让我们思考： A.不减小每根香的计时，两根香加在一起计时是45分钟； B.只用一根香，使其计时减小，直接计时45分钟； C.把两根香的计时都减小，使两根香加起来是45分钟。 A模型显然是不可能成立的；B、C模型的共同点是：我们必须使一根香的计时减小。但是怎样减，能减成什么呢？显然是不能直接把它们分开的，因为香的分布不均匀。由于这里笔者已经降低了难度，根据提示，比较容易想到香是可以两头一起烧的。这样，我们就能把一根香的计时减成半个小时。方案已经更进一步了。通过这一步，B模型只用一根香，是很容易被排除的。 余下的选择只有“C模型+两头烧方法”了，但是C模型不能直接应用“两头烧”，因为这样套用的话，0.5+0.5仍然等于1。我们需要对“两头烧”做进一步改进：如果一根香只烧了一头，当剩余时间为t的时候，我们把另一头也点燃——那么，我们就能够计出t/2的时间了（前提是我们已知当前剩余时间t）。特别地，当t=60min时，t/2=30min。 根据这一改进后的方法，我们很容易就得出正确的解法：分别点燃第一根的两头和第二根的一头，第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；当第二根也烧完了，即时间又过了15分钟。那么我们计出的总的时间就为45分钟了。 【小结】上面这个例子中，我们从构造模型和改进算法两方面入手，一步一步地达到了优化的解法。主要流程是： 找出原始解法和可能改进的方向（即分析成A、B、C模型）； 分析算法的原理（由烧一根香计时半小时，引申为烧剩t的时候点两头就能计时）； 改进算法（改进的过程中，往往不是依靠算法改进算法本身，反而是利用算法的内涵、实质，结合问题，构造算法）； 解决问题（我们得出了正确的解法）。 但是如何来改进原有的算法呢，笔者认为可以有以下途径： 直接增加算法的规模，解决问题 用枚举处理增加的规模，从而解决问题 用贪心解决增加