【算法分析与设计】动态规划(上)

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


一、学习要点

  理解动态规划算法的概念
  掌握动态规划算法的基本要素
  (1)最优子结构性质
  (2)重叠子问题性质

  掌握设计动态规划算法的步骤
  (1)找出最优解的性质,并刻划其结构特征
  (2)递归地定义最优值
  (3)以自底向上的方式计算出最优值
  (4)根据计算最优值时得到的信息,构造最优解

  通过应用范例学习动态规划算法设计策略。
  (1)矩阵连乘问题;
  (2)最长公共子序列;
  (3)最大子段和
  (4)凸多边形最优三角剖分;
  (5)多边形游戏;
  (6)图像压缩;
  (7)电路布线;
  (8)流水作业调度;
  (9)背包问题;
  (10)最优二叉搜索树。


二、算法总体思想

  动态规划算法与分治法类似,其 基本思想也是将待求解问题分解成若干个子问题
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  如果 能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构


三、动态规划基本步骤

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


四、矩阵连乘问题

  问题:给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2,…n-1。我们要计算出这 n个矩阵的连乘积
  因为矩阵乘积满足结合律,所以哪两个矩阵先乘哪两个后乘结果是一样的,但是 计算次数不一样,我们要找计算次数最小的那个次序!


4.1 完全加括号的矩阵连乘积

  完全加括号的矩阵连乘积可递归地定义为:
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  设有四个矩阵A,B,C,D;它们的维数分别是:
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  总共有五中完全加括号的方式:
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  16000, 10500, 36000, 87500, 34500

  给定n个矩阵:【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构其中Ai与Ai+1是可乘的,i=1,2,…,n-1。考察这n个矩阵的连乘积【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  由于 矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
  若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
  给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算 矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少


4.2 穷举法

  列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。
  算法复杂度分析
  对于n个矩阵的连乘积,设其不同的计算次序为P(n)。
  由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1…Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构


4.3 动态规划

  将矩阵连乘积AiAi+1…Aj简记为A[i:j],这里i≤j
  考察计算A[i:j]的最优计算次序。设 这个计算次序在矩阵
Ak和Ak+1之间将矩阵链断开
,i≤k<j,则其相应完全加括号方式为【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相乘的计算量。


4.3.1 分析最优解的结构

  特征:计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的
  矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质问题的最优子结构性质是该问题可用动态规划算法求解的显著特征


4.3.2 建立递归关系

  设计算A[i:j],1≤i≤j≤n,所需要的最少数乘次数m[i,j],则原问题的最优值为m[1,n]
  当i=j时,A[i:j]=Ai,因此,m[i,i]=0,i=1,2,…,n
  当i<j时,【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  可以递归地定义m[i,j]为:
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  (k的位置只有j-i种可能)


4.3.3 计算最优值

  对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此,不同子问题的个数最多只有【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  由此可见,在递归计算时,许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。
  用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  1.计算A1,A2,A3,A4,A5,A6
  2.计算(A1A2),(A2A3),(A3A4),(A4A5),(A5A6)
  3.计算(A1A2A3),…,(A4A5A6)
  4.计算A[1,4],A[2,5],A[3,6]
  5.计算A[1,5],A[2,6]
  6.计算A[1,6]


4.3.4 用动态规划法求最优解

void MatrixChain(int *p,int n,int **m,int **s)
{
        for (int i = 1; i <= n; i++) m[i][i] = 0;
        for (int r = 2; r <= n; r++)
           for (int i = 1; i <= n - r+1; i++) {
              int j=i+r-1;
              m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
              s[i][j] = i;
              for (int k = i+1; k < j; k++) {
                 int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                 if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}
              }
          }
}

【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构
  算法复杂度分析
  算法matrixChain的主要计算量取决于算法中对r,i和k的3重循环。循环体内的计算量为O(1),而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。
【算法分析与设计】动态规划(上),数据结构与算法,算法,动态规划,c++,数据结构


五、动态规划算法的基本要素

5.1 最优子结构

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

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


5.2 重叠子问题

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


5.3 备忘录方法

  备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。

