资源描述：
《论文张一飞论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、冗繁削尽留清瘦——浅谈信息的充分利用长沙市雅礼屮学张一飞【摘要】在算法设计中，人们往往不自觉地进行了大量多余的运算,这些累赘将大大降低算法的效率。作者认为，充分利用已知信息,是解决这一问题的一个有效方法。所谓充分利用信息，就是在算法设计中，把已知信息尽可能充分地利用起来，以避免冗余运算，降低算法的时空复杂度，从而提高算法的效率。本文对充分利用信息，在优化回溯法、动态规划和数值计算中的应用作了初步的探讨。［关键字】信息，算法优化“冗繁削尽留清瘦”山虽然讲的是画竹，却包含着深刻的哲理。算法设计同画竹一-样，也需要削尽兀繁。但在解题实践屮，人们往往不
2、自觉地做了一些多余的运算，而忽视了对已知信息的充分利用。所谓充分利用信息，就是在算法设计中，把已知信息尽可能充分地利用起来,以避免兀余运算，降低算法的时空复朵度，从而提高算法的效率。限于篇幅，本文仅对这种方法提高回溯法、动态规划和数值计算的效率进行探讨。提高回溯法的效率我们知道，冋溯法实质上是从树根出发，遍历一棵解答树的过程。如果解答树中存在一些性质相同的子树，那么，只耍我们知道了具中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索121的基木思想。记忆化搜索避免了一些多余的运算，因而比非记忆化搜索效率耍高。但在
3、有些记忆化搜索屮，对信息的利用仍不够充分，还有进一步优化的余地。下面，我们看一个例子：【序关系计数问题】用关系'V，和^将3个数A、B和C依次排列有13种不同的关系：AvBvC,A.枚举出所有的序关系表达式我们可以采用回溯法枚举出所有的序关系表达式。N个数的序关系表达式，是通过N个人写字母和连接各字母的N・1个关系符号构成。依次枚举每个位置上的大写字母和关系符号
4、，直到确定一个序关系表达式为止。出于类似于'A二B，和卞二A，的序关系表达式是等价的，为此，规定等号前面的人写字母在ASCII表中的序号，必须比等号后面的字母序号小。基于这个思想,我们很容易写出解这道题冃的凹溯算法。算法计算N个数的序关系数。procedureCount(Step,First,Can);(Step表示当前确定第Step个大写字母;First表示当前大写字母可能取到的最小值;Can是一个集合,集合中的元素是述可以使用的大写字母｝beginifStep=Nthenbegin｛确定最后一个字母｝fori:=FirsttoNdoifii
5、nCanthenInc(Total);｛Total为统计的结果｝Exitend;fori:=FirsttoNdo｛枚举当前的大写字母｝ifiinCanthenhegin｛i可以使用｝Count(Step+7,i+J,Cart-[i]);｛添等于号｝Count(Step七添小于号｝endend;调用Coum(l,l,[l..N])后，Total的值就是结果。该算法的时间复杂度是0(N!)〈2〉•粗略利用信息，优化算法1-1算法1-1中存在大量冗余运算。如图1,三个方框内子树的形态完全一样。-旦我们知道了其中某一个方框内所产生的序关系数，就可以利用
6、这个信息，直接得到另两个方框内将耍产生的序关系数。图1N=3时的解答树Root显然，在枚举的过程屮，若已经确定了前k个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的N・k个数所能产生的序关系数。设i个数共有F[i]种不同的序关系，那么，由上面的讨论可知，在算法1-1中，调用一次Count(Step+l,l,Can-[i])之后，Total的增量应该是F[N-Step]0这个值可以在第一次调用Count(Step+l,l,Can-[i])时求出。而一旦知道了F[N-Step]的值,就可以用Total:=Total+F[N-Ste
7、p]代替调用Count(Step+l,l,Can-[i])o这样，我们可以得到改进后的算法1・2。算法12,计算N个数的序关系数。procedureCount(Step,First,Can);｛Step,First,Ccm的含义同算法1・1｝beginifStep=Nthenbegin｛确定最后一个字母｝fori:=FirsttoNdoifiinCanthenInc(Total);｛Total为统计的结果｝Exitend;fori:=FirsttoNdo｛枚举当前的大写字母｝ifiinCanthenbegin｛i可以使用｝Count(StepC
8、cin・[i]);｛添等于号｝ifF[N・Step]=・lthenbegin｛第一次调用｝F[N-Step]:=Total;r=jCount(Step
