Lecture 13: Dynamic programming: overlapping subproblems, optimal substrcture
本课重点讲述了动态规划,介绍了其核心思想,即默记法。本课前半部分用斐波纳契数的例子详细介绍默记法的使用方法。后半部分介绍了决策树和用它解决0/1背包问题的两个程序样例。
动态规划(Dynamic programming),根据百度百科所述,是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。在20世纪50年代初,美国数学家R.E.Bellman(贝尔曼)等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。
动态规划最关键的地方在于,存在一种子问题和最理想子结构重叠的情况。这个说法非常抽象,但简单来说就是如果子问题的最优解被重复使用的话,我们就可以使用动态规划。下面就举一个例子来详细解释:
在Lecture 4的时候,有一个例子斐波那契数Fibonacci numbers,当时有如下程序:
def Fib(n):
if n == 1 or n == 0:
return 1
else:
return Fib(n - 1) + Fib(n - 2)
那么,如果要计算Fib(5)的结果,我们会用到Fib(4)和Fib(3)的结果,而Fib(4)又用到了Fib(3)和Fib(2)的结果,依此类推。我们会发现,Fib(3),Fib(2)的结果被多次调用,而我们又需要花时间去计算Fib(3)和Fib(2),那么这就造成了累赘计算。
相信到这里,大家都会这样觉得,为什么不把这些结果存下来,这样以后用到的时候就可以直接使用了呢?没错,这就是我们所说的默记法。
默记法(Memorization)是动态规划的核心内容。具体方法如下:
这个概念非常简单,容易理解。那么对于上面的斐波那契的例子,我们就可以运用默记法,标程如下:
def FastFib(n, memo):
if not n in memo:
memo[n] = FastFib(n - 1, memo) + FastFib(n - 2, memo)
return memo[n]
def FastFibonacci(n):
memo = {0:1, 1:1} # initialize the memo
return FastFib(n, memo)
本课的后半部分则讲了0/1背包问题的两个解法,下面例1是普通解法,只是用了简单的决策树,而例2则用了动态规划,优化了例1。两个例子如下:
例1:普通解法
def maxVal(w, v, i, aW):
if i == 0:
if w[i] <= aW:
return v[i]
else:
return 0
without_i = maxVal(w, v, i-1, aW)
if w[i] > aW:
return without_i
else:
with_i = v[i] + maxVal(w, v, i-1, aW - w[i])
return max(with_i, without_i)
例2:动态规划
def fastMaxVal(w, v, i, aW, m):
try:
return m[(i, aW)] # to check whether the thing is in the memo or not
except KeyError:
if i == 0:
if w[i] <= aW:
m[(i, aW)] = v[i]
return v[i]
else:
m[(i, aW)] = 0
return 0
without_i = fastMaxVal(w, v, i-1, aW, m)
if w[i] > aW:
m[(i, aW)] = without_i
return without_i
else:
with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m)
res = max(with_i, without_i)
m[(i, aW)] = res
return res
def MaxVal0(w, v, i, aW):
m = {}
return fastMaxVal(w, v, i, aW, m)
这个程序的算法复杂度为O(ns),n为可选择物品的总数量,s为背包可以装的物品数量。这个算法不仅需要O(ns)的时间,也需要O(ns)的空间。可以说,这也是一个用空间换时间的算法。
那么我们再来从复杂度的方面考虑动态规划。根据百度资料,能用动态规划解决的问题,肯定能用搜索解决。但是搜素时间复杂度太高了,怎么优化呢?我们就想到了记忆化搜索,也就是默记法,就是搜完某个解之后把它保存起来,下一次搜到这个地方的时候,调用上一次的搜索出来的结果。这样就解决了处理重复状态的问题。
动态规划之所以速度快是因为解决了重复处理某个状态的问题。记忆化搜索是动态规划的一种实现方法。
搜索到i状态,首先确定要解决i首先要解决什么状态。那么那些状态必然可以转移给i状态。于是我们就确定了状态转移方程。然后我们需要确定边界条件。将边界条件赋予初值。此时就可以从前往后枚举状态进行状态转移拉。
(以上三段均来自于百度:http://zhidao.baidu.com/question/407709820.html)
总结:详细介绍了动态规划和其核心内容默记法,非常有用,初学者必看!