int LookupChain(int i,int j)
{
       if (m[i][j] > 0) return m[i][j];
       if (i == j) return 0;
       int u = LookupChain(i,i) + LookupChain(i+1,j) + p[i-1]*p[i]*p[j];
       s[i][j] = i;
       for (int k = i+1; k < j; k++) {
         int t = LookupChain(i,k) + LookupChain(k+1,j) + p[i-1]*p[k]*p[j];
         if (t < u) { u = t; s[i][j] = k;}
         }
       m[i][j] = u;
       return u;
}

六、思考题:捡硬币问题

  现有n个硬币按顺序依次排列在你面前,可以看为一个数组coins[]={5,1,2,10,6,2},请在此中捡取若干个硬币,使得所取硬币累加值最大,捡取个数不限,但相邻两个硬币不得捡取,请设计相应算法,并输出累加值
  提示:硬币面值必须是正数,不能有负值。建立数组dp[i]存储选取前i个硬币的累加值文章来源地址https://www.toymoban.com/news/detail-717018.html

到了这里,关于【算法分析与设计】动态规划(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法 | 动态规划算法(Dynamic Programming)

    上一篇文末已经提到了记忆化搜索是动态规划(Dynamic Programming)的一种形式,是一种自顶向下(Top-Down)的思考方式,通常采用递归的编码形式;既然动态规划有自顶向下(Top-Down)的递归形式,自然想到对应的另外一种思考方式 自底向上( Bottom-Up ) ,也就是本篇要写的内

    2024年02月05日
    浏览(45)
  • Java数据结构与算法----动态规划(背包篇)

    1.1.算法思路 0/1背包是动态规划、背包问题中最经典的问题啦!它主要的问题是: 给定n种物品、这n种物品的重量分别是,价值分别是 ,而你有一个容量为C的背包,请问如何求出所能拿的最大价值呢? 对于动态规划,我们先需要找到一条推导公式,然后确定边界: 我们设

    2024年02月07日
    浏览(50)
  • 数据结构与算法:动态规划(Dynamic Programming)详解

    动态规划(Dynamic Programming,简称DP) 是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划经常被用于求解优化问题。 动态规划的核心思想是将复杂问题分解为更小的子问

    2024年04月25日
    浏览(48)
  • 【夜深人静学数据结构与算法 | 第十篇】动态规划

    目录 前言: 动态规划: 常见应用: 解题步骤:  动态规划的简化步骤: 案例: 509. 斐波那契数 - 力扣(LeetCode) 70. 爬楼梯 - 力扣(LeetCode) 62. 不同路径 - 力扣(LeetCode) 总结:         本文我们将为大家讲解一下动态规划的理论知识,并且会讲解几道力扣的经典例题。

    2024年02月11日
    浏览(53)
  • python数据结构与算法-动态规划(最长公共子序列)

    一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如:\\\"ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y,求X和Y长度最大的公共子字列。 例:X=\\\"ABBCBDE”Y=\\\"DBBCDB”LCS(XY)=\\\"BBCD\\\" 应用场景:字符串相似度比对 (1)问题思考 思考: 暴

    2024年02月08日
    浏览(52)
  • ​Python—数据结构与算法​---动态规划—DP算法(Dynamic Programing)

    目录 我们一路奋战, 不是为了改变世界, 而是为了不让世界改变我们。 动态规划——DP算法(Dynamic Programing) 一、🏔斐波那契数列(递归VS动态规划) 1、🐒斐波那契数列——递归实现(python语言)——自顶向下 2、🐒斐波那契数列——动态规划实现(python语言)——自底

    2024年02月10日
    浏览(39)
  • 【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

    Kadane\\\'s 算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。 算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。 以下是Kadane’s算

    2024年03月22日
    浏览(102)
  • 【零基础】学python数据结构与算法笔记14-动态规划

    学习python数据结构与算法,学习常用的算法, b站学习链接 动态规划在基因测序、基因比对、hmm 有应用场景。 从斐波那契数列看动态规划 练习: 使用递归和非递归的方法来求解斐波那契数列。 这种非递归求斐波那契数,可以看成是一个动态规划思想,每次都会把重复子问

    2023年04月09日
    浏览(45)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(95)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包