动态规划算法的原理、应用和最新进展( 南开大学 申科)

在计算机算法设计方法中，动态规划技术是比较基本，但又比较抽象，难于理解的一种。它建立在最优原则的基础上，采用动态规划方法，可以优雅而高效地解决许多用贪心技术或分治技术无法解决的问题。因此，动态规划技术越来越成为解决许多重要的应用问题的关键技术。例如，用动态规划解决0-1背包问题、图像数据压缩、矩阵连乘、有向图最短路径、无交叉子集、元件折叠以及最长公共子序列等应用问题。另外，在语音识别领域，应用动态规划技术的动态时间伸缩算法DTW 取得了很大成功，当词汇表较小以及各个词条不易于混淆时，DTW可以有效的解决孤立词识别时说话速度不均匀的难题，从而自20世纪60年代末期掀起了语音识别研究的热潮。
1 动态规划技术的基本原理
1.1 算法思想
动态规划与贪心策略类似，将一个问题的解决方案视为一系列决策的结果。不同的是，贪心算法每采用一次贪心选择便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优决策自序列。使用动态规划时，所求问题应具有以下两种性质。
1.1.1 最优子结构性质
所求问题的最优子结构性质是采用动态规划算法的条件之一，这种性质又被称为最优化原理。动态规划方法采用最优化原理来建立用于计算最优解的递归式。所谓最优化原理即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯以构造最优解。当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助我们高效地解决问题。
1.1.2 子结构重迭性质
人们总希望编写一个简单的递归程序来求解动态规划递归方程。然而，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题，复杂性将大幅度下降。这种方法的思想是：由程序设置“备忘录”，每计算出一个新的子结构的解时，都保存起来。当遇到一次递归时，判断是否已经计算，如果已经计算，只需取出先前保存的结果既可。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。
2 动态规划算法设计举例
2.1 最短路径
假设G中每条边都有一个长度，每条有向路径的长度等于该路径中各边的长度之和。对于每对顶点 ，在顶点i 与j 之间可能有多条路径，各路径的长度可能各不相同。我们定义从i 到j 的所有路径中，具有最小长度的路径为从i 到j 的最短路径。将n 个顶点编号为1到n。令c (i, j, k)表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点。对于任意k＞0，如何确定c (i, j, k) 呢？中间顶点不超过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为 ，否则长度为。c(i, j, k) 可取两者中的最小值。因此可得到如下递归式：
以上的递归式将一个k 级运算转化为多个k-1 级运算，而多个k-1 级运算应比一个k 级运算简单。如果用递归方法求解上式，则计算最终结果的复杂性将无法估量。经过计算可知，得到所有c (i, j, n) 的时间为 。当注意到某些c (i, j, k-1) 值可能被使用多次时，可以更高效地求解c (i, j, n)。利用避免重复计算c(i, j, k) 的方法，可将计算c 值的时间减少到 。这可通过递归方式或迭代方式来实现。迭代算法的C++伪代码如下所示。
//寻找最短路径的长度
//初始化ci，j，1）

for (int i=1; i <= n; i++)
for (int j=1; j <= n; j++)
c(i ,j, 0) = a (i, j); // a 是长度邻接矩阵
//计算c( i ,j, k ) ( 0 < k < = n )
for(int k=1;k <= n;k++)
for(int i=1;i <= n;i++)
for(int j=1;j <= n;j++)
if(c(i, k, k-1)+c(k, j, k-1) < c(i, j, k - 1))
c(i, j, k) = c(i, k, k - 1) + c(k, j, k - 1);
else c(i, j, k) = c (i, j, k - 1) ;

2.2 0-1背包问题
在0-1的背包问题中，最优决策序列由最优决策子序列组成。假设 表示剩余容量为y，剩余物品为i，i + 1，…，n 时的最优解的值，即：
(2-1)
和
(2-2)
在该例中，可得出 ，所以 。接着利用返回值 计算 及 ，此时 ，又由 ，得 ，因此 ，此时 ，所以 ，即得 。
利用递归计算 的函数如下：

//计算f(i, y)
int F(int i, int y)
{
if (i == n) return (y < w[n]) ? 0 : p[n];
if (y < w[i]) return F(i+1,y);
return max(F(i+1,y), F(i+1,y-w[i]) + p[i]);
}

