人工智能（6）Dynamic Programming

上次提到了，回溯(Backtrack)，深度和广度搜索，一些演化的算法，比如规定了最大深度的深度搜索，或者叫做DFS with iterative deepening （DFS-ID），每一个的action都有一个固定的cost，假设最优方案的深度为d的话，空间和时间的复杂度：O（d）和O（b^d)。

总结一下之前讲过的这几种算法, 不难看出时间复杂度都是指数级别的

那么有没有一些方式能把时间复杂度降低一些呢？我们先来看一下动态规划。

上次提到了，对于一个搜索的问题，包含几个要素：

当前的状态S, 到达下一个状态的动作a,这一动作的代价c, 下一个状态（Succ (s,a), successor of S），最终的状态。

动态规划实际上就是这样的一个过程：

在当前状态S下，判断出来达到下一个状态S‘的动作的代价，然后通过某种方式计算一下这个状态到达最终状态的代价。要做的就是找出来代价和最小的下一个状态。

用这样的一个例子一起来看一下动态规划的一个过程：

假设现在有1，2，5，10块四种面值的纸币，现在问一下凑齐68块钱最少需要多少张纸币？

直觉地：先用10块的6张，凑不够10块的，用5块的一张，再用2块的和1块的各一张，刚好68块，毫无疑问这样的方法是正确的，这其实用到了贪心的思想（Greedy Method）。

试想一下，如果现在的钱币面值设置不是这样的，而是1，5，8，10 块的面值，要凑64块钱，贪心的方法会选6张10块，再选4张一块，但这不是用的最少的，8张8块的是最少的。遇到这样的一类问题，方案就是动态规划的方法。

假设现在要兑换N块的纸币，那么最优的方案需要的张数n是关于N的一个这样的递归函数：

n(N) = min {1+n(N-1)；1+n(N-5); 1+n(N-8); 1+n(N-10)}

很明显有几个隐含的条件：如果N = 1,5,8,10, n(N) = 1, 一张就够了。选择的纸币的面值肯定不能超过要凑的纸币总数，比如要凑6块钱，8和10块肯定用不到了。代码实现也很容易：

# i_STEM,Dynamic programming

# 用1，5，8，10 块的纸币凑N块的问题

# 递归

import numpy as np

value = [1,5,8,10]

N = 40

def exchange(value,N, count = [0]):

    count[0]+= 1

    mn = N

    if N in value:

        print ("Recursion times:",count[0])

        return 1

    for i in [int(v) for v in value if int (v) <=N]:

        n = 1 + exchange(value,N-i,mem)

        if n < mn:

            mn = n

    return mn

exchange(value,N) #

但上面这段短短的代码，却要花很多时间去递归，举个例子，要算一下凑40块，要调用20多万次递归，，普通电脑可能花一分钟左右才跑完。。那么问题出现在哪儿呢？不难想象，很多重复的数据出现，重新进行计算，浪费了大量的时间。比如，凑68块，可能会用到前67块各自的需要的最少的数量的纸币，才能得出最后的最优的结果。如果把这些结果保存下来，就省去了重复计算的时间，这其实也是“学习”的一个过程，或者说“记忆”。很简单的，加几行代码就可以了。首先，声明存储的变量，函数调用的时候作为参数。接着，递归出口多了一个，除了面值等于1，5，8，10的之外，其他存储过的最少的纸币的张数也保存起来，到时候直接调用。这样显示，递归了80多次，调用了70多次，不到1秒钟就跑完程序。

# i_STEM,递归动态规划

import numpy as np

value = [1,5,8,10]

N = 40

mem = np.zeros([N+1]) # 存储所有N-1块的需要的纸币的最少的张数

def exchange(value,N, mem,count = [0,0]):

    count[0]+= 1

    mn = N

    if N in value:

        print ("Recursion times:",count[0])

        return 1

    elif mem[N] > 0:

        count[1]+= 1

        print ("Retrieval times:",count[1])

        return mem[N]

    for i in [int(v) for v in value if int (v) <=N]:

        n = 1 + exchange(value,N-i,mem)

        if n < mn:

            mn = n

            mem[N] = mn

    return mn

exchange(value,N, mem) #

print (mem)

那么有一个问题，程序跑完之后，所有1-39块的最少的张数都会保存起来吗？

答案是不一定，因为在求40块的张数的时候，是一个自顶向下的过程，并且，40块不一定需要的张数比20多，30多块的需要的多，自顶向下分解的时候，不一定会分解到每一个值。那么问题来了，能不能找到一种方法，把1-39块的每一种方案都找出来？

答案是肯定的，自底向上的过程可以确保顶层的问题肯定能从下面找到解答。同样的公式：

