python常⽤算法（7）——动态规划，回溯法
完整代码及其数据，请移步⼩编的GitHub
传送门：
如果点击有误：github/LeBron-Jian/BasicAlgorithmPractice
引⾔：从斐波那契数列看动态规划
斐波那契数列：Fn = F n-1 + F n-2 （ n = 1,2 fib(1) = fib(2) = 1）
练习：使⽤递归和⾮递归的⽅法来求解斐波那契数列的第 n 项
代码如下：
# _*_coding:utf-8_*_
def fibnacci(n):
if n == 1 or n == 2:
return 1
else:
return fibnacci(n - 1) + fibnacci(n - 2)
# 写这个是我们会发现计算f(5) 要算两边f(4)
# f(5) = f(4)+f(3)
# f(4) = f(3)+f(2)
# f(3) = f(2)+f(1)
# f(3) = f(2)+f(1)
# f(2) = 1
# 那么同理，算f(6)，我们会计算两次f(5)，三次f(4)....
# 当然不是说所有的递归都会重复计算，
# 时间随着数字越⼤，时间越长
print(fibnacci(10)) # 55
简单来说，就是想要计算f（5），我们需要先计算出⼦问题 f(4) 和 f(3)，然后要计算 f(4) ，我们需要先计算出⼦问题 f(3) 和 f(2)，以此类推，最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下⽣长了。
递归算法的时间复杂度怎么计算？⼦问题个数乘以解决⼀个⼦问题需要的时间。
⼦问题个数，即递归树中节点的总数。显然⼆叉树节点总数为指数级别，所以⼦问题个数为 O(2^n)。
解决⼀个⼦问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) ⼀个加法操作，时间为 O(1)。
所以，这个算法的时间复杂度为 O(2^n)，指数级别，爆炸。
观察递归树，很明显发现了算法低效的原因：存在⼤量重复计算，⽐如 f(5) 被计算了两次，⽽且你可以看到，以 f(5) 为根的这个递归树体量巨⼤，多算⼀遍，会耗费巨⼤的时间。更何况，还不⽌ f(5) 这⼀个节点被重复计算，所以这个算法及其低效。
这就是动态规划问题的第⼀个性质：重叠⼦问题。下⾯，我们想办法解决这个问题。
明确了问题，其实就已经把问题解决了⼀半。即然耗时的原因是重复计算，那么我们可以造⼀个「备忘录」，每次算出某个⼦问题的答案后别急着返回，先记到「备忘录」⾥再返回；每次遇到⼀个⼦问题先去「备忘录」⾥查⼀查，如果发现之前已经解决过这个问题了，直接把答案拿出来⽤，不要再耗时去计算了。
⼀般使⽤⼀个数组充当这个「备忘录」，当然你也可以使⽤哈希表（字典），思想都是⼀样的。
def fibnacci_n_recurision(n):
f = [0, 1, 1]
if n > 2:
for i in range(n - 2):
num = f[-1] + f[-2]
f.append(num)
return f[n]
print(fibnacci_n_recurision(10))
实际上，带「备忘录」的递归算法，把⼀棵存在巨量冗余的递归树通过「剪枝」，改造成了⼀幅不存在冗余的递归图，极⼤减少了⼦问题（即递归图中节点）的个数。
递归算法的时间复杂度怎么算？⼦问题个数乘以解决⼀个⼦问题需要的时间。
⼦问题个数，即图中节点的总数，由于本算法不存在冗余计算，⼦问题就是 f(1), f(2), f(3) ... f(20)，数量和输⼊规模 n = 20 成正⽐，所以
⼦问题个数为 O(n)。
解决⼀个⼦问题的时间，同上，没有什么循环，时间为 O(1)。
所以，本算法的时间复杂度是 O(n)。⽐起暴⼒算法，是降维打击。
⾄此，带备忘录的递归解法的效率已经和动态规划⼀样了。实际上，这种解法和动态规划的思想已经差不多了，只不过这种⽅法叫做「⾃顶向下」，动态规划叫做「⾃底向上」。
啥叫「⾃顶向下」？就是从上向下延伸，都是从⼀个规模较⼤的原问题⽐如说 f(5)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「⾃顶向下」。
啥叫「⾃底向上」？反过来，我们直接从最底下，最简单，问题规模最⼩的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(5)，这就是动态规划的思路，这也是为什么动态规划⼀般都脱离了递归，⽽是由循环迭代完成计算。
为了让我们的说服更有理⼀些，这⾥写了⼀个装饰器，我们通过运⾏时间看。同样对于上⾯两个函数，⼀个递归，⼀个⾮递归，我们输⼊ n=15
# cal_time.py 函数代码如下：
import time
def cal_time(func):
def wrapper(*args, **kwargs):
t1 = time.time()
字符串长度怎么数pythonresult = func(*arg, **kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__, t2 - t1))
return result
return wrapper
运⾏结果：
fibnacci running time: 0.01000070571899414 secs.
fibnacci_n_recurision running time: 0.0 secs.
总结来说，就是递归⾮常⾮常的慢，那⾮递归相对来说就⽐较快了。那为什么呢？就是为什么递归的效率低。我们上⾯代码也说过了，就是对⼦问题进⾏重复计算了。那第⼆个函数为什么快呢，我们将每次的计算结果存在了函数⾥，直接调⽤，避免了重复计算（当然不是说所有的递归都会重复计算⼦问题），第⼆个函数我们其实可以看做是动态规划的思想，从上⾯的代码来看：
动态规划的思想==递推式+重复⼦问题
怎么理解呢，就是说动态规划遵循⼀套固定的流程：递归的暴⼒解法 ——> 带备忘录的递归解法 ——
> ⾮递归的动态规划解法这个过程是层次递进的解决问题的过程，你如果没有前⾯的铺垫，直接看最终的⾮递归动态规划解法，当然觉得难。
1，什么是动态规划
动态规划(dynamic programming)是运筹学的⼀个分⽀，是求解决策过程(decision process)最优化的数学⽅法。把多阶段过程转化为⼀系列单阶段问题，利⽤各阶段之间的关系，逐个求解，创⽴了解决这类过程优化问题的新⽅法——动态规划。
1.1，使⽤动态规划特征
1. 求⼀个问题的最优解
2. ⼤问题可以分解为⼦问题，⼦问题还有重叠的更⼩的⼦问题
3. 整体问题最优解取决于⼦问题的最优解（状态转移⽅程）
4. 从上往下分析问题，从下往上解决问题
5. 讨论底层的边界问题
1.2，动态规划的基本思想
若要解⼀个给定问题，我们需要解其不同部分（即⼦问题），再合并⼦问题的解以得出原问题的解。通常许多⼦问题⾮常相似，为此动态规划法试图仅仅解决每个⼦问题⼀次，从⽽减少计算量：⼀旦某个给定⼦问题的解已经算出，则将其记忆化存储，以便下次需要同⼀个⼦问题解之时直接查表。这种做法在重复⼦问题的数⽬关于输⼊的规模呈指数增长时特别有效。
动态规划最重要的有三个概念：1、最优⼦结构 2、边界 3、状态转移⽅程
所以我们在学习动态规划要明⽩三件事情：
1，⽬标问题
2，状态的定义：opt[n]
3，状态转移⽅程：opt[n] = best_of(opt[n-1], opt[n-2])
其实状态转移⽅差直接代表着暴⼒解法，千万不要看不起暴⼒解，动态规划问题最难的就是写出状态转移⽅差，即这个暴⼒解。2，钢条切割问题
某公司出售钢条，出售价格与钢条长度直接的关系如下表：
问题：现在有⼀条长度为 n 的钢条和上⾯的价格表，求切割钢条⽅案，使得总收益最⼤。
分析：长度为4的钢条的所有切割⽅案如下：（C⽅案最优）
思考：长度为 n 的钢条的不同切割⽅案有⼏种？
下⾯是当长度为n的时候，最优价格的表格（ i 表⽰长度为 n ，r[i] 表⽰最优价格）
2.1，递推式解决钢条切割问题
设长度为 n 的钢条切割后最优收益值为 Rn，可以得到递推式：
第⼀个参数Pn 表⽰不切割
其他 n-1个参数分别表⽰另外 n-1种不同切割⽅案，对⽅案 i=1,2,...n-1 将钢条切割为长度为 i 和 n-i 两段
⽅案 i 的收益为切割两段的最优收益之和，考察所有的 i，选择其中收益最⼤的⽅案
2.2，最优⼦结构解决钢条切割问题
可以将求解规模为 n 的原问题，划分为规模更⼩的⼦问题：完成⼀次切割后，可以将产⽣的两段钢条看成两个独⽴的钢条切割问题。 组合两个⼦问题的最优解，并在所有可能的两段切割⽅案中选取组合收益最⼤的，构成原问题的最优解。
钢条切割满⾜最优⼦结构：问题的最优解由相关⼦问题的最优解组合⽽成，这些⼦问题可以独⽴求解。
钢条切割问题还存在更简单的递归求解⽅法：
从钢条的左边切割下长度为 i 的⼀段，只对右边剩下的⼀段继续进⾏切割，左边的不再切割
递推式简化为：
不做切割的⽅案就可以描述为：左边⼀段长度为 n，收益为 pn，剩下⼀段长度为0，收益为 r0=0.
2.3，钢条切割问题——⾃顶向下递归代码及其时间复杂度
代码如下：
def _cut_rod(p, n):
if n == 0:
return 0
q = 0
for i in range(1, n+1):
q = max(q, p[i] + _cut_rod(p, n-i))
return q
如下图所⽰，当钢条的长度增加时候，切割的⽅案次数随着指数增加。当n=1的时候切割1次，n=2的时候切割2次，n=3的时候切割4次，n=4的时候切割8次。。。。
所以：⾃顶向下递归实现的时间复杂度为 O(2n)
2.4，两种⽅法的代码实现
代码如下：
# _*_coding:utf-8_*_
import time
# 给递归函数⼀个装饰器，它就递归的装饰！！所以为了防⽌这样我们再套⼀层即可def cal_time(func):
def wrapper(*args, **kwargs):
t1 = time.time()
result = func(*args, **kwargs)
t2 = time.time()
print('%s running time : %s secs' % (func.__name__, t2 - t1))
return result
return wrapper
# p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 39, 40]
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
def cut_rod_recurision_1(p, n):
if n == 0:
return 0
else:
res = p[n]
for i in range(1, n):
res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i)) return res
# print(cut_rod_recurision_1(p, 9))
def cut_rod_recurision_2(p, n):
if n == 0:
return 0
else:
res = 0
for i in range(1, n + 1):
res = max(res, p[i] + cut_rod_recurision_2(p, n - i))
return res
# print(cut_rod_recurision_2(p, 9))
@cal_time
def c1(p, n):
return cut_rod_recurision_1(p, n)
@cal_time
def c2(p, n):
return cut_rod_recurision_2(p, n)
print(c1(p, 10))
print(c2(p, 10))
'''
c1 running time : 0.02000117301940918 secs
30
c2 running time : 0.0010001659393310547 secs
30
'''
我们通过计算时间，发现第⼆个递归⽅法明显⽐第⼀个递归⽅法快很多。那么是否还有更简单的⽅法呢？肯定有，下⾯学习动态规划。
2.5，动态规划解决钢条切割问题
递归算法由于重复求解相同⼦问题，效率极低。即使优化过后的递归也效率不⾼。那这⾥使⽤动态规划。
动态规划的思想：
1. 每个⼦问题只求解⼀次，保存求解结果
2. 之后需要此问题时，只需要查保存的结果
动态规划解法代码：
def cut_rod_dp(p, n):
r = [0 for _ in range(n+1)]
for j in range(1, n+1):
q = 0
for i in range(1, j+1):
q = max(q, p[i]+r[j-i])
r[j] = q
return r[n]
或者便于理解这样：
def cut_rod_dp(p, n):
r = [0]
for i in range(1, n+1):
res = 0
for j in range(1, i+1):
res = max(res, p[j]+r[i-j])
r.append(res)
return r[n]
时间复杂度： O(n2)
2.6，钢条切割问题——重构解
如何修改动态规划算法，使其不仅输出最优解，还输出最优切割⽅案？
对于每个⼦问题，保存切割⼀次时左边切下的长度
下图为r[i] 表⽰最优切割的价格，s[i]表⽰切割左边的长度。
代码如下：
def cut_rod_extend(p, n):
r = [0]
s = [0]
# 这个循环的意思是从底向上计算
for i in range(1, n+1):
res_r = 0 # ⽤来记录价格的最优值
res_s = 0 # ⽤来记录切割左边的最优长度
for j in range(1, i+1):
if p[j] + r[i-j] > res_r:
res_r = p[j] + r[i-j]
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论