冗繁削尽留清瘦——浅谈信息的充分利用 张一飞
冗繁削尽留清瘦
——浅谈信息的充分利用
长沙市雅礼中学 张一飞
【摘要】
在算法设计中，人们往往不自觉地进行了大量多余的运算，这些累赘将大大降低算法的效率。作者认为，充分利用已知信息，是解决这一问题的一个有效方法。
所谓充分利用信息，就是在算法设计中，把已知信息尽可能充分地利用起来，以避免冗余运算，降低算法的时空复杂度，从而提高算法的效率。本文对充分利用信息，在优化回溯法、动态规划和数值计算中的应用作了初步的探讨。
【关键字】
信息，算法优化
“冗繁削尽留清瘦”[1]虽然讲的是画竹，却包含着深刻的哲理。算法设计同画竹一样，也需要削尽冗繁。但在解题实践中，人们往往不自觉地做了一些多余的运算，而忽视了对已知信息的充分利用。
所谓充分利用信息，就是在算法设计中，把已知信息尽可能充分地利用起来，以避免冗余运算，降低算法的时空复杂度，从而提高算法的效率。限于篇幅，本文仅对这种方法提高回溯法、动态规划和数值计算的效率进行探讨。
一、 提高回溯法的效率
我们知道，回溯法实质上是从树根出发，遍历一棵解答树的过程。如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索[2]的基本思想。
记忆化搜索避免了一些多余的运算，因而比非记忆化搜索效率要高。但在有些记忆化搜索中，对信息的利用仍不够充分，还有进一步优化的余地。
下面，我们看一个例子：
【序关系计数问题】
用关系’<’和’=’将3个数A、B和C依次排列有13种不同的关系：
A
<1>.枚举出所有的序关系表达式
第 1 页
冗繁削尽留清瘦——浅谈信息的充分利用 张一飞
我们可以采用回溯法枚举出所有的序关系表达式。N个数的序关系表达式，是通过N个大写字母和连接各字母的N-1个关系符号构成。依次枚举每个位置上的大写字母和关系符号，直到确定一个序关系表达式为止。
由于类似于‘A=B’和‘B=A’的序关系表达式是等价的，为此，规定等号前面的大写字母在ASCII表中的序号，必须比等号后面的字母序号小。基于这个思想，我们很容易写出解这道题目的回溯算法。
算法1-1，计算N个数的序关系数。 procedure Count(Step,First,Can);
{Step表示当前确定第Step个大写字母；
First表示当前大写字母可能取到的最小值；
Can是一个集合，集合中的元素是还可以使用的大写字母} begin
if Step=N then begin{确定最后一个字母}
for i:=First to N do if i in Can then Inc(Total); {Total为统计的结果} Exit end;
for i:=First to N do{枚举当前的大写字母} if i in Can then begin{i可以使用}
Count(Step+1,i+1,Can-[i]);{添等于号} Count(Step+1,1,Can-[i]){添小于号} end end;
调用Count(1,1,[1..N])后，Total的值就是结果。该算法的时间复杂度是O(N!)
<2>.粗略利用信息，优化算法1-1
算法1-1中存在大量冗余运算。如图1，三个方框内子树的形态完全一样。一旦我们知道了其中某一个方框内所产生的序关系数，就可以利用这个信息，直接得到另两个方框内将要产生的序关系数。
图1 N=3时的解答树
显然，在枚举的过程中，若已经确定了前k个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的N-k个数所能产生的序关系数。
设i个数共有F[i]种不同的序关系，那么，由上面的讨论可知，在算法1-1中，调用一次Count(Step+1,1,Can-[i])之后，Total的增量应该是F[N-Step]。这个
第 2 页
冗繁削尽留清瘦——浅谈信息的充分利用 张一飞
值可以在第一次调用Count(Step+1,1,Can-[i])时求出。而一旦知道了F[N-Step]的值，就可以用Total:=Total+F[N-Step] 代替调用Count(Step+1,1,Can-[i])。这样，我们可以得到改进后的算法1-2。
算法1-2，计算N个数的序关系数。 procedure Count(Step,First,Can); {Step,First,Can的含义同算法1-1} begin
if Step=N then begin {确定最后一个字母}
for i:=First to N do if i in Can then Inc(Total); {Total为统计的结果} Exit end;
for i:=First to N do {枚举当前的大写字母} if i in Can then begin {i可以使用}
Count(Step+1,i+1,Can-[i]); {添等于号} if F[N-Step]=-1 then begin {第一次调用} F[N-Step]:=Total;
Count(Step+1,1,Can-[i]); {添小于号}
F[N-Step]:=Total-F[N-Step] {F[N-Step]=Total的增量} end else Total:=Total+F[N-Step] {F[N-Step]已经求出} end end;
开始，将F[0],F[1],…,F[N-1]初始化为-1
调用Count(1,1,[1..N])之后，Total的值就是结果
算法1-2与算法1-1的差别仅限于程序中的粗体部分。
算法1-2就是利用了F[0],F[1],…,F[N-1]的值，使得在确定添小于号以后，能够避免多余的搜索，尽快地求出所需要的方案数。该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为O(2N)[3]。同算法1-1相比，效率虽然有所提高，但仍不够理想。
<3>.充分利用信息，进一步优化算法1-2
在搜索的过程中，如果确定在第k个大写字母之后添加第一个小于号，则可得到下面两条信息：
图2充分利用信息，进一步优化算法1-2 第一条信息：前k个大写字母都是用等号连接的。 第 3 页
冗繁削尽留清瘦——浅谈信息的充分利用 张一飞
第二条信息：在此基础上继续搜索，将产生F[N-k]个序关系表达式。
如图2所示，序关系表达式中第一个小于号将整个表达式分成了两个部分。由乘法原理易知，图2所示的序关系表达式的总数，就是图中前半部分所能产生的序关系数，乘以后半部分所能产生的序关系数。算法1-2实质上利用了第二条信息，直接得到图中后半部分将产生F[n-k]个序关系数，并通过搜索得到前半部分将产生的序关系数。但如果我们利用第一条信息，就可以推知图中前半部分将产生的序关系数，就是N个物体中取k个的组合数，即Cnk。这样，我们可以得到F[n] 的递推关系式：
n公式1：F[n]??Ck?1knF[n?k]，其中F[0]?1
采用公式1计算F[n]的算法记为算法1-3[4]，它的时间复杂度是O(N2)。
<4>.小结
下面是三个算法的性能分析表[5]： 分析项目 算法1-1 算法1-2 算法1-3 NO(N!) O(2) O(N2) 理论时间复杂度 O(1) O(N) O(N) 分析 空间复杂度 N=7 1s <0.05s <0.05s 实际N=8 10s <0.05s <0.05s 运行N=15 >10s 0.5s <0.05s 情况 N=17 >10s 2s <0.05s
在优化算法1-1的过程中，我们通过利用F[0],F[1]…,F[N-1]的信息，得到算
法1-2，时间复杂度也从O(N!)降到O(2N)。在算法1-2中，进一步消除冗余运算，就得到了O(N2)的算法1-3。
算法1-3计算F[n]，体现了动态规划的思想。也就是说，我们通过充分利用信息，提高回溯法的效率，实质上是将搜索转化成了动态规划。
二、 提高动态规划的效率
从上一节中可以看到，动态规划之所以高效，就在于它比较充分的利用了已知信息。但是，在有些动态规划中，仍存在冗余运算。这一节我们将进一步探讨如何充分利用信息，提高动态规划的效率。
下面我们看一个例子：
【理想收入问题】
理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。
已知股票在第i天每股价格是V[i]元，1≤i≤M，求M天后的理想收入。
<1>.一种动态规划的解法
解这道题目，很容易想到用动态规划。设F[i]表示在第i天收盘时能达到的最高收入，则有F[i]的递推关系式：
公式2：F[i]?max(0?j?k?i){F[j]/V[k]*V[i]}，其中F[0]?1，V[0]?1
公式2的含义是：在第i天收盘时能达到的最高的收入，是将第j天收盘后
第 4 页
冗繁削尽留清瘦——浅谈信息的充分利用 张一飞
的收入，全部用于买入第k天的股票，再在第i天将所持的股票全部卖出所得的收入。采用公式2，可以得到算法2-1，其时间复杂度是O(M3)，空间复杂度是O(M)。
算法2-1
F[0]:=1;V[0]:=1;F[1..M]:=0; for i:=1 to M do for j:=0 to i-1 do for k:=j to i-1 do
F[i]:=Max{F[i],F[j]/V[k]*V[i]}
<2>.改变状态表示的含义，优化算法2-1
改变动态规划中状态表示的含义，是优化动态规划的常用方法。例如此题，我们可以采用两种不同的状态表示方法优化算法2-1。
方法1：设P[i]表示前i天能获得的最多股票数，可列出如下状态转移方程：
公式3：P[i]?max(0?j?i){P[i?1],P[j]*V[j]/V[i]} 这是因为前i天所能获得的最多股票数，或者是前i-1天获得的最多股票数，或者是在第j天将前j天所能获得的最多的股票全部卖出，再买入第i天的股票。显然，前i-1天能获得的最多股票数乘以第i天的股价，就是第i天能达到的最大收入。
方法2：设Q[i]表示前i天能达到的最大收入，可列出如下状态转移方程：
公式4：Q[i]?max(0?j?i){Q[i?1],Q[j]/V[j]*V[i]} 就是说前i天所能达到的最大收入，或者是前i-1天所能达到的的最大收入，或者是在第j天买入股票，再在第i天卖出，所能获得的最大收入。
上述两种方法的时间复杂度都是O(M2)。这表明，改变状态表示的含义，在一定程度上提高了算法的效率。但对于这道题目，仅仅改变状态表示的含义，很难进一步优化算法。
<3>.粗略利用信息，优化算法2-1
算法2-1粗体部分的功能是确定F[i]所能达到的最大值。由于V[i]不变，因此F[i]达到最大值，当且仅当F[j]/V[k]达到最大值，其中0≤j≤k 算法2-1中，采用了二重循环来确定F[j]/V[k]的最大值。但在确定F[i-1]所能达到最大值的时候，我们实际上已经求出当0≤j≤k 第 5 页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库国家集训队2000论文集 张一飞论文在线全文阅读。
相关推荐：