算法分析与设计---分治+动态规划

这篇具有很好参考价值的文章主要介绍了算法分析与设计---分治+动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.分治法

适用条件：

问题规模缩小到一定程度容易求解

问题可以分解为若干个规模较小的相同子问题，即问题具有最优子结构（使用分治法前提）

可以利用子问题的解合并为该问题的解（决定是否使用分治法）

各个子问题相互独立，即子问题之间不包含公共子问题（若不满足，最好使用动态规划算法）

基本步骤：

2.动态规划算法

适用条件：

满足最优性原理，即具有最优子结构性质（该问题最优解包含子问题最优解）

重叠子问题：可分解为相互关联的若干子问题，子问题之间不独立，子问题的解可能在下一决策阶段中被使用

设计思想：

利用最优子结构性质，将问题划分为一系列子问题，求各子问题的最优解，然后以自底向上的方式递归地从子问题的最优解构造出整个问题的最优解。

ps：“填表” ——构建数据结构，保存子问题的最优解，以便求整个问题的最优解。

设计步骤：

（1）划分子问题（分段）：讲整个问题划分为若干个子问题，找到问题的状态，子问题之间具有的重叠关系。

（2）构建状态转移方程（分析）：关联的状态和状态之间相互转换关系。（动态规划的关键）

（3）存储状态的值求解（填表）：设计表格（即数据结构），以自底向上的方式计算各个子问题的解并填表保存，实现动态规划过程。

注：判断问题是否使用动态规划算法，一定要分析问题满足最优性原理

分析问题是否满足最优性原理，一般用反证法

假设由问题的最优解导出的子问题的解不是最优的；

证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

例：

（1）多路段图问题

（2）旅行商问题（TSP问题）

ps：动态规划算法例题：

1.最长公共子序列（LCS）

满足最优性原理--整个问题的最优解包含子问题的最优解

证明：若X=（x1,x2.x3....xm),Y=(y1,y2,y3.....yn),且设z=(z1,z2,z3...zk)为X，Y的最长公共子序列，则：

（1）若xm=yn,则zk=xm=yn，且（z1,z2,z3...z(k-1))是（x1，x2...x(m-1))和（y1，y2...y(n-1))的最长公共子序列；

（2）若xm！=yn且xk！=xm，则（z1,z2,z3...zk)是（x1，x2...x(m-1))和（y1，y2...yn)的一个最长公共子序列；

（3）若xm！=yn且zk！=yn，则（z1,z2,z3...zk)是（x1，x2...xm)和（y1，y2...y（n-1）)的一个最长公共子序列；

综上，最长公共子序列z包含序列X，Y的所有前缀的最长公共子序列。故最长公共子序列问题满足最优性原理。

步骤一：划分子问题（分段）

设LCS（（x1,x2...xi),(y1,y2...yj))为序列X=（x1,x2...xi)和Y=(y1,y2...yj)的最长公共子序列。

情况1：xi=yj

LCS（（x1,x2...xi),(y1,y2...yj)) = LCS（（x1,x2...x（i-1）),(y1,y2...y（j-1）)) +xi(或yj)

情况2：xi！=yj

LCS（（x1,x2...xi),(y1,y2...yj)) =

max（ LCS（（x1,x2...x（i-1）),(y1,y2...yj) ， LCS（（x1,x2...xi),(y1,y2...y（j-1）)) ）

故问题共有m*n个子问题。

步骤二：构建状态转移方程（分析）

定义二数组L，L[i][j]表示 LCS（（x1,x2...xi),(y1,y2...yj)) 的长度(i=1,2,3...m,j=1,2,3...n)

每考虑一个xi或yj都为动态规划的一个阶段。

情况1：xi=yj L[i][j]=L[i-1][j-1]+1

情况2：xi！=yj L[i][j] =max(L[i-1][j],L[i][j-1])

则状态转移方程为：

显然：

初始子问题：X，Y中至少有一个空序列，即：L[0][j]=L[i][0]=0,i=1,2...m,j=1,2...n

L[i][j]是子问题最优解，L[m][n]是整个问题最优解。

步骤三：存储状态的值求解（填表）

基本思想：自底向上计算LCS的长度

填写数组L的值：

算法设计：

为了得到序列（x1,x2,x3...xm)和(y1,y2,y3...yn)最长公共子序列，另设数组S，其中S[i][j]表示在计算L[i][j]过程中的搜索状态，并且有：

故：

①若S[i][j]=1，下一个回溯方向是S[i-1][j-1],即i=i-1，j=j-1；

②若S[i][j]=2,下一个回溯方向是S[i][j-1],即j=j-1；

③若S[i][j]=3，下一个回溯方向是S[i-1][j],即i=i-1；

算法：
算法：最长公共子序列的动态规化算法
输入：序列X，Y
输出：最长公共子序列长度和最长公共子系列z

