算法探秘系列之动态规划（1）

概述

态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

动态规划一般可分为

线性动规
区域动规
树形动规
背包动规四类。
举例：

线性动规：拦截导弹(最大递减数列)，合唱队形，挖地雷，建学校，剑客决斗等；

区域动规：石子合并，加分二叉树，统计单词个数，炮兵布阵等；

树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；

背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等；

基本概念

动态规划过程

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

态规划经常常使用于解决最优化问题，这些问题多表现为多阶段决策。

关于多阶段决策：

在实际中，人们经常遇到这样一类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若干个联系的阶段。而在各阶段中。人们都须要作出方案的选择。我们称之为决策。

而且当一个阶段的决策之后，经常影响到下一个阶段的决策，从而影响整个过程的活动。这样，各个阶段所确定的决策就构成一个决策序列，常称之为策略。

因为各个阶段可供选择的决策往往不止一个。因而就可能有很多决策以供选择，这些可供选择的策略构成一个集合，我们称之为同意策略集合（简称策略集合）。每一个策略都对应地确定一种活动的效果。我们假定这个效果能够用数量来衡量。

因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择一个策略，使其在预定的标准下达到最好的效果。经常是人们所关心的问题。我们称这种策略为最优策略，这类问题就称为多阶段决策问题。

多阶段决策问题举例：机器负荷分配问题

某种机器能够在高低两种不同的负荷下进行生产。在高负荷下生产时。产品的年产量g和投入生产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下生产时，产品的年产量h和投入生产的机器数量y的关系为h=h(y)。对应的完善率为b(0<b<0)。且a<b。

假定開始生产时完善的机器熟练度为s1。要制定一个五年计划，确定每年投入高、低两种负荷生产的完善机器数量，使5年内产品的总产量达到最大。这是一个多阶段决策问题。

显然能够将全过程划分为5个阶段（一年一个阶段），每一个阶段開始时要确定投入高、低两种负荷下生产的完善机器数，并且上一个阶段的决策必定影响到下一个阶段的生产状态。决策的目标是使产品的总产量达到最大。这个问题常常使用数学方法建模，结合线性规划等知识来进行解决。

动态规划的适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理（最优子结构性质） ：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
无后效性：无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
子问题的重叠性：动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

求解的基本步骤

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
**确定状态和状态变量：**将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

实际应用中可以按以下几个简化的步骤进行设计：

(1) 分析最优解的性质，并刻画其结构特征。
(2) 递归的定义最优解。
(3) 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
(4) 根据计算优值时得到的信息，构造问题的最优解。

实战分析

1. 斐波那契数列

问题描述

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。
数列的前两项为 0 和 1 指的是这样一个数列：0、1、1、2、3、5 … 我们要求
(每一项为前两项的和)

递归写法（直观的解法）

