资源描述:
《规模化问题的解题策略》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、规模化问题的解题策略长沙市一中●谢婧规模化问题的解题策略湖南省长沙市第一中学谢婧【关键字】规模化策略算法【摘要】问题规模化是近来信息学竞赛的一个新趋势,它意在通过扩大数据量来增加算法设计和编程实现的难度,这就向信息学竞赛的选手提出了更高层次的要求,本文试图探索一些解决此类问题的普遍性的策略。开始,本文给出了“规模化”一词的定义,并据此将其分为横向扩展和纵向扩展两种类型,分别进行论述。在探讨横向扩展问题的解决时本文是以谋划策略的“降维”思想为主要对象的;而重点讨论的是纵向扩展问题的解决,先提出了两种策略——分解法和
2、精简法,然后结合一个具体例子研究“剪枝”在规模化问题中的应用。问题规模化是信息学竞赛向实际运用靠拢的一个体现,因此具有不可忽视的意义。【正文】一引论(一)背景分析分析近年来国际、国内中学生信息学竞赛试题,可以看出信息学竞赛对于选手的要求已经不再仅仅局限于“算法设计”,它同时在编程实现方面加强了考察力度,由侧重于考察理论知识转向理论考察与实践考察并重。这一命题宗旨的转变,给信息学竞赛注入了新的机能,为命题者开拓了另一个领域。其一体现有:试题由精巧型(这类试题的难度主要体现在精妙算法的构造,属于一点即通的类型)向规模
3、型发展,从而使得问题的实现复杂化。(二)对“规模化”的理解规模一词在字典中的含义是:事物所具有的格式、形式或范围。在信息学竞赛中,问题的规模具体是指待处理数据量的大小,通常可以通过一组规模参数(S1,S2,…,Sk)来表示。例如下列问题1的规模就是(100),而问题2的规模是(100,100)。问题1:求数列的前100项之和。问题2:求100*100的矩阵中的各项之和。问题3:求数列的前1000项之和。“规模化”-21-规模化问题的解题策略长沙市一中●谢婧即扩展问题的规模,它具体是指增加规模参数的个数或扩大规模参
4、数的数值范围。我们知道,如果撇开计算机的硬件、软件等环境因素,可以认为一个特定算法的“运行工作量”的大小,只依赖于问题的规模,或者说,它是问题规模的函数,程序的执行时间与存储量需求直接受到问题规模的影响。由于种种现行条件的制约,随着规模扩展,问题的实际解法集便会缩小,甚至变为空集,这有时会使问题规模扩展后无法用原来小规模时的理想模型解决。如NOI’99《生日蛋糕》一题,理论上可以用动态规划的方法求解,但因其空间耗费过大,多数人是用搜索来实现的。从“规模化”一词的定义不难看出,它包括横向扩展和纵向扩展。横向扩展是指
5、增加规模参数的个数,如由问题1扩展至问题2,即我们通常说的多维化;纵向扩展是指扩大规模参数的数值范围,如由问题1扩展至问题3。下文将分别探讨这两类问题的一般性解题策略。二横向扩展问题的解题策略(一)构造策略的思想横向扩展问题一般具有维数高、难于构想的特点,所以谋划解决这一类问题的策略,通常采用“降维”[1]的思想:分析低维问题,找到解法,推广至高维的情况。下面我们就来看一个具体例子。问题一:对于一个n维体P((S1,T1),(S2,T2),…,(Sn,Tn)),Si、Ti(i=1..n)均为整数,我们定义其阶积=
6、(T1-S1)*(T2-S2)*…*(Tn-Sn),并称(Ti-Si)是P的一个要素i。如果存在另一个n维体Q((S1`,T1`),(S2`,T2`),…,(Sn`,Tn`)),使得Si`≥Si(i=1..n),且Ti`≤Ti(i=1..n),Si`、Ti`(i=1..n)也是整数,则称Q是P的子n维体。现给定一个n维体((0,A1),(0,A2),…,(0,An)),求它所有子n维体的阶积和。〖问题分析〗:如果泛泛地从n维体入手,会觉得无所适从,根据要求“所有子n维体的阶积和”,我们可以枚举所有的子n维体,其时
7、间复杂度高达O(m2n)(其中m表示Ai(i=1..n)的一般规模),效率不高的主要原因是数学模型不够抽象,而好的数学模型是建立在问题本质基础上的。所以说,如果我们对问题缺乏认识或认识不深,就不可能高效地解决它。这就是笼统的考虑横向扩展问题的弊病。下面我们根据上文提到的“降维”思想来解决此题。第一步:降低问题的规模。我们先从简单模型入手,来看一看n=1时的情况,我们把一维体((0,A1))体现在在下图所示的一根数轴上,这里不妨把一维体看成一条线段,其阶积就是线段的长度。01234A1-1A1-21-规模化问题的解
8、题策略长沙市一中●谢婧第二步:在低维问题中求找规律。试想把长度相同的子线段归类统计,那么对于长度为L的线段(s,s+L):∵s+L≤A1∴s≤A1-L又∵s≥0,∴0≤s≤A1-L,这样的子线段共有A1+1-L条。所以,一维体((0,A1))的所有子一维体的阶积和为Σi*(A1+1-i){i=1..A1},设为Fg(A1)。第三步:将规律推广至高维问题。我们将模型稍加推广