刚才讲到了动态规划算法的递归实现。 动态规划算法递归实现的时候呢,由于同一个子问题 被多次地计算,所以它的时间复杂度呢比较高。 我们想的办法呢就是每个子问题只算一次,只算一次呢 后边用到的时候我们把那个值直接拿过来,这样就可以把时间降下来, 这个就是它的迭代实现。下面我们看一下 在迭代实现的时候,有一些关键问题需要来考虑。 第一个是每个子问题只算一次, 那你就需要注意这个迭代的过程,一定要从最小的子问题算起, 要把它的计算顺序明确下来,这样才能保证后边用到的值 前面已经算好了,存在那了。所以这个迭代的顺序是一个非常重要的,这个是迭代的起始, 下面是它的顺序。还需要考虑的就是用什么样的存储结构 来保留它的计算结果,中间每一步的子问题的计算结果 都留下来,这个就是它的备忘录,要考虑这个存储结构。 还要考虑它的解的追踪,当你这个 最后的优化函数算出来了以后,问题的解是什么? 那是另外一件事情。我们优化函数,比如说矩阵链问题,它只是你的 这个运算次数,这个次数达到最小了,但是你到底括弧加在哪里? 这个是问题的解,所以我们要通过这个 标记函数来标记每一步决策的位置,也就是加括弧运算的位置,这样才能找到它的解。因此 这个追踪解到底怎么个追踪,也需要把这个算法 想清楚。这是它的几个关键问题。 下面我们看一下矩阵链乘法的不同的这个子问题,到底我们 怎么来设计这个子问题的计算顺序,来保证这个迭代 后面用到的值前面已经算过了。那么长度,只含有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,就是刚才那个备忘录存的那个最少的乘法次数。 两种实现可以比较一下, 递归的实现复杂度高,空间比较小;迭代实现呢,时间复杂度 降低了,但是空间消耗加多了。原因呢,是因为递归实现 它是子问题多次重复计算,而子问题的计算次数有可能是指数量级的增长,而迭代计算呢, 每个子问题只算一次,所以这是它时间复杂度低的原因。 动态规划算法的时间复杂度 应该怎么估计呢,有两种办法。一个是通过备忘录各项来计算 它的工作量的总和,每一项工作量都加起来, 然后再和追踪解的工作量算,加到一起就可以了。 啊,可以通过这个办法来算,也可以通过递推方程来算。 啊,这两种办法都可以。一般来讲,这个追踪解的工作量比前边记录的 工作量一般地来讲要小,啊,所以常常很多问题的复杂度函数基本上就和 备忘录计算的工作量是一样的,这是它的递交。 最后,我们把这个算法的要素小结一下。划分子问题确定边界, 转换成多步判断的过程。定义优化函数, 以该函数的极大或极小来做依据,确定是不是满足优化原则。 列出优化函数的递推方程和边界条件。 自底向上的计算,也就是从最小的子问题算起,给定这个计算顺序。 然后设计这个备忘录,就是这个表格是什么样子来存储这个子问题的优化函数值和标记。 这个标记呢,有的问题需要设立,有的问题可能不需要设立, 所以要先想好要不要设立标记函数,标记函数的计算满足什么样的公式。 最后,它的复杂度估计可以用递推方程的方法 或者备忘录的方法来估计它的复杂度函数。