算法导论之动态规划(最长公共子序列和最优二叉查找树)_算法导论 最长子序和

动态规划师通过组合子问题的解而解决整个问题，将问题划分成子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。和分治算法思想一致，不同的是分治算法适合独立的子问题，而对于非独立的子问题，即各子问题中包含公共的子子问题，若采用分治法会重复求解，动态规划将子问题结果保存在一张表中，避免重复子问题重复求解。

动态规划在多值中选择一个最优解，其算法设计一般分为4个步骤：描述最优解的结构；递归定义最优解的值；按自底向上的方式计算最优解的值；由计算出的结果构造一个最优解。

1）装配线调度

求解最快通过工厂装配线路线的问题，问题描述：有两条装配线，用于安装汽车底盘的零件，建造时间不同采用技术有差异导致安装时间有快慢；每条装配线有n个装配站，装配线i的第j个装配站表示为S_ij，相应装配时间为a_ij，每条装配线上一样编号的装配站执行相同的功能，如S_1j和S_2j。

三个时间点说明：

进入时间：一个汽车地盘进入装配线（i为1或2），花费时间为e_i；

移动时间：在同一条装配线上的相邻装配站（从j到j+1）移动没有时间开销，但如果从一条装配线的装配站S_ij移动到另一条装配线上，移动需花费时间t_ij；

离开时间：在完成一条装配线n个装配站后，花费x_i时间离开装配线。

要求解的问题是：求解分别通过装配线1的几个站和装配线2的几个站，才能使汽车底盘零件完成安装的时间最小。

如果已知一个序列的，在装配线1使用那些站，在装配线2使用那些站，则可以在线性时间内得出一个底盘通过工厂装配线要花的时间。但要知道那条路线是时间花费最小，却有2ⁿ中可能，一条装配线所使用的装配站可以看成是{1，2，…，n}的子集。动态规划法就是从2ⁿ中可能发现最优解，我们按照动态规划法四个步骤来说明：

第一步骤：描述最优解的结构

这一步其实就是找到最优解的特征，从而能够将问题转化为若干个子问题来求解。对于装配线调度花费时间最小问题，要描述其最优解，要从一个最基本的假设出发。假设通过装配站S_1j的最快路线通过装配站S_1j-1，那么底盘是利用了最快的路线从开始点到装配站S_1j-1，如果不是，就是存在另一个条从开始点到装配站S_1j-1的更快路线，这就形成矛盾。这个思路理解起来很简单，就是假设你是最快的途经点，那么该点前面的路线也一定是最快，否则就不会经过该店。

照此，找出通过装配站S_1j的最快路线的问题最优解，可以转化为寻找S_1j-1或S_2j-1最快路线的子问题的最优解。这个就是：要寻找该点的最快，那么就找出该点前面必经的点的最快，这里装配线只有两个点会是子结构，装配线1的j-1站或装配线2的j-1站。这和路线规划一致，要找到某一点最短路径，只要找出这一点前面所有点的最短路径即可，把问题拆借成子问题。

总结下，装配线最快时间调度问题的最优解结构：

通过装配站S_1j的最快路线有两个可能：一是通过装配站S_1j-1的最快路线，然后直接通过装配站S_1j；二是通过装配站S_2j-1的最快路线，从装配线2移动到转配线1，然后通过装配站S_1j；类似，装配站S_2j的最快路线也有两个可能。

第二步骤：递归定义最优解的值

输入：装配站执行时间a_ij,装配线之间装配站移动时间t_ij,装配线进入时间e_i和装配线退出时间x_i及每条装配线装配站的数量n

Fun_FastestWay(a,t,e,x,n){

f₁[1]=e₁+a₁₁

f₂[1]=e₂+a₂₁

for j=2 to n

        do if f₁[j-1]+ a_1j=<f₂[j-1]+ a_1j +t_2j-1

            then f₁[j]=f₁[j-1]+a_1j

                 l₁[j]=1 //装配线

            else f₁[j]= f₂[j-1]+a_1j +t_2j-1

                 l₁[j]=2

        if f₂[j-1]+ a_2j=<f₁[j-1]+ a_2j +t_1j-1

then f₂[j]=f₂[j-1]+a_2j

                 l₂[j]=2

            else f₂[j]= f₁[j-1]+a_2j +t_1j-1

                 l₂[j]=1

    if f₁[n]+ x₁ =< f₂[n]+x₂

        then f= f₁[n]+ x₁

                    l=1

    else f= f₂[n]+ x₂

                    l=2

}

这个算法过程就是计算出每一个装配站的值，记录在表格中并保存。

第四步骤：构造最优解

上个步骤计算出的每个装配站时间，就可以输出最快路线的最优解。

2）矩阵链乘法

提出用动态规划法解决矩阵链乘法，有两个前提，一个是矩阵乘法满足结合律；另一个是当两个矩阵相容时才能相乘，所谓相容，就是A的列数等于B的行数。对于n个矩阵链相乘，用括号分组求解，然而不同的加括号分组顺序，在求积的时间上有很大不同。矩阵A(pxq)和B(qxr)相乘，运算次数为pxqxr次，一个矩阵组的不同分组顺序显然在时间性能上会有很大不同。

这就提出了矩阵链乘法的问题：由n个矩阵构成的一个链<A₁,A₂,…,A_i,…,A_n>，其中，i=1,2,…,n，矩阵A_i的维数（行X列）为p_i-1xq_i，以最小化的运算次数对矩阵链进行括号分组，求得A1A2…An乘积。针对问题，采用动态规划法四个步骤来求解。

第一步：描述最优解的结构