n(N) = min {1+n(N-1)；1+n(N-5); 1+n(N-8); 1+n(N-10)}

在第一种方案中，n（N）代表递归的解决方案，这里n（N）表示的是存储的最优方案的值，也即不是去递归调用，而是直接从存储里面去取值，也就是说我们不需要使用递归就可以计算出来，无非是在原有的基础上试探所有四种纸币的可行性和解决方案是否最优。在程序实现的时候，每个n(N)的初始值都是N,也即，最坏的方案是都用1块去凑，然后每求一个n（N），依据N的大小，考虑这四种纸币拼凑的情况，在n(N-1), n(N-5), n(N-8), n(N-10)的基础上加1取值即可。这样的话时间复杂度是O（4*N），空间复杂度O（N）。来看一下代码的实现：

# i_STEM,自底向上动态规划

import numpy as np

value = [1,5,8,10]

N = 40

# 存储最优的方案，N+1个0的list,这样保证下标是0-40，41个数，虽然0下标的位置用不到,

# cost = [0]*(N + 1)

cost = np.zeros([N+1])

def exchange(value, N, cost):

    # N重循环

    for i in range(1,N+1):

        # 初始化为最差的方案，全部用1块

        cost[i] = i

        # 最多四重循环

        for j in [k for k in value if k <= i]:

            # 读取i-j块需要的张数，再加一张即可，j一定是不大于i，需要注意的是cost[0]=0保持不变

            cost_temp = cost[i-j] + 1

            if cost_temp <= cost[i]:

                cost[i] = cost_temp

    return cost

exchange(value, N, cost)

如果要想存储解决的方案，也即哪些纸币被用来去凑N块，声明另外一个变量，cost，求N块的方案，存储最后一个纸币的数额m，也即coin[N]=m，再找出N-m的最后一张纸币的数额，这样就可以把整个方案的找出来。来看一下代码实现：

# i_STEM,自底向上动态规划，存储方案

import numpy as np

value = [1,5,8,10]

N = 40

# 存储最优的方案，N+1个0的list,这样保证下标是0-40，41个数，虽然0下标的位置用不到,

# cost = [0]*(N + 1)

cost = np.zeros([N+1])

# 求N块的方案，存储最后一个纸币的数额m，也即coin[N]=m，再找出N-m的最后一张纸币的数额，这样就可以把整个方案的找出来，

coin = np.zeros([N+1])

def exchange(value, N, cost):

    # N重循环

    for i in range(1,N+1):

        # 初始化为最差的方案，全部用1块

        cost[i] = i

        # 最多四重循环

        for j in [k for k in value if k <= i]:

            # 读取i-j块需要的张数，再加一张即可，j一定是不大于i，需要注意的是cost[0]=0保持不变

            cost_temp = cost[i-j] + 1

            if cost_temp <= cost[i]:

                cost[i] = cost_temp

                coin[i] = j

    return cost,coin

exchange(value, N, cost)

简单的总结，上面的前三种方案中，第一种单纯使用递归，而不使用存储的话，花费大量的时间；第二种方案，使用了一些存储，同时也有递归调用，节约了大量的时间；第三种方案，最大限度的使用存储，没有使用递归，自底向上的解决了问题，也节省了很多的时间。适当的使用存储，来节约大量的时间成本，还是很合算的。

类似的拿少量存储去节省大量时间的例子还有很多，在python中，递归调用的层数不能超过1000层，再考虑到时间成本，所以大量的运算的时候，合适的使用存储很有必要。除此之外，动态规划在很多领域中都可以见到，比如在生物信息学中，做DNA序列的alignment的时候，动态规划是非常常见的例子，比如Needleman–Wunsch 算法

再回到搜索中来，搜索中的动态规划的几个要素上面提到了，当前状态S，动作a，动作的代价Cost(S,a)和下一个状态Succ(s,a)，以及终止状态的判断。与上面所说的不太一样的地方是，上面的问题每一个动作的代价是一样的，增加一张纸币，只是这张纸币选择的上一个状态不尽相同，导致整个方案的代价也不同，取其中最优的。

在搜索中，

FutureCost (S) = 0， 如果是终止状态；

FutureCost (S) = min [Cost(S,a) + FutureCost (Succ(s,a))], 不是终止状态。

好，动态规划是非常重要的一种思想，我们从时间和存储成本的角度简单的分析了一下这样的应用，在不同的行业领域，都会不同的实际应用的方案，但抽象化的中心思想是一致的。后面遇到更经典的动态规划案例，再补充分享。下次来看一下搜索中 uniform cost search的实现。

Reference:

Problem Solving with Algorithms and Data Structures