通过分析可知，算法的时间复杂度为 。可见，直接递归的时间开销是指数级的，必须加以改进。经过分析可以得到，递归程序中经过了大量的重复计算。为了避免 的重复计算，可以利用前面讨论过的“备忘录”方法。具体做法为：定义一个用于保留已被计算出值的映射表M，该表格的每一个元素是三元组 。在计算 之前，应检查M中是否已包含一个三元组 ，其中*表示任意值。如果已包含，则从M中取出的值，否则，对 进行计算并将计算所得的三元组 加入M。实际中M可以用Hash的形式存储。
3 动态规划技术在实际中的应用和最新研究进展
3.1 孤立词语音识别系统的DTW算法
动态时间伸缩算法(Dynamic Time Warpping，简称DTW)，是日本学者板仓(Itakura)将动态规划技术应用于解决孤立词识别时的说话速度不均匀的难题，提出的把时间规整和距离测度计算结合起来的一种非线性归整技术。设测试语音参数共有I桢矢量，而参考模板共有J桢矢量，且 ，则动态时间规整就是要寻找一个时间规整函数，它将测试矢量的时间轴i非线性的映射到模板的时间轴j上，并使该函数 满足：
式中， 是第i桢测试矢量 和第j桢模板矢量 之间的距离测度，D则是处于最优时间规整情况下两矢量的距离。
而实际使用中，DTW是采用动态规划技术(DP)来加以具体实现的。通常，规整函数被限制在一个平行四边形内，它的一条边的斜率为2，另一条边的斜率为1/2。规整函数的起始点为(1,1)，终止点为(I,J)。的斜率为0、1或2；否则就为1或2。我们的目的是寻找一个规整函数，在平行四边形内由点(1,1)到点(I,J)具有最小代价函数。总代价函数的计算式为：
式中， 为匹配点 本身的代价， 是在以前所有允许值中最小的一个。因此，总代价函数是该点本身的代价与带到该点的最佳路径的代价之和。当词汇表较小以及各个词条不易于混淆时，这个算法取得了很大的成功，从而自20世纪60年代末期掀起了语音识别研究的热潮。直到现在，DTW算法仍然广泛的应用于小词汇量语音识别，说话人确认系统，嵌入式语音识别系统等各个领域。
3.2 最长公共子序列(LCS)及其衍生问题
LCS（最长公共子序列）问题可以简单地描述如下：
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A，B，C，B，D，B，A}，Y={B，D，C，A，B，A}，则序列{C，B，A}是X和Y的一个公共子序列，但它不是X和Y 的一个最长公共子序列。序列{B，C，B，A}也是X和Y的一个公共子序列，它的长度为4，而且它是X和Y的一个最长公共子序列，因为X和Y没有长度大于 4的公共子序列。
最长公共子序列问题就是给定两个序列X={x1,x2,…xm}和Y={y1,y2,…yn}，找出X和Y的一个最长公共子序列。对于这个问题比较容易想到的算法是穷举，对X的所有子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的每个子序列相应于下标集{1,2,...,m}的一个子集。因此，共有个不同子序列，从而穷举法搜索需要指数时间。
事实上，最长公共子序列问题具有最优子结构性质：
设序列X={x1,x2,…xm}和Y={y1,y2,…yn}的一个最长公共子序列为Z={z1,z2,…zk}，则
1. 若 ，则 ，且Zk-1是Xm-1和Yn-1的最长公共子序列。
2. 若 且 ，则Z是Xm-1和Y的最长公共子序列。
3. 若 且 ，则Z是X和Yn-1的最长公共子序列。
通过以上的结论，我们观察到——两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，这使我们有可能将算法的时间复杂度降低到多项式级别，因为这两个序列的不同的前缀组合只有 个。并且，根据以上结论，我们可以得出计算Xi和Yj的最长公共子序列的长度 的公式:
当 或 时， 。
当 且 时， 。
当 且 时， 。
这样一来，解决这个问题就比较容易了，通过建立递推结构，可以得出下列算法：

//求序列X和Y的最长公共子序列
for (i=1;i<=m;i++)
　 c[i][0]=0;
for (i=1;i<=n;i++)
　 c[0][i]=0;
for (i=1;i<=m;i++)
{
　　for (j=1;j<=n; j++)
　　{
　　　if (x[i]==y[j])
　　　　c[i][j]=c[i-1][j-1]+1;
　　　else if (c[i-1][j]>=c[i][j-1])
　　　　c[i][j]=c[i-1][j];
　　　else
　　　　c[i][j]=c[i][j-1];
　　}
}

X和Y的最长公共子序列的长度就存于c[m][n]中，欲求出具体的子序列，则可通过数组的值用 的时间回推，具体的方法不再赘述。
4 结束语
动态规划技术是基本算法设计技术中较难掌握但也是极其重要的一种方法，它的应用领域非常广泛，除了本文提到的一些问题之外，动态规划还用于解决字符串搜索问题、手写字符识别问题、网络的无交叉布线、电路元件折叠和旅行商问题等各种实际应用问题，因此，掌握动态规划技术对提高计算机算法设计和分析水平及解决实际计算问题具有至关重要的作用和意义。