动态规划法(一)——概述

什么是动态规划法

动态规划法也是用于求解最优化问题,也采用分步决策的策略,将一个大问题划分成若干个较小的同类子问题,根据子问题的解,自底向上,得出整个问题的解。

与贪心法的异同

相同

  1. 都是用于求解最优化问题;
  2. 都采用分步决策,计算出每一步的最优解。

不同

  1. 贪心法的每一步决策依赖于『最优量度标准』,不依赖于子问题的解和尚未作出的选择;
  2. 动态规划法每一步决策依赖于子问题的解,无需最优量度标准。

与分治法的异同

相同

  1. 都将问题话分成若干个规模较小的同类型子问题。

不同

  1. 分治法会有重叠子问题的现象,对于一些子问题会重复计算,而动态规划法能避免重叠子问题现象。

最优子结构

动态规划法具有最优子结构特性。 最优子结构特性:一个问题的最优解包含其子问题的最优解。 当一个问题具有最优子结构特性时,在构造该问题最优解的过程中,只需考虑每一个子问题的最优解。因为每个子问题的最优解构成了该问题的最优解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏量子位

干货分享 | 云脑科技核心算法工程师详解时间序列(附PPT)

云脑科技机器学习训练营以讲解时间序列收尾,详细解说了时间序列的传统模型、进阶模型、神经网络模型,量子位作为合作媒体为大家带来本期干货整理。 内容简介 主讲人:徐...

2824
来自专栏机器之心

学界 | 对比对齐模型:神经机器翻译中的注意力到底在注意什么

3765
来自专栏企鹅号快讯

一文读懂机器学习概率图模型

来源:机器之心 本文长度为10085字,建议阅读15分钟 本文结合基础应用示例系统性的为你讲解概率图模型。 概率图模型是人工智能领域内一大主要研究方向。近日,数...

2497
来自专栏新智元

NLP重磅!谷歌、Facebook新研究:2.26亿合成数据训练神经机器翻译创最优!

机器翻译依赖于大型平行语料库,即源语和目的语中成对句子的数据集。但是,双语语料是十分有限的,而单语语料更容易获得。传统上,单语语料被用于训练语言模型,大大提高了...

1012
来自专栏IT派

读懂概率图模型:你需要从基本概念和参数估计开始

概率图模型是人工智能领域内一大主要研究方向。近日,Statsbot 团队邀请数据科学家 Prasoon Goyal 在其博客上分两部分发表了一篇有关概率图模型的...

4054
来自专栏机器之心

学界 | FAIR新一代无监督机器翻译:模型更简洁,性能更优

1636
来自专栏数据派THU

一文读懂机器学习概率图模型(附示例和学习资源)

来源:机器之心 本文长度为10085字,建议阅读15分钟 本文结合基础应用示例系统性的为你讲解概率图模型。 概率图模型是人工智能领域内一大主要研究方向。近日,数...

9889
来自专栏人工智能LeadAI

学习资料参考:从深度学习到自然语言处理

注意:本文已经更新,新版结合深度学习简介和发展历程,给出了更详尽的学习资料参考。新版链接:深度学习简介与学习资料参考(http://peteryuan.net/...

3708
来自专栏机器学习算法原理与实践

SimRank协同过滤推荐算法

    在协同过滤推荐算法总结中,我们讲到了用图模型做协同过滤的方法,包括SimRank系列算法和马尔科夫链系列算法。现在我们就对SimRank算法在推荐系统的...

2231
来自专栏崔庆才的专栏

干货 | 给妹纸的深度学习教学——从这里出发

或许你第一个想弄明白的问题是人工智能(AI),机器学习(ML),深度学习(DL)三者的区别和联系,下图清晰明了地告诉你。 ? 1. 什么是机器学习 从小学开始...

45411

扫码关注云+社区