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

什么是动态规划法

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

与贪心法的异同

相同

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

不同

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

与分治法的异同

相同

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

不同

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

最优子结构

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

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

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

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

SimRank协同过滤推荐算法

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

37610
来自专栏机器之心

学界 | 减少模型半数内存用量:百度&英伟达提出混合精度训练法

机器之心编译 选自:arXiv 参与:李泽南、蒋思源 ? 深度学习的模型正在变得越来越复杂,所需要的计算资源也越来越多,在开发更加强大的硬件的同时,很多人也在致...

35690
来自专栏量子位

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

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

30240
来自专栏新智元

CMU:深度学习自然语言处理,神经机器翻译与 seq2seq 模型汇总,6 大类型附部署技巧

【新智元导读】CMU 语言技术研究所助理教授 Graham Neubig 将有关神经机器翻译和 seq2seq 各种模型的概要、重点以及部署技巧整理为一篇长达6...

38050
来自专栏机器之心

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

20560
来自专栏机器之心

专访 | 监管机器翻译质量?且看阿里如何搭建翻译质量评估模型

阿里机器翻译团队在本次比赛中,参加了英语到德语和德语到英语两个语向的句子级别和词级别的七项质量评估任务,收获了六项世界冠军。其中,德语到英语的统计机器翻译评估任...

9510
来自专栏机器之心

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

44950
来自专栏AI科技评论

深度学习鼻祖Geoffrey Hinton带你入门机器学习(36页干货PPT)

雷锋网注:Geoffrey Everest Hinton(杰弗里·埃弗里斯特·辛顿 )是一位英国出生的计算机学家和心理学家,以其在神经网络方面的贡献闻名。辛顿是...

1K40
来自专栏新智元

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

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

22220

扫码关注云+社区

领取腾讯云代金券