学习面对实际问题如何设计算法与分析算法。
039动态规划算法的迭代实现
Loading...
来自 Peking University 的课程
算法设计与分析 Design and Analysis of Algorithms
31 个评分
从本节课中
动态规划算法
动态规划是另一种常用的算法设计技术。首先通过矩阵相乘的例子介绍动态规划算法的设计思想、主要步骤、分析方法、迭代实现与存储表示等。然后通过投资、背包、最长公共子序列等典型问题展现不同的动态规划算法在子问题划分与迭代计算时的特点和提高算法效率的技巧。
与讲师见面
Wanling QuProfessor
School of EECS, Peking University
刚才讲到了动态规划算法的递归实现。
动态规划算法递归实现的时候呢，由于同一个子问题
被多次地计算，所以它的时间复杂度呢比较高。
我们想的办法呢就是每个子问题只算一次，只算一次呢
后边用到的时候我们把那个值直接拿过来，这样就可以把时间降下来，
这个就是它的迭代实现。下面我们看一下 在迭代实现的时候，有一些关键问题需要来考虑。
第一个是每个子问题只算一次，
那你就需要注意这个迭代的过程，一定要从最小的子问题算起，
要把它的计算顺序明确下来，这样才能保证后边用到的值
前面已经算好了，存在那了。所以这个迭代的顺序是一个非常重要的，这个是迭代的起始，
下面是它的顺序。还需要考虑的就是用什么样的存储结构
来保留它的计算结果，中间每一步的子问题的计算结果
都留下来，这个就是它的备忘录，要考虑这个存储结构。
还要考虑它的解的追踪，当你这个
最后的优化函数算出来了以后，问题的解是什么？
那是另外一件事情。我们优化函数，比如说矩阵链问题，它只是你的
这个运算次数，这个次数达到最小了，但是你到底括弧加在哪里？ 这个是问题的解，所以我们要通过这个
标记函数来标记每一步决策的位置，也就是加括弧运算的位置，这样才能找到它的解。因此
这个追踪解到底怎么个追踪，也需要把这个算法 想清楚。这是它的几个关键问题。
下面我们看一下矩阵链乘法的不同的这个子问题，到底我们
怎么来设计这个子问题的计算顺序，来保证这个迭代
后面用到的值前面已经算过了。那么长度，只含有1个矩阵，
这样的子问题，就是最小的子问题它有n个 子问题，这个不需要计算，因为它没有乘法。
长度是2，是2个矩阵的子问题，这有n-1个子问题。
长度是3的这样的矩阵有n-2个子问题，
一直到长度是n-1的，有两个子问题。长度是 n的，就是原始问题，只有一个，这是它的不同的子问题
有这么多个，根据它的规模我们把它列出来了。下边看一下迭代计算的顺序，
迭代计算的顺序呢，长度是1的，我们作为初值，都是0， 这个i
可以从1到n，就是m[1,1]到m[n,n]，
这是n个子问题。长度是2的是1到2的一个链，2到3的
链，一直到n-1到n的链，只有n-1个子问题。
长度是3的，1到3的，2到4的，一直到n-2到n的， 我们按照这样的顺序
从前到后每一行，每一行从左到右这样来计算。一直到长度是n-1
有两个子问题，先算第一个，再算第二个。最后这就是长度是n的，是原始问题。
这个是它的迭代计算的顺序，我们就按照这样的顺序来计算。
那么当你计算到后面的时候，可能会调用前面的子问题，
它的值直接拿过来就可以了。我们看看
具体的例子，这是n到8的这样的子问题，也就是说
一共是8个矩阵， 8个矩阵从A1到A8，
初值我们不考虑了。长度是2的， A1，A2，A2，A3到最后A7，A8，
这是它的子问题列出来了。长度是3的，一共是
6个子问题，列在这，这是它的计算顺序，从左到右。长度是4的， 长度是5的，是6的，是7的，最后是原始问题，
因为正好等于n了。这个是 子问题的计算顺序，我们就按照这样的顺序来做。下边看一下
矩阵链相乘算法的伪码，这个是迭代实现。
首先我们先赋初值，令所有的m[i,i]的 初值都为0，这就是长度是1的矩阵链。
然后我们对所有的链长进行迭代计算，
链长的最少的值是2，最长的值到n，
那么对于每一个给定的链长，我们在选择它的首边界
和后边界，所以这个地方是遍历所有长度是r的子问题，
那么从这个里头，它的计算就是具体对一个子问题的
计算，这一个子问题的计算呢一开始这几个步是矩阵链前边的
子问题指长度是1，只有1个矩阵，后边从i+1到j是后边
看作一个子问题，这样来做计算，这是第一步计算的结果。
然后这个分隔的位置k就开始移动，刚才那个分隔的位置
是划在i的后面，下面就从i+1到j-1， 陆续遍历所有可能的分隔的位置。
在这个分隔位置下，这是前一个矩阵的它的最少的乘法次数，
这是后边这个结果矩阵的最少的乘法次数，然后把这两个子问题的结果综合起来
需要做这么多的乘法次数，这就计算出来了在这个分隔位置下的
它的最少的次数，如果这个值比原来保存的值更小，这个时候
我们就要来做替换，所以遍历了所有的划分以后，就可以
通过这样的替换保留了最好的结果，就把这个解更新了。
这是我们看到的它的矩阵链相乘的
伪码。那么这里边有两个备忘录，s和m两个是备忘录，
m记录的是最少在乘法次数所有子问题的最少的乘法次数，
s呢是记录这个分界的位置，就是通过这样的 赋值来把这个分界位置记下来，这是它的伪码。
下面我们看一下时间复杂度。
时间复杂度的分析呢根据这个伪码，第二行是遍历所有可能的
链的长度，从2一直到n，所以这个是O(n)量级。第3行
它是确定子问题的首位置，这个首位置也有O(n)种选择的可能。那么当首位置定了以后，
链长定了，它的末位置也就定了，相当于把子问题定了。那么第7行呢，是对针对这个子问题
它要分隔成更小的子问题，这个k要移动，要进行切分，
那这个切分的量级也是O(n)，所以这三行的
它的循环都是O(n)的操作，那按照这个O(n)的
这样的一个操作有三个变量，那是n³种可能的子
内部操作，而内部操作呢是常数时间，所以它总的工作量是
O(n³)。那么另外一种估计工作量的方法就
根据备忘录来估计，因为备忘录里头每一项的工作量
一共对它的工作量再求和就可以了。而子问题一共
有多少个呢？就意味着这个备忘录有多少个项，一共有n²个
子问题，相当于它的每个矩阵链的前后边界 所有可能的组合，然后在每个子问题内部的工作量它
需要做划分，把它划分成更小的子问题，而这个 划分的次数大概是O(n)次。所以整个的
每一个子问题的工作量是O(n)，一共有n²个子问题， 也就是说它的备忘录有n²个项，
它的工作总时间是O(n³)，这个是关于它的这个时间的复杂度的估计。
那么追踪解的工作量是O(n)，把这两个工作量加到一起
当然它的总工作量还是O(n³)，这就是算法分析的结果。
看一个具体的例子，这是一个矩阵链，
这个矩阵链呢它的行列的参数给在这个p里面，这个是它的
矩阵个数，5个矩阵。那么对于它来讲，
它是这5个矩阵的行列号都可以由这个参数把它列出来，
它的备忘录刚好是所有子问题的
最小的乘法次数，还有划分位置来存储，这是备忘录的设计。
下边我们看一下一个具体的这个结果，就是刚才那个矩阵链。
在这儿，r=1是初值， 这个都赋成零。然后，我们
对链长是2的做计算，链长是2的， [1,2]一个子问题，[2,3]、[3,4]、[4,5]，
这是顺序计算，把这几个值算出来记在这个备忘录里面
然后，这是链长是3的，有3个子问题，这个是它的计算结果
这个是链长是4的两个子问题的计算结果，这是最后原始问题的最终结果
那么在这个计算中呢，我们看一个具体的步骤，比如说m[2,5]这个计算是怎么得到的。
m[2,5]的计算呢，它可能是这样的划分位置，就是第二个矩阵作为一个
子问题，[3,5]矩阵做一个子问题。那么这个值是0，这个值是2500
把它们俩合并的工作量应该是35,15和20。
好，应该这三个乘起来，也就是说这一项。
那这个0在这，这个2500在这项，加上合并的工作量
这是这一种划分的时候，它的最少的次数，那这个运算次数呢，我们可以观察到
它已经超过一万了。下边我们看到还有另外的划分位置，
那就是说，{2,3]作为前一个子问题，
[4,5]作为第二个子问题。那么，这个第一个子问题的工作量2625，第二个工作量
1000，反应在这两项里头。然后，把这两个子问题合并，它是35,5,20，
这样的参数，所以就是合并的工作量在这一项里头，那这个算出来的结果呢是7125。- 啊，这是
第二个结果，比第一个结果要好。那还有 第三个划分的位置，就是[2,4]是一个子问题，
第五个矩阵自己是一个子问题，那这个结果是4375，
然后这个结果是0，这是初值，加上它们合并的工作量 35x10,
35,10,20，这个结果算出来也超过一万了。
所以，三个值最小的结果是这个7125，这就是
它的具体的计算过程。那么，我们在计算[2,5]的这个项的时候调用了前边的
刚才讲到的若干个值，啊，把它直接拿过来就可以了，这个就是备忘录。
然后我们看一下标记函数。标记函数呢，
它也是标记我们得到那个最优值的时候它的划分位置，那根据这个标记函数来
追踪最后的解，也就是加括弧加在哪里。我们由这个项来追踪，s[1,5]=3，
说明最后一次计算是在第三个矩阵后面作为划分位置计算的。
因此，我们就可以知道整个的计算最后一次是划在这个位置。
前三个矩阵的计算结果，后两个矩阵计算结果，然后把这两个作为最后的结果乘起来。
这是找到了这个位置，然后由它，我们还要追踪前面这个子问题，它究竟
乘法是按照什么顺序计算的，那就要查s[1,3]，
s[1,3]呢是1，s[1,3]是1就说明
我们划分的位置在第一个矩阵后面，也就是说它是这样计算的
A2、A3算了，然后A1再和它来算，啊，这是它的计算。
那么把这个合到一起呢，我们就得到整个的计算顺序，A2、A3先算，A1再和它算。
把这个结果再和A4、A5的结果再算，就是这个最终的计算顺序，而它的
运算次数就是11875，就是刚才那个备忘录存的那个最少的乘法次数。
两种实现可以比较一下，
递归的实现复杂度高，空间比较小；迭代实现呢，时间复杂度
降低了，但是空间消耗加多了。原因呢，是因为递归实现
它是子问题多次重复计算，而子问题的计算次数有可能是指数量级的增长，而迭代计算呢，
每个子问题只算一次，所以这是它时间复杂度低的原因。
动态规划算法的时间复杂度
应该怎么估计呢，有两种办法。一个是通过备忘录各项来计算
它的工作量的总和，每一项工作量都加起来， 然后再和追踪解的工作量算，加到一起就可以了。
啊，可以通过这个办法来算，也可以通过递推方程来算。
啊，这两种办法都可以。一般来讲，这个追踪解的工作量比前边记录的
工作量一般地来讲要小，啊，所以常常很多问题的复杂度函数基本上就和
备忘录计算的工作量是一样的，这是它的递交。
最后，我们把这个算法的要素小结一下。划分子问题确定边界，
转换成多步判断的过程。定义优化函数，
以该函数的极大或极小来做依据，确定是不是满足优化原则。
列出优化函数的递推方程和边界条件。
自底向上的计算，也就是从最小的子问题算起，给定这个计算顺序。
然后设计这个备忘录，就是这个表格是什么样子来存储这个子问题的优化函数值和标记。
这个标记呢，有的问题需要设立，有的问题可能不需要设立，
所以要先想好要不要设立标记函数，标记函数的计算满足什么样的公式。
最后，它的复杂度估计可以用递推方程的方法
或者备忘录的方法来估计它的复杂度函数。