# 一般写法
def fib_recursion(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib_recursion(n-1)+fib_recursion(n-2)

分析问题
因为通项公式为 f(n) = f(n-1) + f(n-2)

我们看适用条件
- 最优子结构性质：f(n) 问问题f(n-1) 为子问题，所以一个n 的问题可以拆解成两个子问题n-1 和n-2 当子问题得到最优，那么原问题的最优解也得出。
- 无后效性：即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
- 子问题的重叠性 我们根据一张图来看一下重复计算的问题
这张图详细讲解了利用递归思想的求解fib(5) 的过程,我们需要先知道fib(4) 和 fib(3)；而fib(4) 需要知道fib(3) 和fib(2)；fib(3) 则需要知道fib(2) 和 fib (1)；fib(3) 则需要…
我们可以看到 fib(3) fib(2) 被计算了多次，浪费了很多时间。

时间优化
我们一个中间结果，保存已经计算过的结果

# 中间结果的方式
def fib_mid_result(n):
    mid_ret = [0,1]
    # 初始化
    for i in range(0,n):
        mid_ret.append(None)
    def fib(n):
        if mid_ret[n] != None:
            return mid_ret[n]
        if n <= 0:
            return 0
        if n == 1:
            return 1
        mid_ret[n] = fib_recursion(n-1)+fib_recursion(n-2)
        return mid_ret[n]
    return fib(n)

空间优化
- 中间队列优化
  
  我们来看中间队列，由于我们的每一项是根据前两项得到的，换句话说，我们n 只依赖于前两项，这样依赖，我们的中间结果就不在需要那么多的空间来存贮。所以我们只需要两个数来，分别是 n-1 和n -2 就能得出结论。
- 字底向上：
  
  我们上面的实现方式都是自顶向下的实现方式，如果考虑自定向上的方式，我们就可以避免是用递归。
  例如，我们可以先算 f(0)和 f(1) 然后f(2) 就可以用 f(0) + f(1) 来得到结果在根据 f(1) + f(2)得到f(3)
  
  来看代码。
1
2
3
4
5
6
7
def fib_bottom_up(n):
pre = 0
next = 1
while n>0:
pre , next = next, pre + next
n-=1
return pre

2. 剪绳子

问题描述

把一根长度为 n 的绳子剪成 m 段，并且使得每段的长度的乘积最大（n, m 均为整数）
分析问题

假设我们剪一刀，使得一根长度为i，一个长度为 n-1,他们的乘积 i * n-1如果这个时候，乘积结果是最大的，则直接返回。

当时实际上往往将i这段绳子还能拆分，拆分的结果乘积 i 这个数本身还要大
所以我们的要解决的问题就变成了
求F(n) = max(F(i) * F(n - 1))，要使得 f(n) 最大那必须要让 f(i) 和 f(n-i)得到最大值

我们用列举:

n 分段序列最大乘积

1 1 1 不需要拆分

2 1,1 2 不需要拆分

3 1,2 3 不需要拆分

4 [1,3] [2,2] 4

5 [1,4] [2,3] 6

n	分段序列	最大乘积
1	1	1	不需要拆分
2	1,1	2	不需要拆分
3	1,2	3	不需要拆分
4	[1,3] [2,2]	4
5	[1,4] [2,3]	6

按着这个思路当n <= 3 的时候不用切,当n > 4的时候才需要切割

一般写法(递归写法)

def ecursive(n):
    ### 不用切割，返回的是自身长度
    if n <= 3:
        return n
    # 切割几次
    split_number = n//2
    max_ret = n;
    for i in range(1,split_number+1,1):
        max_ret = max(ecursive(i)*ecursive(n-i),max_ret)
    return max_ret

优化分析
这个优化分如同第一题的分析一样，只不过第一题的加法改成了乘法，本质上是一样的。
接下来我们来看加了中间结果的优化方法

动态优化写法：时间优化，保留计算结果

## 优化后的 递归算法 保留已经计算过的结果
result = {}
def ecursive2(l):
    if result.get(l) != None:
        return result[l]
    if l <= 3:
        return l
    split_number = l//2
    max_ret = l;
    for i in range(1,split_number+1,1):
        max_ret = max(ecursive2(i)*ecursive2(l-i),max_ret)
    result[l] = max_ret
    return max_ret

字底向上写法

假如入我们要计算
e(6)那么我们首先要计算 e(1) 和 e(5)

因为 1，2，3 比较特殊是不需要剪的所以我们从第4个开始
首先我们得到一个初始化数组里面的元素为 [0,1,2,3]
计算 e(4) 拆分得到 e(4) = e(1) * e(3) ... e(2) * e(2)，找出最大的赋值给第四个元素这个时候数组就变成了 [0,1,2,3,4] 这个数组的概念为 [e(1),e(2),e(3),e(4)]
这个时候计算e(5) 重复上述过程

def ecursive3(l):
    ret_mid = [0,1,2,3]
    if l <= 3:
        return ret_mid[l]
    for i in range(4,l + 1):
        max_mid_ret = i
        ret_mid.append(max_mid_ret)
        for n in range(1,i//2 + 1):
            max_mid_ret = max(ret_mid[n] * ret_mid[i - n],max_mid_ret)
        ret_mid[i] = max_mid_ret
    return ret_mid[l]

贪婪算法写法
当n大于等于5时，我们尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。为什么选2，3为最小的子问题？因为2，3包含于各个问题中，如果再往下剪得话，乘积就会变小。为什么选长度为3？因为当n≥5时，3(n−3)≥2(n−2)

其实为什么要选2和3,来看证明
证明： n<4的情况不必说，我们假设n>=5。这里的思想是把剪绳子划归为若干个子问题，每一剪就划分为两个子问题。当n>=5时，若剪为长度为a与n-a的两段更优，即a(n-a)>n，其中1<=a<n

推导如下：

令f(n)=(a-1)n-a^2 由于a-1>=0，f(n)单调递增。当n=5时，f(n)取得最小值为f(5)=(a-1)*5-a^2。要使最小值大于0，接下来求a的取值范围，令方程(a-1)*5-a^2=0，可用求根公式解得a为2,3（取整）。
换句话说当解中出现2，3 的时候总能让函数递增，也就是是剪出来的数大于本身长度。

来看实现

def greedy (l):
    if l <= 3:
        return n
    # 3出现的次数
    time_3  = l // 3 
    if l % 3 == 1:      #如果剩下4 则4分为 2 2
        time_3 -= 1
    time_2 = (l - time_3 * 3) // 2
    print(time_2,time_3)
    ret = math.pow(3,time_3)
    if time_2 != 0:
        ret + math.pow(2, time_2)
return ret

3. 背包问题

由于篇幅问题

4. 抢劫问题

5. 小兵向前冲

6. 最大递减数列

赏

支付宝打赏

微信打赏

赞赏一下

动态规划介绍

概述