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

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

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

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

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

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

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

6、C模型不能直接应用“两头烧”，因为这样套用的话，0.5+0.5仍然等于1。我们需要对“两头烧”做进一步改进：如果一根香只烧了一头，当剩余时间为t的时候，我们把另一头也点燃——那么，我们就能够计出t/2的时间了（前提是我们已知当前剩余时间t）。特别地，当t=60min时，t/2=30min。根据这一改进后的方法，我们很容易就得出正确的解法：分别点燃第一根的两头和第二根的一头，第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；当第二根也烧完了，即时间又过了15分钟。那么我们计

7、出的总的时间就为45分钟了。【小结】上面这个例子中，我们从构造模型和改进算法两方面入手，一步一步地达到了优化的解法。主要流程是：1.找出原始解法和可能改进的方向（即分析成A、B、C模型）；2.分析算法的原理（由烧一根香计时半小时，引申为烧剩t的时候点两头就能计时）；1.改进算法（改进的过程中，往往不是依靠算法改进算法本身，反而是利用算法的内涵、实质，结合问题，构造算法）；2.解决问题（我们得出了正确的解法）。但是如何来改进原有的算法呢，笔者认为可以有以下途径：1.直接增加算法的规模，解决问题2.用

8、枚举处理增加的规模，从而解决问题3.用贪心解决增加的规模，从而解决问题4.以上各个途径的综合运用围绕这一主线，笔者将用例题做进一步的阐明。三、改进算法的途径(1)直接增加算法的规模，解决问题解决简单的问题，常常可以采用直接处理的方法，但是很多时候还是需要一些技巧。【例一】街道问题及其扩展。（经典问题）【题目大意】〖原题〗在右图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。〖扩展〗在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的