动态规划(dynamic programming)这个名词曾不止一次吓到我,而事实上,动态规划作为一种思想而非算法,其最大的作用是优化。这次笔记中,我就对最为经典的The Triangle[1]问题来对DP的记忆化搜索进行解释。
如图1,从三角形的最上面的顶点往下层走(每次只能向左或向右一个),那么如何走,才能途径的所有位置的点数之和最大呢?

图1

第一种自然而然的思路就是把所有可能的路径都找到,并找到其中点数和最大的一条路径作为答案,然而这样的思路却存在着很大的效率问题,从第一个顶点开始往下走,每走一步都有2种选择,那么走到第N层的时候,路径数目就多达2^N条,枚举如此巨大数目的路径,必然会使程序在测试的过程中出现超时(TLE),所以这样的方法并不可取。
至此,我们可以隆重推出动态规划的思想了,我们从结果来看,答案的路径是确认的,那么第一步只有向左或向右才可能到达最终答案的地点,第二步也是,第三步也是……在这个过程中,我们往下走,只选择“能到达最优解”的路径走,这样就可以帮助我们减少大量的搜索,而只需要考虑“走在什么位置是可能到最优解”这个问题就好,那么我们首先把问题中的三角形上各个位置用坐标表示出来:

图2

按照刚才所说的思路,我们把每一次决策用图3来表示:

图3

当前位置是(i, j),需要选择一条向下的路径,黑色圈代表当前位置的点数,绿色的圈代表了了选择这条路径后,最终所能到达的最大点数和,什么意思呢?换句话就是,当作出选择后,我们就能知道,走这条路最多能得到的点数,如果选左路最多能得到的点数不如选右路最终得到的点数多,那么必然右路是最佳路径,我们用状态转移方程来描述这样的决策过程:

f(i, j) = a(i, j) + max{f(i+1, j), f(i+1, j+1)}

请先理解这个方程和图3以及文字描述的关系,这是个递推公式,要便于理解,应该从问题中的图从下层往上看,通过层层的计算,来得到最优的路径,通过计算最佳的子问题的解,来最终得到整体问题的解答。
得到递推公式,就为编写程序提供了巨大的便利,因为我们可以直接通过递归函数来描述这个求解过程:

但这个代码真的可以直接用作答案么?答案是否定的。
这个代码存在两个问题,一个是没有进行边界处理(到达底层后不能继续再递归);
第二则是,对于效率,并没有比全面搜索有所改进。
为什么?因为为了找到最优子问题,我们递归函数调用的数量是巨大的!见图4:

图4

看到了么?递归运算的次数仍高达2^N-1,其中你要特别关照用绿色填实的圆圈,这部分圆圈中的数值,在之前的递归运算中已经计算过了一次了,这提示我们,直接用递归表达,会产生“重复运算子问题”的问题,如果我们可以在运算中避免重复计算子问题,那么我们的优化就明朗化了,我们只需要递归n(n+1)/2次就可以找到最优解,从O(2^n)到O(n^2),从指数复杂度到多项式复杂度,这就是动态规划的强大所在。
为了解决效率低下的问题,我们再次隆重推出“记忆化搜索”的方法,也就是,用一个数组,记录每次递归运算后得到的值,当程序试图计算重复子问题的时候,会先看看之前是否已经计算过了,如果计算过了,那么不必再算,只需要把之前计算过的结果给出即可,我用数组d[i][j]来保存每次递归的结果,这个数组的初值用memset函数设定为-1,也就是我用-1这个值来表示我没有计算过这个位置的递归值,那么改进的递归函数如下:

在记忆化搜索当中,我们需要用一个数组来存储每次递归的值,相当于以空间换取时间,但面对如此诱人的时间优化的时候,还是怎么想怎么值:)。

[1] POJ 1163 The Triangle

说点什么

1 评论 在 "DP记忆化搜索"

  Subscribe  
最新 最旧 得票最多
提醒