1.for(i=0;i<=m;i++)  L[i][0] = 0;
  for(j=1;j<=n;j++)  L[0][j] = 0;
2.for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
       if(X[i]==Y[j])  {L[i][j] = L[i-1][j-1]+1; S[i][j]=1;}
       else 
        {
           if(L[i][j-1]>=L[i-1][j])  {L[i][j] = L[i][j-1]; S[i][j]=2;}
           else {L[i][j]=L[i-1][j]; S[i][j]=3;}
        }
3.i=m,j=n,k=L[m][n];
4.while(i>0&&j>0)
{
   if(S[i][j]==1) {z[k]=X[i]; i--;j--;}
   else if(S[i][j]==2) j--;
   else  i--;

}
5.输出L[m][n]和z


时间复杂度：O（m*n）

2.最大子段和问题

问题：给定n个数（可以为负数）的序列（a1,a2,...an)，求

①子问题界定：前边界1，后边界i，C[i]是A[1...i]中包含元素A[i]的向前连续延伸的最大子段和

②构建状态转移方程：

C[i]=max{C[i-1]+A[i],A[i]},i=2,3,...n

若A[1]>0 C[1]=A[1]

否则 C[1]=0

故：OPT（A）=max{C[i]}

③伪码：
算法：MaxSum(A,n)
输入：数组A[n]
输出：最大字段和sum和子段最后位置c

1.max <- 0
  if A[1]>0
  then C[1]:=A[1];
  else  C[1]:=0;
2.for i <- 2 to n do
3.  if C[i-1] > 0
    then C[i] := C[i-1]+A[i]
    else C[i] := A[i]
4.max = 0;
5.for i <- 1 to n do
    if max < C[i]
    then max := C[i]
6.输出max和i

  
时间复杂度：O(n)   

3.矩阵连乘问题

问题：给定n个矩阵{A1,A2...An}，其中Ai与Ai+1是可乘的，确定计算矩阵连乘计算顺序，使得依此次序矩阵连乘积需要的数乘次数最少。输入数据为矩阵的个数和每个矩阵的规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

最优性原理：

为方便起见，将连乘积AiAi+1...Aj简记为A[i:j]，其中Ai的维度记为pi-1×pi。

计算A[i:j]最优次序所包含的计算矩阵子链A[i:k],A[k+1:j]的次序也是最优的。即该问题的最优解包含子问题的最优解，满足最优性原理。

步骤一：划分子问题

问题目的求解A[1:n]的最优解，则可将问题划分为求若干个A[i:j]的最优计算次序。

考察A[i:j]的最优计算次序：设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i<=k<j,则其相应的括号方式为：（AiAi+1..Ak)(Ak+1...Aj)。则A[i:k]的计算量加上A[k+1,j]的计算量，再加上A[i:k]和A[k+1,j]相乘的计算量。

步骤二：建立状态转移方程

设计算A[i:j]，1<=k<j，所需要的最少数乘次数为dp[i,j],原问题的最优值dp[1,n].
①当i=j时，dp[i,j]=0
②当i<j时，dp[i,j]=min{dp[i,k]+dp[k+1,j]+pi-1pkpj

步骤三：存储状态的值求解

在程序中，dp的实现是一个二维数组，也就是一张二维表，为了方便计算，dp的下标从1开始。要计算 A [ 1 : n ]的最少乘次，本质上是求dp[1][n]的值，也就是二维表表右上角的值.
例如，连乘矩阵个数为6，维数分别为：
A 1 ( 30 × 35 ) ；
A 2 ( 35 × 15 ) ；
A 3 ( 15 × 5 ) ；
A 4 ( 5 × 10 ) ；
A 5 ( 10 × 20 ) ；
A 6 ( 20 × 25 ) ；

根据递归公式，对角线的值为0。其他值需要根据于断开位置 k k k的值来得到， k ∈ [ i , j ) k \in [i,j) k∈[i,j)，我们要遍历所有 k k k，就要访问所求值的所有同一行左边的值和同一列下方的值。因此，在代码中我们可以使用自底向上、从左到右的计算顺序来依次填充，最终得到右上角的值。如：

dp[2][5]=min{dp[2][2]+dp[3][5]+p1p2p5,dp[2][3]+dp[4][5]+p1p3p5,dp[2][4]+dp[5][5]+p1p4p5}

关键代码：文章来源地址https://www.toymoban.com/news/detail-467462.html
for(i=1;i<=n;i++)
{
  for(j=i;j<=n;j++)
 {
   if(i==j) dp[i][j]=0;
   else
   {
     for(k=i;k<j;k++)
      {
        temp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
        if (temp < dp[i][j])
        {
            dp[i]j]=temp;
            S[i][j]=k;//记录分割处
        }
      }
   }
 }
}    