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

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

ID:49070026

大小:169.50 KB

页数:13页

时间:2020-02-27

算法合集之《用改进算法的思想解决规模维数增大的问题》.doc_第1页
算法合集之《用改进算法的思想解决规模维数增大的问题》.doc_第2页
算法合集之《用改进算法的思想解决规模维数增大的问题》.doc_第3页
算法合集之《用改进算法的思想解决规模维数增大的问题》.doc_第4页
算法合集之《用改进算法的思想解决规模维数增大的问题》.doc_第5页
资源描述:

《算法合集之《用改进算法的思想解决规模维数增大的问题》.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)直接增加算法的规模,解决问题解决简单的问题,常常可以采用直接处理的方法,但是很多时候还是需要一些技巧。【例一】街道问题及其扩展。(经典问题)【题目大意】〖原题〗在右图中找出从左下角到右上角的最短路径,每步只能向右方或上方走。〖扩展〗在地图中找出从左下角到右上角的两条路径,两条路径中的任何一条边都不能重叠,并且要求两条路径的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。