算法分析与设计总结---动态规划_什么是最优子结构性质?请说明动态规划方法为什么需要最优子结构性质

---

前言

算法分析与设计课程学习后的一些总结，本文主要介绍动态规划。

---

一、DP简介

动态规划为什么需要最优子结构性质

动态规划算法通常用于求解具有某种最优性质的问题，需要最优子结构性质来确定最优策略。一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

动态规划与分治算法的区别

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

步骤

（1）刻画一个最优解的结构特征。
（2）递归地定义最优解的值
（3）计算最优解的值。①带备忘录的自顶向下②自底向上
（4）利用计算出的信息构造一个最优解。

二、DP应用

1.矩阵链相乘

步骤1：最优括号化方案的结构特征
动态规划方法的第一步是寻找最优子结构，然后就可以利用这种子结构从子问题的最优解构造出原问题的最优解。在矩阵链乘法问题中，此步骤的做法如下所述。为方便起见，我们用符号A_(i,j)(i≤j) A_i A_(i+1)……A_j乘积的结果矩阵。对A_i A_(i+1)……A_j进行括号化，我们就必须在某个A_k和A_(k+1)之间将矩阵链划分开。也就是说,对某个整k,我们首先计算矩阵A_(i,k), A_(k+1,j) ,然后再计算它们的乘积得到最终结果A_(i,j) 。此方案的计算代价等于矩阵A_(i,k)的计算代价，加上矩阵A_(k+1,j)，的计算代价，再加上两者相乘的计算代价。本问题的最优子结构：假设A_i A_(i+1)……A_j的最优括号化方案的分割点在A_k和A_(k+1)之间。那么，继续对“前缀”子链A_(i,k)进行括号化时，应直接采用独立求解它时所得的最优方案。也就是说我们每次求的子问题，都是最优的结构
步骤2：一个递归求解方案
下面用子问题的最优解来递归地定义原问题最优解的代价。令m[i,j]表示计算矩阵A_(i,j)所需标量乘法次数的最小值。递归定义m[i,j]如下。

步骤3：计算最优代价

备忘录设计：

m矩阵(备忘录)：

伪代码（递归）：

