精华内容
下载资源
问答
  • 最优子结构特征

    千次阅读 2020-03-22 16:50:02
    优子结构:如果问题的优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。 无后效性:即子问题的解一旦确定,就...

    最优子结构:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
    无后效性:即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
    重复子问题:。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高

    展开全文
  • 文章目录1 概念2 递归写法3 递推写法4 总结4.1 区别4.2 应用条件4.2.1 最优子结构4.2.2 重叠子问题4.2.3 条件4.2.4 区别4.2.4.1 分治和动态规划4.2.4.2 贪心和动态规划 1 概念 动态规划(Dynamic Programming,DP)...

    1 概念

    • 动态规划(Dynamic Programming,DP):用来解决最优化问题的算法思想。
      • 一般来说,动态规划将复杂的问题分解为若干子问题,通过综合子问题的最优解来得到原问题的最优解。
      • 动态规划会将每个求解过的子问题记录下来,这样下次碰到相同的子问题,就可以直接使用之前记录的结果,而不重复计算。
      • 一般用递归或递推的写法来实现动态规划,其中递归写法在此处又称为记忆化搜索。

    2 递归写法

    • 记录子问题的解,来避免下次遇到相同子问题时的重复计算。
      以斐波那契数列为例子:
      斐波那契数列定义为F0 =1,F1 = 1,Fn = Fn-1+Fn-2(n>=2)
      递归写法为:
    int F(int n){
        if(n == 0 || n == 1) return 1;
        else return F(n-1) + F(n-2);
    }
    

    这个递归会涉及到很多重复的计算,如当n==5时,可以得到F(5)= F(4)+F(3),接下来计算F(4)时又会有F(4)= F(3)+F(2),这时不采取措施,F(3)将会被计算两次。如果n很大,重复计算的次数将难以想象。

    实际上由于没有保存中间计算的结果,实际复杂度将会高达O(2n),即每次都会计算F(n-1)和F(n-2)这两个分支,基本上不能承受n较大的情况。

    开一个数组dp,用来保存已经计算过的结果,其中dp[n]记录F(n)的结果,并用dp[n] = -1来表示F(n) 当前还没有被计算过。

    int dp[MAXN];
    

    然后就可以在递归中判断dp[n]是否是-1,如果不是-1,说明已经计算过F(n),直接返回dp[n]就是结果;否则,按照递归式进行递归。

    int F(int n){
        if(n == 0 || n == 1) return  1;
        if(dp[n] != -1) return dp[n];
        else{
            dp[n] = F(n-1) + F(n-2);
            return dp[n];
        }
    }
    
    

    通过记忆化搜素,把复杂度从O(2n)降到O(n)。
    斐波那契数列递归图:
    在这里插入图片描述
    斐波那契数列记忆化搜索示意图:
    在这里插入图片描述

    如计算F(45),直接使用递归用时9.082809,用记忆化搜索仅仅0.000001
    计算代码:

    #include <cstdio>
    #include <ctime>
    #include <cstdlib>
    #include <algorithm>
    
    using std::fill;
    
    const  int MAXN = 1000;
    int dp[MAXN];
    
    int F2(int n){
        if(n == 0 || n == 1) return 1;
        else return F2(n-1) + F2(n-2);
    }
    int F(int n){
        if(n == 0 || n == 1) return  1;
        if(dp[n] != -1) return dp[n];
        else{
            dp[n] = F(n-1) + F(n-2);
            return dp[n];
        }
    }
    
    int main(){
        int n = 45;
        int ans;
        fill(dp, dp + MAXN, -1);
        clock_t start,end;
    
        srand((unsigned)time(NULL));//随机数种子
    
        start = clock();//开始记时
        ans = F2(n);
        end = clock();
    
        printf("%d\n", ans);
        printf("Time is %f\n", double(end - start) / CLOCKS_PER_SEC);//输出运行时间
    
        srand((unsigned)time(NULL));//随机数种子
        start = clock();//开始记时
        ans = F(n);
        end = clock();
    
        printf("%d\n", ans);
        printf("Time2 is %f\n", double(end - start) / CLOCKS_PER_SEC);//输出运行时间
    
        return 0;
    }
    

    3 递推写法

    以数塔问题为例:
    将一些数字排成数塔形状,其中第一层有一个数字,第二层有两个数字,。。。第n层有n个数字。现在要从第一层走到第n层,每次只能走向下一层连接的两个数字中的一个。问:最后将路径上所有数字相加后得到的和最大是多少?

    Sample Input:
    5 //5层数塔,下面有5行
    5
    8 3
    12 7 16
    4 10 11 6
    9 5 3 9 4
    Sample Output:
    44

    • 思路:
      从第一层出发,按5-8-7的线路来到7,并枚举从7出发到达最底层的所有路径,但是,之后按5-3-7的线路再次来到7时,又回去枚举从7出发到达最底层的所有路径。这导致从7出发到达最底层的所有路径被反复的访问,做了许多多余的计算。

    其实可以把从7出发到达最低层的所有路径能产生的最大和记录下来,这样再次访问7就能直接获取这个最大值,避免重复计算。

    如果要求出“从位置(1,1)到达最底层的最大和”dp[1][1],那么一定要求出它的两个子问题,“从位置(2,1)到达最底层的最大和”d[2][1]和"从位置(2,2)到达最底层的最大和"d[2][2],即进行一次决策,
    走数字5左下,还是右下。于是dp[1][1]就是dp[2][1]和dp[2][2]的较大值加上5,写成式子就是:
    dp[1][1] = max(dp[2][1], d[2][2])+f[1][1]

    令dp[i][j]表示从第i行第j个数字出发的到达最低层的所有路径上所能得到的最大和
    由此得到要求dp[i][j],
    dp[i][j] = max(dp[i+1][j], dp[i + 1][j +1])+f[i][j]
    把dp[i][j]称为状态,上面的式子称为状态转移方程,它把状态dp[i][j]转为dp[i+1][j]和dp[i + 1][j +1]。

    可以发现dp[i][j]只与i+1层的状态有关,与其他层无关。

    边界(直接确定其结果):数组dp最后一层dp总是等于元素自身

    动态规划的递推写法,总是从这些边界出发,通过状态转移方程扩散到整个dp数组。

    • 参考代码
    #include <cstdio>
    #include <algorithm>
    
    using std::max;
    
    const int MAXN = 1000;
    int f[MAXN][MAXN], dp[MAXN][MAXN]; 
    
    int main(int argc, char const *argv[])
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= i; ++j)
            {
                scanf("%d", &f[i][j]);
            }
        }
    
        //边界
        for (int i = 1; i <= n; ++i)
        {
            dp[n][i] = f[n][i];
        }
    
        //从n-1层不断向上计算dp[i][j]
        for (int i = n - 1; i >= 1; --i)
        {
            for (int j = 1; j <= i; ++j)
            {
                //状态转移方程
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
            }
        }
    
        printf("%d\n", dp[1][1]);
        return 0;
    }
    

    4 总结

    4.1 区别

    • 递推写法:自底向上,即从边界开始,不断向上解决问题,直到解决了目标问题。
    • 递归写法:自顶向下,从目标问题开始,将他们分解成子问题的组合,直到分解到边界为止。

    4.2 应用条件

    4.2.1 最优子结构

    问题拥有最优子结构:一个问题的最优解可由子问题的最优解有效构造出来。

    最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导而来。

    因此一个问题必须拥有最优子结构,才能用动态规划解决。

    4.2.2 重叠子问题

    一个问题必须拥有重叠子问题,才能使用动态规划求解。

    重叠子问题:一个问题可以被分为若干个子问题,且这些子问题会重复出现。

    4.2.3 条件

    一个问题必须拥有重叠子问题和最优子结构,才能用动态规划来解决。

    4.2.4 区别

    4.2.4.1 分治和动态规划

    共同点:都是将问题分解成子问题,然后合并子问题的解得到原问题。

    • 区别:
      • 分治分出来的子问题是不重叠的,如归并排序和快速排序(分别处理左右排序,然后将左右序列结果合并),分治解决的问题不一定是最优化问题。
      • 动态规划解决的问题拥有重叠子问题,且一定是最优化问题。

    4.2.4.2 贪心和动态规划

    共同点:都要求问题拥有最优子结构。

    • 区别
      • 贪心:整个过程以单链的流水方式进行,显然这种“最优的选择”的正确性需要用归纳法证明。例如数塔问题,贪心从最上层开始,每次选择左下或右下较大的那个,一直到最底层得到结果,显然这不一定可以得到最优解。
      • 动态规划:无论采用自底向上还是自顶向下的方法,都是从边界向上得到最优解,它总是会考虑所有子问题,并选择继承能得到最优结果那个,对于暂时没被继承的子问题,由于重叠子问题的存在,后期可能会再次考虑它,因此还有机会成为全局最优的一部分,不需要放弃。
    展开全文
  • ------ 本文是学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------ 上一节,我通过两个非常的问题,向你展示了用动态规划问题的过程。今天主要讲一些理论知识。学完这节内容,可以帮你解决这几个问题:...

    ------ 本文是学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------

    上一节,我通过两个非常的问题,向你展示了用动态规划问题的过程。今天主要讲一些理论知识。学完这节内容,可以帮你解决这几个问题:什么样的问题可以用动态规划来解决?解决动态规划问题的一般思路是什么?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系。

    “一个模型三个特征”理论的讲解

    动态规划作为一个非常成熟的算法思想,很多人对此做了非常全面的总结,我把这部分理论总结为“一个模型三个特征”。

    首先,“一个模型”指的是动态规划适合解决问题的模型。我把这个模型定义为“多阶段决策最优解模型”。

    具体来说,我们一般是用动态规划来解决最优问题。而解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应一组状态。然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。

    三个特征”,分别是最优子结构无后效性重复子问题。这三个概念比较抽象,逐一解释一下。

    1、最优子结构

    最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也可以理解为,后面阶段的状态可以通过前面状态推导出来。

    2、无后效性

    无后效性,有两层含义,第一层含义是,在推导后面阶段状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。

    3、重复子问题

    这个概念,前面一节,已经多次提到。用一句话概括就是: 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。

    “一个模型三个特征”实例剖析

    “一个模型三个特征”这部分理论知识,比较抽象,你看了之后可能还是有点懵,有种似懂非懂的感觉,没关系,这个很正常。接下来,我结合一个具体的动态规划问题,来详细解释下。

    假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角,终止位置在右下角。我们将棋子从左上角移到右下角。每次只能向右或者向下移动一位。整个过程,会有多种不同的路径可以选择。我们把每条路径经过的数字加起来看作路径的长度。那从左上角到右下角的最短路径长度是多少呢?
    在这里插入图片描述

    我们先看看,这个问题是否符合“一个模型”?

    从(0, 0)直到(n-1, n-1),总共要走 2*(n-1)步,也就是对应着 2*(n-1)个阶段。每个阶段都有向右走或者向下走两种决策,并且每个阶段都会对应一个状态集合。

    我们把状态定义为 min_dis(i, j),其中 i 表示行,j 表示列。 min_dis 的值表示从(0, 0)到达(i, j)的最短路径长度。所以,这个问题是一个多阶段决策最优解的问题,符合动态规划的模型。
    在这里插入图片描述

    再来看,这个问题是否符合“三个特征”?

    我们可以用回溯算法来解决这个问题。如果你自己写一下代码,画一下递归树,就会发现,递归树中有重复的节点。重复的节点表示,从左上角节点对应的位置,有多种路线,这也能说明这个问题中存在重复子问题。
    在这里插入图片描述

    如果我们走到(i, j)这个位置,我们只能通过(i-1, j),(i, j-1)这两个位置移过来,也就是说,我们想要计算(i, j)位置对应的状态,只需要关心(i-1, j),(i, j-1)这两个位置的状态,并不关心棋子是通过什么样的路线到达这两个位置的。而且,我们仅仅允许往下和往右移动,不允许后退,所以,前面阶段的状态确定之后,不会被后面阶段的决策所改变。所以这个问题,是符合“无后效性”的。

    刚刚定义状态的时候,我们把从起始位置(0, 0)到(i, j)的最小,记作 min_dis(i, j)。因为我们只能往右或者往下移动,所以,我们只有可能从(i-1, j),(i, j-1)两个位置到达(i, j)。也就是说,到达(i, j)的最短路径要么经过(i-1, j),要么经过(i, j-1),而且到达(i, j)的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是,min_dis(i, j)可以通过min_dis(i, j-1)和min_dis(i-1, j)两个状态推导出来。这就说明,这个问题符合“最优子结构”。

    • min_dis(i, j) = w[i][j] + min(min_dis(i, j-1), min_dis(i-1, j))

    两种动态规划解题思路的总结

    刚刚讲过,如何鉴别一个问题是否可以用动态规划来解决。现在,我再总结一下,动态规划解题的一般思路,让你面对动态规划问题的时候,能够有章可循,不至于束手无策。

    我个人觉得,解决动态规划问题,一般有两种思路。我把它们分别叫作,状态转移表法和状态转移方程法

    1、状态转移表法

    一般能用动态规划解决的问题,都可以使用回溯算法的暴力搜索解决。所以,当我们拿到问题的时候,我们可以先用简单的回溯算法解决,然后定义状态,每个状态表示一个节点,然后对应画出递归树。从递归树中,我们很容易可以看出来,是否存在重复子问题,以及重复子问题是如何产生的。以此来寻找规律,看是否能用动态规划解决。

    找到重复子问题之后,接下来,我们有两种处理 思路,第一种是直接用**回溯加“备忘录”**的方法,来避免重复子问题。从执行效率上来讲,这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法,状态转移表法。第一种思路,这里就不细讲了,可参考上节内容。我们重点来看下状态转移表法是如何工作的。

    我们先画一个状态表。状态表一般都是二维的,所以你可以把它想象成二维数组。其中,第个状态包含三个变量,行、列、数组值。我们根据决策的先后过程,从前往后,根据递推关系,分阶段填充表中的每个状态。最后,我们将这个递推填表的过程,翻译成代码,就是动态规划的代码了。

    尽管大部分表都是二维的,但是如果问题的状态比较复杂,需要很多变量来表示,那对应的状态可能就是高维的,比如三维、四维。那这个时候,我们就不适合用状态转移表法来解决了。一方面是因为高维状态转移表不好画图表示,另一方面因为人脑确实很不擅长思考高维的东西。

    现在,看一下,如何用状态转移表法,来解决那矩阵最短路径的问题?

    从起点到终点,我们有很多种不同的走法。我们可以穷举所有的走法,然后对比找出一个最短走法。不过如何才能不重复,不遗漏地穷举出所有的走法?我们可以用回溯算法这个比较有规律的穷举算法。

    回溯算法的代码实现如下

        private int minDist = Integer.MIN_VALUE; //  全局变量或者成员变量
        
        public void minDistBT(int i, int j, int dist, int[][] w, int n) {
        	// 到达了n-1, n-1这个位置
        	if (i == n && j == n) {
    			if (dist < minDist) {
    				minDist = dist;
    			}
    			return;
    		}
        	if (i < n) { // 往下走,更新 i=i+1, j=j
        		minDistBT(i + 1, j, dist+ w[i][j], w, n);
    		}
        	if (j < n) { // 往右走,更新 i=i, j=j+1
        		minDistBT(i, j = 1, dist+ w[i][j], w, n);
    		}
        }
    

    有了回溯代码之后,接下来, 我们要画出递归树,以此来寻找重复子问题。在递归树中,一个状态(也就是一个节点)包含三个变量(i, j, dist),其中 i, j 分别表示行列,dist表示从起点到达(i, j)的路径长度。从图中, 我们看出,尽管(i, j, dist)不存在重复的,但是(i, j)重复的有很多。对于(i, j)重复的节点,我们只需要选择 dist最小的节点,继续递归求解,其他节点就可以舍弃了。在这里插入图片描述

    既然存在重复子问题,我们就可以尝试看下,是否可以用动态规划来解决呢?

    我们画出一个二维状态表,表中的行、列表示棋子所在的位置,表中的值表示从起点到这个位置的最短路径。我们按照决策过程,通过不断状态递推演进,将状态表填好。为了方便代码的实现,我们按行来进行依次填充。在这里插入图片描述

    将上面的过程,翻译成代码,就是下面这个样子

        public int minDistDP(int[][] matrix, int n) {
        	int[][] states = new int[n][n];
        	int sum = 0;
        	for (int j = 0; j < n; j++) { // 初始化 states 的第一行数据
        		sum += matrix[0][j];
        		states[0][j] = sum;
    		}
        	sum = 0;
        	for (int i = 0; i < n; i++) { // 初始化 states 的第一列数据
        		sum += matrix[i][0];
        		states[i][0] = sum;
    		}
        	for (int i = 1; i < n; i++) {
    			for (int j = 1; j < n; j++) {
    				states[i][j] = matrix[i][j] + Math.min(states[i][j - 1], states[i - 1][j]);
    			}
    		}
        	return states[n - 1][n - 1];
        }
    

    2,状态转移方程法

    状态转移方程法有点类似递归的解题思路。我们需要分析,某个问题如何通过子问题来递归求解,了就是所谓的最优子结构。根据最优子结构,写出递归公式,也就是所谓的状态转移方程。有了状态转移方程。代码实现就非常简单了。一般情况下,我们有两种代码实现方法,一种是递归加“备忘录”,另一种是迭代递推

    状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程,那动态规划问题基本上就解决了一大半了,而翻译代码非常简单。但是很多动态规划问题的状态本身不好定义,状态转移方程也就不好想到。

    下面用递归加“备忘录”的方式,将状态转移方程翻译成代码,你可以看看。对于另一种实现方式,跟状态转移表法的代码实现是一样的,只是思路不同。

    	private int[][] matrix = { { 1, 3, 5, 9 }, { 2, 1, 3, 4 }, { 5, 2, 6, 7 }, { 6, 8, 4, 3 } };
    	
    	private int n = 4;
    	
    	private int[][] men = new int[4][4];
    	
    	private int minDist(int i, int j) { // 调用minDist(n-1, n-1);
    		if (i == 0 && j == 0) {
    			return matrix[0][0];
    		}
    		if (men[i][j] > 0) {
    			return men[i][j];
    		}
    		int minLeft = Integer.MAX_VALUE;
    		if (j -1 >= 0) {
    			minLeft = minDist(i, j - 1);
    		}
    		int minUp = Integer.MAX_VALUE;
    		if (i - 1 >= 0) {
    			minUp = minDist(i - 1, j);
    		}
    		
    		int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
    		
    		men[i][j] = currMinDist;
    		return currMinDist;
    	}
    

    两种动态规划解题思路到这里就讲完了。我强调一点,不是第个问题都同时适合这两种解题思路。有的问题可能用第一种思路更清晰,而有的问题可能用第二种思路更清晰,所以,人要结合具体的题目来看,到底选择哪种解题思路。

    四种算法思想比较分析

    到今天为止,我们已经学习了四种算法思想,贪心、分治、回溯和动态规划。今天的内容主要讲些理论知识,这里看下这四种算法之间有什么区别和联系。

    如果我们将这四种算法思想分一下类,那贪心、回溯、动态规划可以归为一类,而分治单独可以作为一类。因为它跟其它三个都不大一样。为什么这么说呢?前三个算法解决问题的模型,都可以抽象成我们今天讲的那个多阶段决策最优解模型,而分治算法解决的问题尽管大部分也是最优解问题,但是,大部分都不能抽象成多阶段决策模型。

    回溯算法是个“万金油”。基本上能用动态规划、贪心解决问题,我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况,然后对比得出最优解。不过,回溯算法的时间复杂度非常高,只能用来解决小规模数据问题。对于大规模数据的问题,用回溯算法解决的执行效率就很低了。

    尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决的问题,需要满足三个特征,最优子结构、后后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反。动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题。

    贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效,代码实现再加简洁。不过,它可以解决的问题也更加有限。它能解决的问题需要满足三个条件,最优子结构、无后效性和贪心选择性(这里我们不怎么强调重复子问题)。

    其中,最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是,通过局部最优的选择,能产生全局最优选择。每一个阶段,我们都选择当前看起来最优的决策,所有的阶段的决策完成之后,最终由些局部最优解构成全局最优解。

    展开全文
  • 1、最优子结构 最优子结构指的是,问题的优解包含子问题的优解。反过来说就是,我们可以通过子问题的优解,推导出问题的优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也...

    上一节,我通过两个非常的问题,向你展示了用动态规划问题的过程。今天主要讲一些理论知识。学完这节内容,可以帮你解决这几个问题:什么样的问题可以用动态规划来解决?解决动态规划问题的一般思路是什么?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系。


    “一个模型三个特征”理论的讲解

    动态规划作为一个非常成熟的算法思想,很多人对此做了非常全面的总结,我把这部分理论总结为“一个模型三个特征”。

    首先,“一个模型”指的是动态规划适合解决问题的模型。我把这个模型定义为“多阶段决策最优解模型”。

    具体来说,我们一般是用动态规划来解决最优问题。而解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应一组状态。然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。

    “三个特征”,分别是最优子结构、无后效性和重复子问题。这三个概念比较抽象,逐一解释一下。

    1、最优子结构

    最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也可以理解为,后面阶段的状态可以通过前面状态推导出来。

    2、无后效性

    无后效性,有两层含义,第一层含义是,在推导后面阶段状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。

    3、重复子问题

    这个概念,前面一节,已经多次提到。用一句话概括就是: 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。


    “一个模型三个特征”实例剖析

    “一个模型三个特征”这部分理论知识,比较抽象,你看了之后可能还是有点懵,有种似懂非懂的感觉,没关系,这个很正常。接下来,我结合一个具体的动态规划问题,来详细解释下。

    假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角,终止位置在右下角。我们将棋子从左上角移到右下角。每次只能向右或者向下移动一位。整个过程,会有多种不同的路径可以选择。我们把每条路径经过的数字加起来看作路径的长度。那从左上角到右下角的最短路径长度是多少呢?

    我们先看看,这个问题是否符合“一个模型”?

    从(0, 0)直到(n-1, n-1),总共要走 2*(n-1)步,也就是对应着 2*(n-1)个阶段。每个阶段都有向右走或者向下走两种决策,并且每个阶段都会对应一个状态集合。

    我们把状态定义为 min_dis(i, j),其中 i 表示行,j 表示列。 min_dis 的值表示从(0, 0)到达(i, j)的最短路径长度。所以,这个问题是一个多阶段决策最优解的问题,符合动态规划的模型。

    再来看,这个问题是否符合“三个特征”?

    我们可以用回溯算法来解决这个问题。如果你自己写一下代码,画一下递归树,就会发现,递归树中有重复的节点。重复的节点表示,从左上角节点对应的位置,有多种路线,这也能说明这个问题中存在重复子问题。

    如果我们走到(i, j)这个位置,我们只能通过(i-1, j),(i, j-1)这两个位置移过来,也就是说,我们想要计算(i, j)位置对应的状态,只需要关心(i-1, j),(i, j-1)这两个位置的状态,并不关心棋子是通过什么样的路线到达这两个位置的。而且,我们仅仅允许往下和往右移动,不允许后退,所以,前面阶段的状态确定之后,不会被后面阶段的决策所改变。所以这个问题,是符合“无后效性”的。

    刚刚定义状态的时候,我们把从起始位置(0, 0)到(i, j)的最小,记作 min_dis(i, j)。因为我们只能往右或者往下移动,所以,我们只有可能从(i-1, j),(i, j-1)两个位置到达(i, j)。也就是说,到达(i, j)的最短路径要么经过(i-1, j),要么经过(i, j-1),而且到达(i, j)的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是,min_dis(i, j)可以通过min_dis(i, j-1)和min_dis(i-1, j)两个状态推导出来。这就说明,这个问题符合“最优子结构”。

    min_dis(i, j) = w[i][j] + min(min_dis(i, j-1), min_dis(i-1, j))


    两种动态规划解题思路的总结

    刚刚讲过,如何鉴别一个问题是否可以用动态规划来解决。现在,我再总结一下,动态规划解题的一般思路,让你面对动态规划问题的时候,能够有章可循,不至于束手无策。

    我个人觉得,解决动态规划问题,一般有两种思路。我把它们分别叫作,状态转移表法和状态转移方程法

    1、状态转移表法

    一般能用动态规划解决的问题,都可以使用回溯算法的暴力搜索解决。所以,当我们拿到问题的时候,我们可以先用简单的回溯算法解决,然后定义状态,每个状态表示一个节点,然后对应画出递归树。从递归树中,我们很容易可以看出来,是否存在重复子问题,以及重复子问题是如何产生的。以此来寻找规律,看是否能用动态规划解决

    找到重复子问题之后,接下来,我们有两种处理 思路,第一种是直接用**回溯加“备忘录”**的方法,来避免重复子问题。从执行效率上来讲,这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法,状态转移表法。第一种思路,这里就不细讲了,可参考上节内容。我们重点来看下状态转移表法是如何工作的

    我们先画一个状态表。状态表一般都是二维的,所以你可以把它想象成二维数组。其中,第个状态包含三个变量,行、列、数组值。我们根据决策的先后过程,从前往后,根据递推关系,分阶段填充表中的每个状态。最后,我们将这个递推填表的过程,翻译成代码,就是动态规划的代码了。

    尽管大部分表都是二维的,但是如果问题的状态比较复杂,需要很多变量来表示,那对应的状态可能就是高维的,比如三维、四维。那这个时候,我们就不适合用状态转移表法来解决了。一方面是因为高维状态转移表不好画图表示,另一方面因为人脑确实很不擅长思考高维的东西。

    现在,看一下,如何用状态转移表法,来解决那矩阵最短路径的问题?

    从起点到终点,我们有很多种不同的走法。我们可以穷举所有的走法,然后对比找出一个最短走法。不过如何才能不重复,不遗漏地穷举出所有的走法?我们可以用回溯算法这个比较有规律的穷举算法。

    有了回溯代码之后,接下来, 我们要画出递归树,以此来寻找重复子问题。在递归树中,一个状态(也就是一个节点)包含三个变量(i, j, dist),其中 i, j 分别表示行列,dist表示从起点到达(i, j)的路径长度。从图中, 我们看出,尽管(i, j, dist)不存在重复的,但是(i, j)重复的有很多。对于(i, j)重复的节点,我们只需要选择 dist最小的节点,继续递归求解,其他节点就可以舍弃了

    既然存在重复子问题,我们就可以尝试看下,是否可以用动态规划来解决呢?

    我们画出一个二维状态表,表中的行、列表示棋子所在的位置,表中的值表示从起点到这个位置的最短路径。我们按照决策过程,通过不断状态递推演进,将状态表填好。为了方便代码的实现,我们按行来进行依次填充。


    2,状态转移方程法

    状态转移方程法有点类似递归的解题思路。我们需要分析,某个问题如何通过子问题来递归求解,也就是所谓的最优子结构。根据最优子结构,写出递归公式,也就是所谓的状态转移方程。有了状态转移方程,代码实现就非常简单了。一般情况下,我们有两种代码实现方法,一种是递归加“备忘录”,另一种是迭代递推

    我们还是拿刚才的例子来举例。最优子结构前面已经分析过了,你可以回过头去再看下。为了方便你查看,我把状态转移方程放到这里。

    min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
     

    这里我强调一下,状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程,那动态规划问题基本上就解决一大半了,而翻译成代码非常简单。但是很多动态规划问题的状态本身就不好定义,状态转移方程也就更不好想到

    下面我用递归加“备忘录”的方式,将状态转移方程翻译成来代码,你可以看看。对于另一种实现方式,跟状态转移表法的代码实现是一样的,只是思路不同。

    两种动态规划解题思路到这里就讲完了。我要强调一点,不是每个问题都同时适合这两种解题思路。有的问题可能用第一种思路更清晰,而有的问题可能用第二种思路更清晰,所以,你要结合具体的题目来看,到底选择用哪种解题思路


    四种算法思想比较分析

    到今天为止,我们已经学习了四种算法思想,贪心、分治、回溯和动态规划。今天的内容主要讲些理论知识,我正好一块儿也分析一下这四种算法,看看它们之间有什么区别和联系。

    如果我们将这四种算法思想分一下类,那贪心、回溯、动态规划可以归为一类,而分治单独可以作为一类,因为它跟其他三个都不大一样。为什么这么说呢?前三个算法解决问题的模型,都可以抽象成我们今天讲的那个多阶段决策最优解模型,而分治算法解决的问题尽管大部分也是最优解问题,但是,大部分都不能抽象成多阶段决策模型。

    回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题,我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况,然后对比得到最优解。不过,回溯算法的时间复杂度非常高,是指数级别的,只能用来解决小规模数据的问题。对于大规模数据的问题,用回溯算法解决的执行效率就很低了。

    尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决的问题,需要满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反,动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题

    贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效,代码实现也更加简洁。不过,它可以解决的问题也更加有限。它能解决的问题需要满足三个条件,最优子结构、无后效性和贪心选择性(这里我们不怎么强调重复子问题)。

    其中,最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是,通过局部最优的选择,能产生全局的最优选择。每一个阶段,我们都选择当前看起来最优的决策,所有阶段的决策完成之后,最终由这些局部最优解构成全局最优解。


    内容小结

    今天的内容到此就讲完了,我带你来复习一下。

    我首先讲了什么样的问题适合用动态规划解决。这些问题可以总结概括为“一个模型三个特征”。其中,“一个模型”指的是,问题可以抽象成分阶段决策最优解模型。“三个特征”指的是最优子节、无后效性和重复子问题。

    然后,我讲了两种动态规划的解题思路。它们分别是状态转移表法和状态转移方程法。其中,状态转移表法解题思路大致可以概括为,回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。状态转移方程法的大致思路可以概括为,找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码

    最后,我们对比了之前讲过的四种算法思想。贪心、回溯、动态规划可以解决的问题模型类似,都可以抽象成多阶段决策最优解模型。尽管分治算法也能解决最优问题,但是大部分问题的背景都不适合抽象成多阶段决策模型。

    今天的内容比较偏理论,可能会不好理解。很多理论知识的学习,单纯的填鸭式讲给你听,实际上效果并不好。要想真的把这些理论知识理解透,化为己用,还是需要你自己多思考,多练习。等你做了足够多的题目之后,自然就能自己悟出一些东西,这样再回过头来看理论,就会非常容易看懂。

    所以,在今天的内容中,如果有哪些地方你还不能理解,那也没关系,先放一放。下一节,我会运用今天讲到的理论,再解决几个动态规划的问题。等你学完下一节,可以再回过头来看下今天的理论知识,可能就会有一种顿悟的感觉。

    展开全文
  • 贪心算法的设计思想: 贪心选择的概念:它所做出的每一个选择都是当前状态下局部的最好选择,即贪心选择。...(2)最优子结构性质:当一个问题的优解包含其子问题的优解时,称此问题具有最优子结构性质。 ...
  • 动态规划原理

    2016-04-25 11:29:00
    某个问题是否适用动态规划方法,观察其是否具有最优子结构性质是一个好的线索(具有最优子结构性质也可能意味着适用贪心策略)。实际上,发掘最优子结构性质遵循如下的通用模式: 证明问题优解的第一个部分是...
  • 动态规划思想的几个问题

    千次阅读 2014-06-04 22:03:04
    1.优子结构的概念,并从反面举例“哪些case不具备优子结构”;    动态规划只能应用于有优子结构的问题。...如果问题的优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足优化
  • 动态规划算法的基本要素为:最优子结构性质与重叠子问题性质 1)算法分析中,记号O表示渐进上界,记号表示渐进下界, 记号表示紧渐进界。 2)回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。 3...
  • 动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划只能应用于有优子结构的问题。优子结构的意思是局部优解能决定全局优解(对有些问题这个要求...
  • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题优解更好的解,从而导致矛盾。 利用问题的最优子结构性质...
  • 贪心算法部分知识点

    2019-03-13 22:37:17
    贪心算法 概念:简单来说,贪心算法就是贪心,在求解的时候步步贪心,步步求得优解,直至结束时求得想要的优解...当一个问题的优解包含其子问题的优解时,称此问题具有最优子结构性质。问题的最优子结构性质...
  • 算法设计与分析第四章复习 第四章 贪心算法 一、贪心算法的基本...当一个问题的优解包含其子问题的优解时,称此问题具有最优子结构性质。 二、活动安排问题 各活动的起始时间和结束时间存储于数组s和f中,且按结
  • 1、数据结构与算法 1.1、算法特性 正确性 健壮性 可理解性 抽象分级 高效性(时间复杂度,空间复杂度) 1.2、算法的描述方法 ...最短路径问题(单源点最短路径问题、多段图最短路径问题、多源点
  • 数据结构与算法数据结构定义研究对象数据的逻辑结构数据的物理结构数据存储结构常用的数据结构数组(Array)栈( Stack)队列(Queue)链表( Linked List)树( Tree)图(Graph)堆(Heap)散列表(Hash)常用算法算法特征有穷性...
  • 贪心_算法

    2021-08-15 16:56:27
    基本概念: 贪心的本质:选择每⼀阶段中的局部最优,从⽽达到全局的最优。...当一个问题的优解包含其子问题的优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪
  • (使用动态规划的分析思路:证明原问题具有最优子结构性质,证明原问题的优解可以由子问题的优解构造而成) (动态规划的耗时:递归式求解中,每次有i种选择,每种选择产生m个子问题,再考虑外层循环则计算量较...
  • 贪心算法与动态规划的区别

    万次阅读 多人点赞 2018-05-21 23:17:50
    基本要素:最优子结构性质和贪心选择性质。 最优子结构性质 问题的整体优解中包含子问题的优解 贪心选择性质 l整体的优解可通过一...
  • 动态规划

    2018-12-17 15:37:15
    记录一下动态规划的学习 ...如果一个问题的解结构包含其子问题的优解,就称此问题具有最优子结构性质。某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个很好的线索。 2、边界 例如斐波那契数...
  • 淮海工学院计算机工程学院 实验报告书 课程名 算法分析与设计 题 目 实验3 贪心算法 哈夫曼...2掌握最优子结构性质的证明方法 3掌握贪心法的设计思想并能熟练运用 4证明哈夫曼树满足最优子结构性质 5设计贪心算法求解哈
  • DP(动态规划,dynamic programming). 将一个问题拆成几个子问题,...大问题的优解可以由小问题的优解推出,这个性质叫做“最优子结构性质”。 能将大问题拆成几个小问题,且满足无后效性、最优子结构性质...
  • 贪心算法

    2019-10-24 10:49:29
    贪心算法 基本思想:贪心算法并不从整体最优上加以考虑,它所做的选择只是在某种意义上的局部优解。 基本要素:最优子结构性质和贪心选择性质。 ...
  • 一:概念介绍 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。形象点,如下图,假如有4个城镇A,B,C,D,它们之间有道路连通,且有长度。...1)最短路径的最优子结构性质  该性质描述为:如果
  • Algorithm --贪心算法

    2019-04-13 16:44:17
    一、概念 原理:一种启发式策略,在每个决策点作出在当时看来最佳的选择,即总是遵循某种规则,做出局部最优的选择...②优子结构:如果一个问题的优解包含其子问题的优解,则称此问题具有最优子结构性质; 解...
  • 【专题】贪心算法

    2016-11-19 17:44:23
    如果问题的优解由相关子问题的优解组合而成,并且这些子问题可以独立求解,那么称这种问题满足最优子结构性质。 贪心算法的设计步骤摘自算法导论: 1.将优化问题转化为这样的形式:对其做出一次选择后,只...
  • 线性规划、动态规划等几个概念

    万次阅读 2015-03-16 11:52:50
    线性规划: 在数学中,线性规划(Linear Programming,简称LP)问题是目标函数和约束条件都是线性的优化问题。... 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往
  • 遇到的一些算法概念

    2019-04-02 10:21:00
    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解; 4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子...
  • 分治法: 基本思想: 将问题分解成多个子问题,并允许不断分解,使规模越来越小,最终...当一个问题的优解包含其子问题的优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心
  • 最优子结构 基本思想 贪婪法求解步骤 示例 例 1寻找最大值 例2图的最小生成树的问题贪心算法概述关键: 问题分解。 在寻找优解时候,有很多常用的办法,比如说:贪心,分治,回溯,动态规划等等。这些思想有各自...
  • 动态规划题型总结

    2017-07-31 18:41:01
    (1)优子结构:如果问题的优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足优化原理)。意思就是,总问题包含很多个子问题,而这些子问题的解也是最优的。 (2)重叠子问题:子...
  • 以下是在编程面试中排名前10的算法相关的概念,我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力,因此这份列表只是作为一个介绍。本文将从Java的角度看问题,包含下面的这些概念: 1....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,619
精华内容 1,047
关键字:

最优子结构性质的概念