当前位置: 首页 > article >正文

【从零开始学习计算机科学】算法分析(三)动态规划 与 贪心算法

【从零开始学习计算机科学】算法分析(三)动态规划 与 贪心算法

    • 动态规划
      • 重叠子问题
    • 贪心算法

动态规划

动态规划通过组合子问题的解而解决整个问题的。相对动态规划,分治算法是指将问题划分为一些独立的子问题,递归的求解各个问题,然后合并子问题的解而得到原问题的解。例如归并排序,快速排序都是采用分治算法思想。而动态规划与此不同,动态规划适用于子问题不是独立的情况,也就是说各个子问题包含有公共的子问题。在这种情况下,用分治算法则会重复做不必要的工作。而采用动态规划算法对每个子问题只求解一次,将其结果存放到一张表中,以供后面的子问题参考,从而避免每次遇到各个子问题时重新计算答案。因此,我们可以得出动态规划与分治法之间的区别主要是,分治法是指将问题分成一些独立的子问题,递归的求解各子问题,而动态规划适用于这些子问题不是独立的情况,也就是各子问题包含公共子问题。

动态规划通常用于最优化问题(此类问题一般有很多可行解,我们希望从这些解中找出一个具有最优(最大或最小)值的解)。
动态规划算法的设计分为以下四个步骤:描述最优解的结构,递归定义最优解的值,按自低向上的方式计算最优解的值,由计算出的结果构造一个最优解。
动态规划的第一步是描述最优解的结构,即选择问题的在什么时候会出现最优解,通过分析子问题的最优解而达到整个问题的最优解。在第二步,递归定义最优解的值,根据第一步得到的最优解描述,将整个问题分成小问题,直到问题不可再分为止,层层选择最优,构成整个问题的最优解,给出最优解的递归公式。第三步根据第二步给的递归公式,采用自底向上的策略,计算每个问题的最优解,并将结果保存到辅助表中。第四步骤是根据第三步中的最优解,借助保存在表中的值&#


http://www.kler.cn/a/590145.html

相关文章:

  • STM32---FreeRTOS事件标志组
  • 数学建模:MATLAB循环神经网络
  • PostgreSQL教程(二)九大类型
  • 第27周JavaSpringboot git初识
  • 如何在Django中设置CSRF Token?
  • 【计算机网络】浏览器组成、工作原理、页面渲染流程...
  • 什么是 Fisher 信息矩阵
  • JDBC数据库连接池技术详解——从传统连接方式到高效连接管理
  • Android Dagger2 框架注入模块源码深度剖析(四)
  • matlab图论分析之指标计算(二)
  • CSS @media print 使用详解
  • Flutter_学习记录_状态管理之GetX
  • 通过物联网与可视化技术搭建的智慧工地管理云平台,java智慧工地源代码,企业级源码
  • OpenManus 架构的详细技术实现
  • 算法——图论——最短路径(多边权)
  • 优化VsCode终端样式
  • 【前端动态列表渲染:如何正确管理唯一标识符(Key)?】
  • 设计模式Python版 模板方法模式(下)
  • React封装axios请求方法
  • 新能源电站系统建设提速!麒麟信安操作系统驱动光伏风电双领域安全升级