RECURSIVE-MATRIX-CHAIN(p,i,j)
	if m[i][j] exists then // 备忘录
		return m[i][j]
	if i==j then 
		return 0;
	end if
	m[i][j] = +INF  // 初始化正无穷，保证会被更新
	for k=i to j-1 do
		v = RECURSIVE-MATRIX-CHAIN(P,i,k) + RECURSIVE-MATRIX-CHAIN(P,k+1,j) + p[i-1]p[k]p[j]
		if v < m[i][j] then
			m[i][j]=v;
		    s[i][j]=k; 
		end if
	end for
	return m[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

步骤4：构造最优解
s[i,j]记录了构造最优解所需的信息。每个表s[i,j]记录了一个k值，指出A_i A_(i+1)……A_j最优括号化方案的分割点应在某个A_k和A_(k+1)之间。因此，我们通过表s[i,j]可以很轻易的得出整个矩阵链的切分点。

2.最长公共子序列

给定两个子序列X={x1,x2,x3…,xm}和Y={y1,y2,y3…yn},找出X和Y的一个最长的公共子序列。例如：X={A,B,C,B,A,D,B}，Y={B,C,B,A,A,C},那么最长公共子序列是B,C,B,A。
（1）分析最优解的结构特征
假设已经知道Zk={z1,z2，z3…,zk}是Xm={x1,x2,x3，…xm}和Yn={y1,y2,y3,…yn}的最长公共子序列。这个假设很重要，我们都是这样假设已经知道最优解。
那么可以分三种情况讨论。
①. xm=yn=zk；那么Zk-1={z1,z2，z3…,zk-1}是Xm-1和Yn-1的最长公共子序列，应该容易理解吧。
②. xm≠yn, xm≠zk；我们可以把xm去掉，那么Zk是Xm-1和Yn的最长公共子序列。
③. yn≠xm, yn≠zk; 我们可以把yn去掉，那么Zk是Xm和Yn-1的最长公共子序列。
（2）建立最优值的递归式
设c[i][j]表示Xi和Yj的最长公共子序列长度。
①. xm=yn=zk；那么c[i][j]=c[i-1][j-1]+1;
②. xm≠yn, xm≠zk；那么我们只需要求解Xi和Yj-1的最长公共子序列和Xi-1和Yj的最长公共子序列，比较它们的长度那个更大，就取哪一个值。即c[i][j]=max{c[i][j-1],c[i-1][j]}.
③. 最长公共子序列长度递归表达式：

（3）自底向上计算最优解，并计算最优解和最优策略
i=1时：{x1}和{y1,y2,y3,…yn}中的字符一一比较，按递归式求解并记录最长公共子序列的长度。
i=2时：{x2}和{y1,y2,y3,…yn}中的字符一一比较，按递归式求解并记录最长公共子序列的长度。
…
i=m时：{xm}和{{y1,y2,y3,…yn}中的字符一一比较，按递归式求解并记录最长公共子序列的长度。
（4）构造最优解
上面的求解过程只是得到了最长公共子序列长度，并不知道最长公共子序列是什么，那么怎么办呢？
例如，现在已经求出c[m][n]=5,表示Xm和Yn的最长公共子序列是5，那么这个5怎么得到的呢？我们可以反向追踪5是从哪里来的。根据递归式，有如下情况。
xi=yj时；c[i][j]=c[i-1][j-1]+1;
xi≠yj时；c[i][j]=max{c[i][j-1],c[i-1][j]}；
那么c[i][j]的来源一共有三个：c[i][j]=c[i-1][j-1]+1,c[i][j]=c[i][j-1],c[i][j]=c[i-1][j],在第三步自底向上计算最优值时，用一个辅助数组b[i][j]记录这三个来源：
c[i][j]=c[i-1][j-1]+1，b[i][j]=1;
c[i][j]=c[i][j-1]，b[i][j]=2;
c[i][j]=c[i-1][j]，b[i][j]=3;
这样就可以根据b[m][n]反向追踪最长公共子序列，当b[i][j]=1时，输出xi;当b[i][j]=2时；追踪c[i][j-1];当b[i][j]=3时，追踪c[i-1][j];，直到i=0或j=0停止。

代码如下：

import java.util.Scanner;
public class Main {
    static int N=1002;
    static int [][]c=new int[N][N];
    static int [][]b=new int[N][N];//记录最优解来源数组
    static char []s1=new char[N];
    static char []s2=new char[N];
    static int len1,len2;//s1,s2的长度
    static void LCSL(){
        int i,j;
        for(i=1;i<=len1;i++){//控制s1序列
            for(j=1;j<=len2;j++){//控制s2序列
                if(s1[i-1]==s2[j-1]) {//下标从零开始，如果当前的字符相同，则公共子序列的长度为该字符前的最长公共序列
                    c[i][j] = c[i - 1][j - 1] + 1;
                    b[i][j]=1;
                }
                else{
                    if(c[i][j-1]>=c[i-1][j]){//两者找最大值，并记录最优解来源
                        c[i][j]=c[i][j-1];
                        b[i][j]=2;
                    }
                    else{
                        c[i][j]=c[i-1][j];
                        b[i][j]=3;
                    }
                }
            }
        }
    }
    /*
    我们在最长公共子序列长度c[i][j]的过程中，用b[i][j]记录了c[i][j]的来源，所以可以根据b[i][j]数组倒推最优解
     */
    static void print(int i,int j){//根据记录下来的信息构造最长公共子序列（从b[i][j]开始递推）
        if(i==0||j==0)
            return;
        if (b[i][j]==1){//说明s1[i-1]=s2[j-1],递归输出print（i-1，j-1）;然后输出s1[i-1]
            print(i-1,j-1);
            System.out.print(s1[i-1]);
        }
        else if(b[i][j]==2){//说明s1[i-1]≠s2[j-1]且最优解来源于c[i][j]=c[i][j-1],递归输出print（i,j-1）
            print(i,j-1);
        }
        else//即b[i][j]=3,说明s1[i-1]≠s2[j-1]且最优解来源于c[i][j]=c[i-1][j],递归输出print（i-1,j）
            print(i-1,j);
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int i,j;
        String s;
        System.out.println("请输入字符串s1:");
        s=sc.nextLine();
        len1=s.length();
        for(i=0;i<len1;i++){
            s1[i]=s.charAt(i);
        }
        System.out.println("请输入字符串s2:");
        s=sc.nextLine();
        len2=s.length();
        for(i=0;i<len2;i++){
            s2[i]=s.charAt(i);
        }
        for(i=0;i<=len1;i++){
            c[i][0]=0;//初始化第一列为0；
        }
        for(j=0;j<=len2;j++){
            c[0][j]=0;//初始化第一行为0；
        }
        LCSL();
        System.out.println("s1和s2的最长公共子序列的长度是："+c[len1][len2]);
        System.out.println("s1和s2的最长公共子序列是：");
        print(len1,len2);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

3最短路径Floyd

算法：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离

• 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大，这也是所谓的初始化工作；
• 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
  
  代码：

// 计算最短路径,i循环起点，j循环终点，k循环中间点
        for (int k = 0; k < mVexs.length; k++) {
            for (int i = 0; i < mVexs.length; i++) {
                for (int j = 0; j < mVexs.length; j++) {
                    // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
                    int tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                    if (dist[i][j] > tmp) {
                        // "i到j最短路径"对应的值设，为更小的一个(即经过k)
                        dist[i][j] = tmp;
                        // "i到j最短路径"对应的路径，经过k
                        path[i][j] = path[i][k];
                    }
                }
            }
        }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

问：为什么弗洛伊德算法支持负权值？

答：因为路径更新是根据新值和旧值比较获得的，最终的结果都是在最后一次迭代过程中对全局进行更新而得到的，中间的每次迭代只是一次局部调整而非最终结果。而不像迪杰斯特拉采用的贪心策略，每一次迭代都确定出一条最短路径，负权的出现使得不能保证每次迭代都是最优解。

---

滴答

提示：本文是对互联网上搜集内容的一些体会，侵权请联系。