人工智能(6)Search(2)Dynamic Programming

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

总结一下之前讲过的这几种算法:

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

假设现在有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

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

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

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

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

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

n(N) = min

在第一种方案中,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)。来看一下代码的实现:

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

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

类似的拿少量存储去节省大量时间的例子还有很多,在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:

Problems Solving with Algorithms and Data Structures

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181117G0SAZ100?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券