0%

动态规划之——简化递归算法

简化递归算法

在读《数据结构与算法分析》一书[算法设计技巧]一章时,其中提到了将递归实现简化为非递归实现的方法,
而这种方法正是动态规划的关键思想。

任何数学递归公式都可以翻译成递归算法;但是递归算法的编程实现有可能是非常复杂且低效的。
此时,将递归算法重新写成非递归算法,将子问题的计算结果系统地记录在某种表内。
利用这种方法的一种算法技巧叫做动态规划(Dynamic Programming)。

从这段话提取出如下信息:

  • 简化递归程序的关键是将子问题14的结果记录在表内,从而避免冗余计算;
  • 动态规划算法也是利用了记录子问题的结果这种方法来解决问题;
  • 动态规划算法包括简化递归实现;

再强调一下动态规划算法的核心就是记住已经解决过的子问题的答案,先计算子问题,再由子问题计算父问题。
回想一下,动态规划思想有3个基本要素:

  • 最优子结构
  • 状态转移方程
  • 边界条件

通常,面对优化问题,我们首先借助动态规划来抽象建模出上述3个要素,进而很直接的写出递归程序实现;
但往往递归程序计算复杂度很高,这个时候重新审视问题的求解实现,使用表记录子问题的答案,将其转化为
非递归实现
,会有出其不意的效果。其实整个过程才是完整的动态规划方法。

换句话说,动态规划解决问题的关键就是记住并利用子问题的答案来得到完整问题的最优解;
那我们使用动态规划解决问题的完整流程应该问:

优化问题->动态规划建模->递归实现->记录子问题结果移除冗余计算->非递归实现

本文先只讨论递归化简,动态规划的思想留待后续完善。

以下2个例子可以体会下简化递归算法带来的性能改善。

斐波那契数列

废话少说,斐波那契数列的数学公式如下:
\begin{align*}
F(0) &= 0 \\\\
F(1) &= 1 \\\\
F(2) &= 1 \\\\
F(n) &= F(n-1)+F(n-2) (n>=3)
\end{align*}

递归实现

根据这个公式,我们可以很自然地写出递归实现:

1
2
3
4
5
6
7
8
9
int Fib(int N) {
if (N <= 0) {
return 0;
} else if (N == 1) {
return 1;
} else {
return Fib(N-1) + Fib(N-2);
}
}

这个递归程序是非常低效的$O(2^N)$,因为它做了很多冗余计算,而冗余计算的增长是爆炸性的,
通常会导致指数级的复杂度。如果提供一个表保留已经计算过的值,避免对已经解过的子问题再进行递归调用,
那么这种指数级爆炸就可以避免。

用一个表代替递归

可以看出,计算$F_N$所需要的只是$F_{N-1}$和$F_{N-2}$,因此只需要记录最近算出的2个斐波那契数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Fibonacci(int N) {
int i;
int last, nexttolast, answer;

if (N <= 0) {
return 0;
} else if (N == 1) {
return 1;
}

last = nexttolast = 1;
for(i=2; i<=N; i++) {
answer = last + nexttolast;
nexttolast = last;
last = answer;
}
return answer;
}

很明显,这个实现的复杂度是线性的$O(N)$。

简化递归关系

这个例子同样来自书里;首先,我们定义递归求和关系:
\begin{align*}
C(N) &= \frac{2}{N} \sum_{i=0}^{N-1} C(i) + N \\\\
C(0) &= 1
\end{align*}

递归实现

根据公式,可以写出如下递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double eval_recursion(int N) {
int i;
double sum;

if (0 == N) {
return 1.0;
} else {
sum = 0.0;
for(i=0; i<N; i++) {
sum += eval_recursion(i);
}
return 2.0 * sum / N + N;
}
}

同样,这个递归实现的复杂度仍然是指数级。

使用表代替递归

使用表记录中间结果,避免冗余计算,得到复杂度为$O(N^2)$的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
double eval_origin(int N) {
int i, j;
double sum, answer;
double *clist;

clist = (double*)malloc(sizeof(double) * (N+1));
if (NULL == clist) {
cout << "Out of space!" << endl;
return -1;
}

clist[0] = 1.0;
for(i=1; i<=N; i++) {
sum = 0.0;
for(j=0; j<i; j++) {
sum += clist[j];
}
clist[i] = 2.0 * sum / i + i;
}

answer = clist[N];
free(clist);

return answer;
}

这样就可以了吗?慢着,仔细看看,上面的程序仍然有冗余计算,可以进一步化简,得到$O(N)$的实现!

进一步优化

让我们先来审视一下上面程序计算的流程:使用表记录下已经求得的$C(…)$,当要计算$C(i)$时,
则利用已知结果求和:$C(i)=C(0) + C(1) + C(2) + … + C(i-1)$,进而得到结果。
只关注求和部分,略去其他,就是下面的过程:
\begin{align*}
& C(0) = 1 \\\\
& C(1) = C(0) \\\\
& C(2) = C(0) + C(1) \\\\
& C(3) = C(0) + C(1) + C(2) \\\\
& C(4) = C(0) + C(1) + C(2) +C(3) \\\\
& C(5) = C(0) + C(1) + C(2) +C(3) + C(4) \\\\
& …
\end{align*}
可以看到,做了冗余的加法;其实只需要记录当前已经求得的和$sum$,然后边计算$C(i)$边更新这个$sum$
就可以了,无需每次都从头计算和值。

进一步优化为$O(N)$的程序实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double eval_simplified(int N) {
int i;
double sum, answer;

sum = 1.0;
answer = 1.0;

for (i=1; i<=N; i++) {
answer = 2.0 * sum / i + i;
sum += answer;
}

return answer;
}

动态规划递归化简的关键是:确保子问题只被计算一次,并保存必要的计算结果;
time-memory trade-off使用额外的空间换取时间。

算法优化奥妙无穷,也是一种对美的探求!