算法合集之《用改进算法的思想解决规模维数增大的问题》

《算法合集之《用改进算法的思想解决规模维数增大的问题》》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、从1到2，从2到3——用改进算法的思想解决规模维数增大的问题广东省韶关一中张伟达用改进算法的思想解决规模维数增大的问题广东韶关一中张伟达【关键字】增大规模改进算法降维分析构造【摘要】我们常常会遇到一些特殊的问题，它们把我们能够解决的问题改了一改，增加了一维，或者增加了一个因素，从1到2或者是从2到3，本文把它们统称规模维数增大的问题。解决这类问题可以用改进算法的思想：本文第一部分先是概述这种思想；第二部分则从一道有趣的IQ题目说起，引入改进算法的基本思路和基本途径；第三部分则用多个例子解释说明如何改进算法；最后一部分是总结改进算法的思想。【目录

2、】一、概述2二、引子：从一道IQ题说起2三、改进算法的途径3(1)直接增加算法的规模，解决问题3【例一】街道问题及其扩展。（经典问题）3(2)用枚举处理增加的规模，从而解决问题4【例二】旅行（广东省奥林匹克竞赛2001）4【例三】炮兵阵地。（NOI2001）5(3)用贪心解决增加的规模，从而解决问题5【例四】求网络的最小费用最大流。（经典问题）5(4)多种途径的综合运用6【例五】TeamSelection(BalkanOI2004Day1)6四、总结9【感谢】9【参考文献】10【附录】11A.旅行(广东省奥林匹克竞赛2001)11B.炮兵阵地（

3、NOI2001）12C.TeamSelection(BalkanOI2004Day1Task2)132005集训队论文-13-从1到2，从2到3——用改进算法的思想解决规模维数增大的问题广东省韶关一中张伟达一、概述每个学习信息学奥林匹克的选手总是要先学习一些基本的算法，然后才能把算法应用到题目当中去。但是，题目形式多种多样，这些算法往往是不能够直接套用的。有的时候我们分析到某个问题好像可以用某种方法解决，但是这个问题却与之前见过的问题有些不同，例如本文所讨论的情况：问题的规模维数比原问题大，一维的变二维的，二维的变三维的，等等。我们不妨把这类问

4、题叫做规模维数增大的问题，解决这一类问题，往往需要观察问题的特殊性，改进原有算法，从而解决实际问题。二、引子：从一道IQ题说起【IQ题题目】在走入正题之前，还是让我们来玩一道IQ题(据说是IBM公司招聘面试用过的题目)：有两根完全相同但分布不均匀的香（提示：不妨假设是蚊香，一圈圈的那种），每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间？【……】（思考中）【思路】在公布答案之前，还是让我们来循序渐进地思考下去吧。要确定45分钟的时间，而每根香烧完的时间是一个小时，现在应该有三个模型让我们思考：A.不减小每根香的计时，两根香加在

5、一起计时是45分钟；B.只用一根香，使其计时减小，直接计时45分钟；C.把两根香的计时都减小，使两根香加起来是45分钟。A模型显然是不可能成立的；B、C模型的共同点是：我们必须使一根香的计时减小。但是怎样减，能减成什么呢？显然是不能直接把它们分开的，因为香的分布不均匀。由于这里笔者已经降低了难度，根据提示，比较容易想到香是可以两头一起烧的。这样，我们就能把一根香的计时减成半个小时。方案已经更进一步了。通过这一步，B模型只用一根香，是很容易被排除的。余下的选择只有“C模型+两头烧方法”了，但是C模型不能直接应用“两头烧”，因为这样套用的话，0.5

6、+0.5仍然等于1。我们需要对“两头烧”做进一步改进：如果一根香只烧了一头，当剩余时间为t的时候，我们把另一头也点燃——那么，我们就能够计出t/2的时间了（前提是我们已知当前剩余时间t）。特别地，当t=60min时，t/2=30min。根据这一改进后的方法，我们很容易就得出正确的解法：分别点燃第一根的两头和第二根的一头，第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；当第二根也烧完了，即时间又过了15分钟。那么我们计出的总的时间就为45分钟了。【小结】上面这个例子中，我们从构造模型和改进算法两方面入手，一步一步地达到

7、了优化的解法。主要流程是：1.找出原始解法和可能改进的方向（即分析成A、B、C模型）；2.分析算法的原理（由烧一根香计时半小时，引申为烧剩t2005集训队论文-13-从1到2，从2到3——用改进算法的思想解决规模维数增大的问题广东省韶关一中张伟达的时候点两头就能计时）；1.改进算法（改进的过程中，往往不是依靠算法改进算法本身，反而是利用算法的内涵、实质，结合问题，构造算法）；2.解决问题（我们得出了正确的解法）。但是如何来改进原有的算法呢，笔者认为可以有以下途径：1.直接增加算法的规模，解决问题2.用枚举处理增加的规模，从而解决问题3.用贪心解

8、决增加的规模，从而解决问题4.以上各个途径的综合运用围绕这一主线，笔者将用例题做进一步的阐明。三、改进算法的途径(1)直接增加算法的规模，解决问题解决