动态规划方法的第一步就是寻找最优子结构，利用子结构，可以根据子问题的最优解构造出原问题的一个最优解。一个问题的最优解可以由子问题的最优解构成，而这种最优子结构显然是可以构成递归的。对于矩阵链乘法的最优子结构也很好理解，A_i,j表示矩阵乘积A_iA_i+1…A_j求值的结果，其中i<=j，取k为i和j之间的取值的，可以将矩阵A_i,j的求值分成A_iA_i+1…A_k到A_kA_k+1…A_j两个区间并求其最优解，类似装配线调度问题，假设A_iA_i+1…A_j为最优解，则从k分开的两个区间是最优加括号。

有了这样的最优子结构，就可以根据子问题的最优解来构造原问题的一个最优解。矩阵链乘法求解的问题，可以构造出最优子结构，或者说存在子结构可以求得最优解，即分割乘积，问题的最优解包含了子问题的最优解。

第二步：定义递归最优解

这一步就是根据子问题的最优解来递归定义一个最优解的代码。矩阵链乘法的问题就是确定A_iA_i+1…A_j加全部括号的乘积最小代价问题。设m[i,j]为计算矩阵A_i,j所需的标量乘法运算次数的最小值，就是给矩阵链怎么分割（用加括号）才能让乘积运算次数代价最小。那么，对整个问题来说，计算A_1,n的最小代价就是m[1,n]。

假设最优加全部括号将乘积A _iA _i+1…A _j从A _k和A _k+1之间分开，其中i=<k<j，使m[i,j]为计算子乘积A _iA _i+1…A _k和A _kA _k+1…A _j的代价，再加上两个矩阵相乘的代价，假设每个矩阵A _i从是p _i-1xp _i的，则A _i…kA _k+1…j要进行p _i-1p _kp _j次标量乘法，从而得出：

第三步：计算最优代价

同样的，如果用递归来实现，算法是指数级时间，而矩阵链乘法问题的子问题显然满足重叠这个性质，可以用自底向上的表格法来计算最优代价。适合动态规划法的问题，第一个特点就是具有最优子结构，第二个特点就是子问题重叠。

假设矩阵A_i的维数是p_i-1xp_i，i=1,2,…,n。输入一个序列p=<p_0,p₁,…,p_n>，length[p]=n+1，设计一个辅助表m[1…n,1…n]来保存m[i,j]的代价，并使用辅助表s[1…n,1…n]来记录m[i,j]取得最优解时k的值。

Fun_Matrix_chain_order(p){

    n= length[p]-1;

    for i=1 to n

        do m[i,j]=0;//i=j下代价为0

    for l=2 to n

        do for i=1 to n-l+1

            do j=i+l-1;

            m[i,j]=∞；//初始化i<j的每一个区间代价

            for k=i to j-1

                do q=m[i,k]+m[k+1,j]+ p_i-1p_kp_j

                        if q<m[I,j]

                     then m[i,j]=q;

                          s[i,j]=k;

    return m and s;

}

这个算法比较好理解，就是循环计算每个区间的代价，然后用两个辅助表记录，三层循环，算法时间为O(n3)，空间需要两个表的耗费。

第四步：构造最优解

有了第三步的矩阵链乘积最优标量乘法次数，利用m和s表很容易构造出最优解。

3）动态规划的特性

动态规划方法的四步骤通过矩阵链乘法和装配线调度两个问题已经比较清晰勾勒了，需要总结下现实中怎样的问题适合用动态规划法来解决呢？

前文已经提到，适合采用动态规划方法来求解最优问题需要满足两个特性：具有最优子结构和重叠子问题，同时子问题是独立的。

如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。寻找最优子结构，可以遵循如下模式：

问题的一个解是一个选择，对于给定的问题存在最优解的选择，且子问题的最优解具有相同结构，可以由子子问题的最优解构成。

通俗地说：这个问题可以分成具有相同结构的子问题，这样就可以把求问题最优解分到求子问题的最优解。相同结构也将是说问题是重叠的，可以将解原问题的递归算法反复地用来解子问题。这个分治法解决的问题不一样，分治法产生的子问题都是全新的，不具有相同结构。换句话说，动态规划法要解决的问题，具有俄罗斯套娃一样的性质，而分治法面对的则是子问题都具有不同结构和求解性质，不能将同样算法用于问题和不同子问题。这里还需要提到的是贪心算法和动态规划法一样适用于问题具有最优子结构，不同的是，贪心算法是以自顶向下的方式来适用最优子结构，而动态规划师自底向上；就是说，贪心算法和动态规划法面对最优子结构，贪心算法是先定最优解再求子问题最优解，而动态规划正好相反，先求子问题最优解在推问题最优解；贪心算法是先选择最优而后求解，动态规划法是先求解最优而后选择。

值得说明的是，动态规划要求其子问题重叠同时也要求其独立。何谓子问题独立？就是同一个问题的两个子问题不共享资源，则他们是独立。而重叠是指子问题是相同的，只不过作为不同问题的子问题。对于理解子问题是独立的，导论中给出了无权最短路径和无权最长简单路径的分析，回到现实中，也是很好理解这个案例所说明的全权最长简单路径的子问题不独立，无法应用动态规划法来解决。最短路径就不说了，最长问题分解到子问题，显然在某个图节点上不是独立的。

更有现实应用意义的当属应用动态规划法寻找最长公共子序列和最优二叉查找树。最大公共子序列（LCS）文中提到可用于DNA串相似匹配，就是寻找两个字符串之间具有公共序列的最长度。最优二叉查找树文中提到用于单词翻译，并根据频率构造最优二叉树，这显然也适合于根据频率来排序的场景。这两个案例的动态规划法构造四步骤过程就不描述，原理类似，最主要在现实应用中，寻找满足动态规划法解决的问题，并改良以适用。

后续如遇到类似 最长公共子序列和最优二叉查找树的场景，再研究其动态规划法来解决。