4.2 动态规划算法分析
动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种具体算法。因此,必须对待解决的具体问题进行具体分析,先运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。在上一节中,以最长公共子序列为例,给出了如何用动态规划思想求解最优化问题。这一节,将从抽象的角度来分析什么样的问题可以用动态规划思想求解,并介绍动态规划方法的最优化问题中的两个要素:最优子结构和重叠子问题。
4.2.1 最优子结构
用动态规划优化问题的第一步是描述最优解的结构。当一个问题具有最优子结构时,动态规划思想就可能适用于解决该问题(在这种情况下,贪心策略可能也是适用的,后续章节会介绍贪心策略)。最优子结构性质可以表述为:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态的最优决策。
也就是说,在动态规划中,利用子问题的最优解可以得到原问题的最优解,因此在设计算法时,必须认真分析,确保所考虑的子问题范围中,要包含用于最优解中的那些子问题。
上一节的最长公共子序列问题就具有最优子结构性质,两个序列X和Y的最长公共子序列可以通过这两个序列的前缀间(“Xm-1和Yn-1”或“Xm-1和Y”或“X和Yn-1”)的最长公共子序列来构造。在寻找一个问题的最优子结构时,可以采用以下思路求解。
1)试着将待解决问题抽象为做选择的问题,做这种选择会得到一个或多个有待解决的子问题。
2)假设这个待解决问题已经有已知的可以得到最优解的选择,暂且不关心这个选择是如何确定的。
3)已知这个选择后,分析会出现哪些待解决的子问题,并试着恰当地描述这些子问题。
4)证明在待解决问题的一个最优解中,使用的子问题的解本身也是子问题的最优解。
下面用一个简单的例子对上面的思路作进一步的说明。假设现在有一个有向图G=(V,E)和结点u, v∈V。要求找出一条从u到v的包含最少边数的路径。这样的一条路径必须是简单路径,因为从路径中去掉一个回路后,会产生边数更少的路径。这个问题被称为无权最短路径。
首先假设u≠v,这样任意从u到v的路径p必然包含一个中间顶点w。这个问题其实等价于判断这个有向图中每一个顶点是否在路径p上,因此得到了一个选择问题,即是否选择某顶点作为最短路径上的一个顶点。下一步,可以假设顶点w在这条最短路径p上(暂且不关心这个结论是如何确定的),那么路径p就可以分解为两条子路径,即从顶点u到w的子路径p1和从顶点w到v的子路径p2。那么就将解决原问题变成了解决两个子问题。现在就需要证明路径p1和路径p2是否必须是顶点u到w和顶点w到v的无权最短路径,如果是的话,那么就说明这个问题的最优解中包含的子问题的解也是最优解(该证明很容易,故不在此赘述)。可以考虑使用动态规划思想解决。实际上,通常要考虑所有的中间顶点w,先找出从u到w的一条最短路径和从w到v的一条最短路径,然后选择一个会产生整体最短路径的中间结点w,从而找出从u到v的一条最短路径。
4.2.2 重叠子问题
动态规划求解的最优化问题必须具备的第二个要素是重叠子问题。重叠子问题指的是:在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些问题已经被反复计算多次。对于这些会被求解多次的子问题,在动态规划算法中,对这些子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。
以上一节中介绍的最长公共子序列为例,在解c[m,n]时,由递归式可知需要反复查看参数较小的子问题的解。例如给出序列X=<A,B,C,B,D,A,B>与序列Y=<B,D,C,A,B,A>,按照递归的思路,计算c[7,6]时,需要调用四次c[4,2],如果c[4,2]每次都被重新计算,而不是被查看,则所增加的运行时间相当可观。事实上,可以证明由递归程序直接来计算c[m,n]的运行时间为O(2mn)。然而,如果使用自底向上的动态规划算法,那么可以发现解c[m,n]时,因为最多有m⋅n个子问题,从表4.1中可知,每个子问题只会被计算一次,计算每个子问题的时间为O(1),因此,用动态规划解LCS的运行时间为O(mn)。