精华内容
下载资源
问答
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...

    1.序

    近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

    2.动态规划的基本概念[^1]

    在学习动态规划之前,先思考这样一个问题:什么是动态规划?为什么叫动态规划?
    当读者在试图探索这个问题的时候,不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的,应用于工程领域。
    动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

    所谓多阶段决策过程是指这样一类决策过程:它可以把一一个复杂问题按时间(或空间)分成若干个阶段,每个阶段都需要作出决策,
    以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何,不但与该阶段的经济效果有关,
    还影响以后各阶段的经济效果,可见这类多阶段决策问题是一个动态的问题,因此,处理的方法称为动态规划方法。然而,动态
    规划也可以处理一些本来与时间没有关系的静态模型,这只要在静态模型中人为地引入“时间”因素,分成时段,就可以把它看作
    是多阶段的动态模型,用动态规划方法去处理。
    

    简言之,多阶段决策过程是指这样的一类特殊的活动过程:问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。
    下面举例说明什么是多阶段决策问题。
    例1(最短路线问题)在线路网络图1中,从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离,为使总运费最少,必须找出一条由A至E总里程最短的路线。
    在这里插入图片描述

    图1

    为了找到由A至E的最短线路,可以将该问题分成A—B—C—D—E 4个阶段,在每个阶段都需要作出决策,即在A点需决策下一步到B1还是到B2或B3;同样,若到达第二阶段某个状态,比如B1 ,需决定走向C1还是C2 ;依次类推,可以看出:各个阶段的决策不同,由A至E的路线就不同,当从某个阶段的某个状态出发作出一个决策,则这个决策不仅影响到下一个阶段的距离,而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策,使这些决策序列所决定的一条路线对应的总路程最短。

    3.动态规划算法的基本思想[^2]

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
    在这里插入图片描述

    图2

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
    在这里插入图片描述

    图3

    4.动态规划的求解步骤[^2]

    a. 找出最优解的性质,并刻划其结构特征。
    b. 递归地定义最优值。
    c. 以自底向上的方式计算出最优值。
    d. 根据计算最优值时得到的信息,构造最优解

    5.动态规划算法的基本要素[^2]

    5.1 最优子结构

    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
    • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
    • 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

    注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)

    5.2 重叠子问题

    • 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
    • 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
    • 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      在这里插入图片描述
      图4

    6.一些经典的动态规划问题

    这部分待补充~
    笔者要充电了~

    参考文献
    [1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
    [2]引用自老师的课件

    展开全文
  • 动态规划算法的基本要素

    万次阅读 2016-10-08 22:09:05
    最优子结构性质和子问题重叠性质是该问题可用动态规划算法求解的基本要素: 1.最优子结构  当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划...

    最优子结构性质和子问题重叠性质是该问题可用动态规划算法求解的基本要素:

    1.最优子结构

           当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。

           在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

    2.重叠子问题

           可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要此子问题时,只要简单地用常数时间查看一下结果。通常,不同的子问题个数随问题的大小呈多项式增长。因此,用动态规划算法通常只需要多项式时间,从而获得较高的解题效率。

    展开全文
  • 动态规划算法求解0,1背包问题

    千次阅读 2015-05-11 21:14:05
    看看动态规划四个步骤:对于动态规划算法,我们必须明确两个基本要素,这两个要素对于在设计求解具体问题算法时,是否选择动态规划算法具有指导意义:

    首先我们来看看动态规划的四个步骤:

      1. 找出最优解的性质,并且刻画其结构特性;

      2. 递归的定义最优解;

      3. 以自底向上的方式刻画最优值;

      4. 根据计算最优值时候得到的信息,构造最优解

    其中改进的动态规划算法:备忘录法,是以自顶向下的方式刻画最优值,对于动态规划方法和备忘录方法,两者的使用情况如下:

        一般来讲,当一个问题的所有子问题都至少要解一次时,使用动态规划算法比使用备忘录方法好。此时,动态规划算法没有任何多余的计算。同时,对于许多问题,常常可以利用其规则的表格存取方式,减少动态规划算法的计算时间和空间需求。当子问题空间中的部分子问题可以不必求解时,使用备忘录方法则较为有利,因为从其控制结构可以看出,该方法只解那些确实需要求解的问题。

    对于动态规划算法,我们必须明确两个基本要素,这两个要素对于在设计求解具体问题的算法时,是否选择动态规划算法具有指导意义:

    1 算法有效性依赖于问题本身所具有的最优子结构性质:设计算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可以使用动态规划算法求解的重要线索

    在矩阵连乘积最优次序问题中注意到,若A1A2...An的最优完全加括号方式在Ak和Ak+1之间断开,则由此可以确定的子链A1A2A3...Ak和Ak+1Ak+2...An的完全加括号方式也最优,即该问题具有最优子结构性质。在分析该问题的最优子结构性质时候,所使用的方法具有普遍性。首先假设由原问题导出的子问题的借不是最优解,然后在设法说明在这个假设下可以构造出比原问题最优解更好的解,从而导致矛盾。

           在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归的从子问题的最优解逐渐构造出整个问题的最优解。算法考察的子问题的空间规模较小。例如在举证连乘积的最优计算次序问题中,子问题空间由矩阵链的所有不用的子链组成。所有不用的子链的个数为o(n*n),因而子问题的空间规模为o(n*n)

    2 可以用动态规划算法求解问题应该具备另一个基本要素是子问题的重叠性。在用递归算法自顶向下求解此问题时候,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题都只是求解一次,而后将其保存到一个表格中,当再次需要解此问题时,只是简单使用常数时间查看一下结果。通常,不同子问题个数随着问题大小呈多项式增长。因此使用动态规划算法通常只是需要多项式时间,从而获得较高的解题效率。

    下面是使用动态规划算法求解0,1背包问题的Java实现:

    package dynamic_planning;
    
    public class Package0_1 {
    
    	private int c;  //背包总容量
    	private int n;  //背包中物品数目
    	private int []v;  //背包中每个物品的价值,一定是一一对应的
    	private int []w;  //背包中每个物品的重量,一定是一一对应的
    	private int [][]m;  //动态规划求解时候所使用的空间
    	
    	public Package0_1(){
    		c=20;n=6;
    		v=new int[]{12,45,23,14,5,27};
    		w=new int[]{2,9,8,3,7,6};
    		m=new int[n][c];
    	}
    	
    	public Package0_1(int c,int n,int []v,int []w,int [][]m){
    		this.c=c;this.n=n;
    		this.v=v;this.w=w;
    		this.m=m;
    	}
    	
    	//自底向上求解子问题
    	public void knapsack(){
    		for(int i=0;i<n;i++)
    			m[i][0]=0;
    		for(int s=1;s<=n;s++){
    			for(int i=n-s;i>=0;i--){
    				for(int j=1;j<c;j++){
    					if(i==n-1){
    						if(j<w[i])
    							m[i][j]=0;
    						else if(j>=w[i])
    							m[i][j]=v[i];
    					}
    					else{
    						if(j<w[i])
    							m[i][j]=m[i+1][j];
    						else if(j>=w[i])
    							m[i][j]=m[i+1][j]>(m[i][j-w[i]]+v[i])?m[i+1][j]:(m[i][j-w[i]]+v[i]);
    					}
    				}
    			}
    		}
    	}
    	//循环求解0,1向量组,0代表相应位置不装入背包,1代表装入背包
    	public void traceBack(){
    		for(int k=1;k<=n;k++)
    			System.out.print(k+"  ");
    		System.out.println();
    		int j=c-1;
    		for(int i=0;i<n-1;i++){
    			if(m[i][j]==m[i+1][j])
    				System.out.print(0+"  ");
    			else{
    				System.out.print(1+"  ");
    				j-=w[i];
    			}
    		}
    		if(j>=w[n-1])
    			System.out.print(1);
    		else 
    			System.out.print(0);
    	}
    	
    	public static void main(String[] args) {
    		Package0_1 package0_1=new Package0_1();
    		package0_1.knapsack();
    		package0_1.traceBack();
    	}
    }
    
    
    
    


    展开全文
  • 先讲一个问题来了解动态规划算法的思想 矩阵连乘问题 问题描述:给定 n 个矩阵 { A1, A2, … , An } 其中相邻矩阵是可乘,求它们连乘积 A1, A2, … , An 完全加括号:以加括号形式,明确指明矩阵连乘计算...

    思想 & 基本要素

    先讲一个问题来了解动态规划算法的思想
    矩阵连乘问题
    问题描述:给定 n 个矩阵 { A1, A2, … , An } 其中相邻的矩阵是可乘的,求它们的连乘积 A1, A2, … , An
    完全加括号:以加括号的形式,明确指明矩阵连乘的计算顺序,记为 ( A1, A2, … , An )
    不同的完全加括号式对应不同的运算次数
    矩阵连乘问题即为寻找运算次数最小的完全加括号式
    在这里插入图片描述
    在这里插入图片描述
    穷举搜索法
    在这里插入图片描述

    再思考下列问题:
    分治算法的三个要点:子问题与原问题的性质相同,子问题的求解彼此独立,划分子问题的规模尽可能均衡
    若分解的子问题不是互相独立的?
    分治法的子问题如下图:
    分治法的子问题
    动态规划的子问题如下图:
    在这里插入图片描述
    重复计算导致复杂性急剧提高,甚至达到指数阶
    Catalan数列
    在这里插入图片描述
    指数阶
    在这里插入图片描述
    在这里插入图片描述
    求解中子问题存在大量的重复
    在这里插入图片描述
    实际上所有的子问题只有10个
    A1, A2, A3, A4, A1A2, A2A3, A3A4, A1A2A3, A2A3A4, A1A2A3A4

    动态规划的两个基本要素
    第一个要素:最优子结构性质

    1. 问题的最优解包含了子问题的最优解
    2. 原问题可以通过分解子问题来解决
      第二个要素:重叠子问题性质(如:爬楼梯问题、斐波那契数列)
      与分治法的主要区别:
    3. 直接递归求解子问题的复杂性往往是指数阶
    4. 子问题空间的规模通常是多项式阶
    5. 同一个子问题可能出现在多次问题分解中

    动态规划的求解过程
    递归 --> 保存 --> 自底向上 / 自顶向下

    矩阵连乘问题的求解
    在这里插入图片描述
    动态规划的复杂性为 O(n^3)

    备忘录法:自顶向下
    动态规划与备忘录

    1. 动态规划相当于迭代,需要分析子问题的结构,从最小的问题解起
    2. 备忘录相当于递归,直接从原问题出发,若未解,则向下递归调用
    3. 当所有子问题都至少需要求解一次时,动态规划较好
    4. 当子问题空间中的部分子问题不必求解时,备忘录较好

    最长公共子序列

    问题描述:求序列 X = { x1, x2, … , xm} 和序列 Y = {y1, y2, … , yn} 最长的公共子序列

    穷举法

    找出 X = { x1, x2, … , xm} 的所有子序列,逐个检查 X子序列是否也是 Y子序列,输出最长的一个公共子序列,子序列的数量为 O(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 的最长公共子序列

    重叠子问题性质

    递归关系式
    在这里插入图片描述

    动态规划求解

    在这里插入图片描述
    算法的复杂性为 O(mn)

    0-1背包问题

    问题描述:给定 n 个物品和一个背包。物品 i 的重量为 Wi ,价值为 Vi ,背包的容量为 c ,问如何选择物品,使得背包中物品的价值最大
    在这里插入图片描述

    动态规划法

    1、最优子结构
    设 { x1, x2, … , xn} 是背包的一种最优装法,考虑如下子问题:
    待装入物品 { 2, … , n} ,且背包容量为 c-W1X1
    假设这个子问题的最优解不是 { x2, … , xn},而是 { x’2, … , x’n},则原问题按 { x1, x‘2, … , x’n} 的装法,得到的总价值最高,与 { x1, x2, … , xn} 是最优装法的假设矛盾
    2、子问题构造
    已考察完后 n - i 个物品,剩余物品为 1, … , i ,剩余容量为 j
    设该子问题的最优解为 m[ i ][ j ],原问题为 m[ 0 ][ c ]
    3、递归关系式
    考察下一个物品 i是否装入,若 Wi > j,无法装入,否则,取装入时和不装入时价值的较大者
    在这里插入图片描述
    在这里插入图片描述
    算法的复杂性为 O(nc)

    小结

    1. 使用动态规划求解时,应先证明问题的最优子结构性质
    2. 构造子问题最优解之间的递归关系式仍是求解的重点和难点
    3. 子问题的数量通常是规模的多项式阶
    4. 绘制一维或二维 DP 表是动态规划的常用手段
    展开全文
  • 动态规划基本要素

    2021-04-26 16:07:55
    该问题可用动态规划算法求解的基本要素 1.最优子结构 当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。最优子结构性质提供了该问题的可用动态规划算法求解的重要线索。 动态规划,利用问题的...
  • 首先我们先代入问题来认识一下贪心算法涉及问题 找钱问题 给顾客找钱,希望找零钞票尽可能少,零钱种类和数量限定 找钱问题满足最优子结构 最快找零(贪心):为得到最小找零次数,每次最大程度低减少零额 ...
  • 两大性质 1.最优子结构 2.子问题重叠性质 最优子结构 定义 问题的最优解包含着其子问题的最优解。这种性质称为最优子结 构性质。 证明 首先假设由问题的最优解导出... 最优子结构是问题能用动态规划算法求解的前提 ...
  • 63 4.2 贪心算法的基本要素 贪心算法和动态规划算法都要求问题具有最优子结构性质这 是 2 类算法的一个共同点但是对于具有 最优子结构 的问题 应该选用贪心算法还是动态规划算法求解 ? 是否能用动态规划 算法求解的...
  • 动态规划的基本要素

    千次阅读 2019-07-04 13:37:48
    1.最优子结构 当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态... 可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用...
  • 贪心算法的基本要素

    千次阅读 多人点赞 2019-10-29 11:17:55
    贪心算法的基本要素3.1贪心选择性质3.2 最优子结构性质3.3 贪心算法与动态规划算法的差异4.贪心算法的基本步骤5.一些经典的贪心算法问题 1.前言 本文着重讨论可以用贪心算法求解的问题的一般特征。 对于一个具体...
  • 动态规划

    2020-06-20 16:39:21
    从一般意义上讲,问题所具备的这两个重要性质是该问题可用动态规划算法求解的基本要素。这对于在设计求解具体问题的算法时,是否选择动态规划算法具有指导意义。 1.1最优子结构 设计动态规划算法的第一步通常是刻画...
  • 一.动态规划算法的基本要素[^2] 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优...最优子结构是问题能用动态规划算法求解的前提。 注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的
  • 矩阵连乘——动态规划算法

    千次阅读 多人点赞 2019-07-25 11:26:21
    矩阵连乘——动态规划算法 目录 矩阵连乘——动态规划算法 预备知识 前言 ...步骤2:一个递归求解方案 ...算法的基本要素 1、最优子结构 2、重叠子问题 3、备忘录方法 闲聊时刻 预备知识 了解...
  • 动态规划算法例题及解析

    千次阅读 2013-12-15 21:05:46
    最优子结构性质:这是可用动态规划算法求解的前提条件 (2)  重叠子问题:子问题是否具有重叠性会影响到动态规划算法的效率   1.字符串转换 设A和AB是两个字符串,要用最少的字符操作,将字符串A转换为字符...
  • 动态规划算法: 一、算法思想: 将待求解的问题分解成若干个子问题,并存储子问题的解而避免计算重复的子问题,并由子问题的解得到原问题的解。...l动态规划算法的基本要素:最优子结构性质和重叠子问题。 ...
  • 动态规划算法解决0-1背包问题

    万次阅读 2016-04-30 21:44:25
    2.动态规划算法常以自底向上方式计算最优值,也就是说,从最小子问题开始向包含该子问题大问题方向求解,把每一次求解子问题解保存下来,以便提供给包含该小问题大问题使用,因此使用循环迭代方式计算...
  • 算法——动态规划

    2020-07-10 16:45:01
    动态规划基本概念思想基本要素最优子结构重叠性质基本步骤动态规划算法和备忘录法具体例子矩阵连乘问题题目描述:问题分析:抽象描述:算法:例子代码最大字段和问题定义算法分析:实现最长公共子序列问题定义:...
  • (3动态规划算法的基本要素:最优子结构性质和重叠子问题。最优子结构性质:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态(由上一次的决策产生)的最优决策。重叠子...
  • 二简答题 备忘录方法和动态规划算法相比有何异同简述之 简述回溯法解题的主要步骤 简述动态规划算法求解的基本要素 简述回溯法的基本思想 简要分析在递归算法中消除递归调用将递归算法转化为非递归算法的方法 简要...
  • 动态规划-基本思想

    2016-10-16 10:13:29
    ·掌握动态规划算法的基本要素 ·(1)最优子结构性质 ·(2)重叠子问题性质 ·掌握设计动态规划算法的步骤。 ·(1)找出最优解的性质,并刻划其结构特征。 ·(2)递归地定义最优值。 ·(3)以自底向上的方式...
  • 与分治法不同的是,适用于动态规划算法求解的问题,经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算很多次。如果我们能保存已解决子问题的答案,...
  • 文章目录什么是动态规划算法数字三角形经典递归解法 什么是动态规划算法 ...使用动态规划来求解的问题需要具备的基本要素包括: (1)重复子问题 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子
  • 1.动态规划的基本概念 其基本思想是将求带解决的问题分解成若干子问题,向求解子问题,再...4. 动态规划算法的步骤 找出最优解的性质,并刻画其结构特征 递归的定义最优质 以自底向上的方式计算得到最优质 根据计算最
  • 动态规划前言一、矩阵连乘问题用动态规划法解矩阵连乘的最优计算次序问题二、动态规划算法的基本要素1、最优子结构2、重叠子问题3、备忘录方法 前言         动态规划算法...
  • 根据期末老师划的重点复习…=_=!...(2)动态规划算法的基本要素 最优子结构性质 重叠子问题性质 (3)动态规划算法的基本步骤 1 找出最优解的性质,并刻画其结构特征 2 递归地定义最优值 3 以自底向上的...

空空如也

空空如也

1 2 3 4 5
收藏数 90
精华内容 36
关键字:

动态规划算法求解的基本要素