计算机科学及编程导论(麻省理工)

计算机科学及编程导论(麻省理工)

5 (18人评价)
  • 课时:(24)

  • 学员:(658)

  • 浏览:(26141)

  • 加入课程

动态规划,重叠的子问题,最优子结构的笔记

相关课时: 笔记详情:

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)

 

总结:详细介绍了动态规划和其核心内容默记法,非常有用,初学者必看!

2 2

你感兴趣的课程

2万+浏览/ 931学员/ 4.7评分
¥9.90
理论基础 数学之美
2万+浏览/ 706学员/ 4.4评分
免费
2万+浏览/ 826学员/ 4.8评分
免费