动态规划法与分治方法
动态规划 (Dynamic Programming) 与分治方法相似, 都是通过组合子问题的解来求解原问题. 不同的是, 分治方法通常将问题划分为互不相交的子问题, 递归地求解子问题, 再讲它们的解组合起来, 求出原问题的解. 而动态规划应用于子问题重叠的情况, 即不用的子问题具有公共的子子问题. 在这种情况下, 如果采用分治算法, 则分治算法会做许多不必要的工作, 它会反复地求解那些公共子子问题. 对于动态规划法, 它对每个子子问题只求解一次, 将其保存在一个表格中, 从而无需每次求解一个子子问题时都重新计算, 避免了这种不必要的计算工作.
也就是说, 动态规划法与分治方法相比, 是用空间来换时间, 而时间上获得的效益是很客观的, 这是一种典型的时空平衡 (time-memory trade-off) 的策略. 通常, 动态规划法用来求解最优化问题 (optimization problem), 如斐波那契数列求值问题, 钢条切割问题, 0-1 背包问题, 矩阵链乘法问题, 最长公共子序列(LCS) 问题, 最优二叉搜索树问题等.
一般情况下, 动态规划算法的步骤如下:
刻画一个最优解的结构特征.
递归地定义最优解的值.
计算最优解的值, 通常采用自底向上的方法.
利用计算出的信息构造一个最优解.
接下来, 我们将从斐波那契数列求值这个简单的例子入手, 来分析动态规划法的具体步骤和优点.
斐波那契数列
斐波那契数列记为 \(\{f(n)\}\), 其表达式如下:
\[ \left\{ \begin{array}{lr} f(0)=0\\ f(1)=1\\ f(n)=f(n-1)+f(n-2),n\geq 2 \end{array} \right. \]
具体写出前几项, 就是: 0,1,1,2,3,5,8,13,21,34,55,89,144,233......
接下来, 我们将会采用递归法和动态规划法来求解该数列的第 n 项, 即 f(n)的值.
递归法求解
首先, 我们采用递归法来求解斐波那契数列的第 n 项 \(f(n)\), 其算法描述如下:
- function fib(n)
- if n = 0 return 0
- if n = 1 return 1
- return fib(n 1) + fib(n 2)
分析上述伪代码, 先是定义一个函数 fib(n), 用来计算斐波那契数列的第 n 项, 当 \(n\geq 2\)时, 它的返回值会调用函数 fib(n-1)和 fib(n-2). 当 \(n=5\)时, 计算 fib(5)的函数调用情况如下图所示:
在计算 fib(5)时, fib(5)调用 1 次, fib(4)调用 1 次, fib(3)调用 2 次, fib(2)调用 3 次, fib(1)调用 5 次, fib(0)调用 3 次, 一共调用函数 fib()15 次. 由此, 我们可以看到, 在计算 fib(5)时, 存在多次重复的 fib()函数的调用, 当 n 增大时, 重复调用的次数会急剧增加, 如计算 fib(50)时, fib(1)和 fib(0)大约会被调用 \(2.4\times10^{10}\)次. 由此可见, 该算法的效率并不是很高, 因为该算法的运行时间是指数时间.
我们用 Python 实现上述算法, 并计算 f(38)的值及运算时间. Python 代码如下:
- import time
- # recursive method
- def rec_fib(n):
- if n <= 1:
- return n
- else:
- return rec_fib(n-1) + rec_fib(n-2)
- # time cost of cursive method
- t1 = time.time()
- t = rec_fib(38)
- t2 = time.time()
- print('结果:%s, 运行时间:%s'%(t, t2-t1))
输出结果如下:
结果: 39088169, 运行时间: 22.93831205368042
动态规划法求解
在使用递归法来求解斐波那契数列的第 n 项时, 我们看到了递归法的不足之处, 因为递归法在使用过程中存在大量重复的函数调用, 因此, 效率很差, 运行时间为指数时间. 为了解决递归法存在的问题, 我们可以尝试动态规划法, 因为动态规划法会在运行过程中, 保存上一个子问题的解, 从而避免了重复求解子问题. 对于求解斐波那契数列的第 n 项, 我们在使用动态规划法时, 需要保存 f(n-1)和 f(n-2)的值, 牺牲一点内存, 但是可以显著地提升运行效率.
动态规划法来求解斐波那契数列第 n 项的伪代码如下:
- function fib(n)
- var previousFib := 0, currentFib := 1
- if n = 0
- return 0
- else if n = 1
- return 1
- repeat n1 times
- var newFib := previousFib + currentFib
- previousFib := currentFib
- currentFib := newFib
- return currentFib
在上述伪代码中, 并没有存在重复求解问题, 只是在每次运行过程中, 保存上两项的值, 再利用公式 \(f(n)=f(n-1)+f(n-2)\)来求解第 n 项的值. 用 Python 实现上述过程, 代码如下:
- import time
- # bottom up approach of Dynamic Programming
- def dp_fib(n):
- previousFib = 0
- currentFib = 1
- if n <= 1:
- return n
- # repeat n-1 times
- for _ in range(n-1):
- newFib = previousFib + currentFib
- previousFib = currentFib
- currentFib = newFib
- return currentFib
- # time cost of DP method
- t1 = time.time()
- t = dp_fib(38)
- t2 = time.time()
- print('结果:%s, 运行时间:%s'%(t, t2-t1))
输出结果如下:
结果: 39088169, 运行时间: 0.0
显然, 使用动态规划法来求解斐波那契数列第 n 项的运行效率是很高的, 因为, 该算法的时间复杂度为多项式时间.
参考文献
算法导论(第四版)
- https://www.cs.upc.edu/~jordicf/Teaching/programming/pdf/IP07_Recursion.pdf
- https://www.saylor.org/site/wp-content/uploads/2011/06/Dynamic-Programming.pdf
附录
用递归法和动态规划法来求解该数列的第 n 项, 完整的 Python 代码如下:
- # calculate nth item of Fibonacci Sequence
- import time
- # recursive method
- def rec_fib(n):
- if n <= 1:
- return n
- else:
- return rec_fib(n-1) + rec_fib(n-2)
- # bottom up approach of Dynamic Programming
- def dp_fib(n):
- previousFib = 0
- currentFib = 1
- if n <= 1:
- return n
- # repeat n-1 times
- for _ in range(n-1):
- newFib = previousFib + currentFib
- previousFib = currentFib
- currentFib = newFib
- return currentFib
- # time cost of cursive method
- t1 = time.time()
- t = rec_fib(38)
- t2 = time.time()
- print('结果:%s, 运行时间:%s'%(t, t2-t1))
- # time cose of DP method
- s = dp_fib(38)
- t3 = time.time()
- print('结果:%s, 运行时间:%s'%(t, t3-t2))
输出结果如下:
结果: 39088169, 运行时间: 22.42628264427185
结果: 39088169, 运行时间: 0.0
注意: 本人现已开通两个微信公众号: 用 Python 做数学 (微信号为: python_math) 以及轻松学会 Python 爬虫(微信号为: easy_web_scrape), 欢迎大家关注哦~~
来源: https://www.cnblogs.com/jclian91/p/9132642.html