动态规划算法

动态规划过程:每一次决策依赖于当前的状态,即下一状态的产生取决于当前状态。一个决策序列就是在变化的状态中产生的,这种多阶段最优化问题的求解过程就是动态规则过程。

基本思想原理

与分而治之原理类似,将待求解的问题划分成若干个子问题(阶段)求解,顺序求解各个子问题(阶段),前一子问题(阶段)为后一子问题(阶段)的求解提供有用的信息。通过各个子问题(阶段)的求解,依次递进,最终得到初始问题的解。一般情况下,能够通过动态规划求解的问题也可通过递归求解。

动态规划求解的问题多数有重叠子问题的特点,为了减少重复计算,对每个子问题只求解一次,将不同子问题(阶段)的解保存在数组中。

与分而治之的区别:分而治之得到的若干子问题(阶段)一般彼此独立,各个子问题(阶段)之间没有顺序要求。而动态规划中各子问题(阶段)求解有顺序要求,具有重叠子问题(阶段),后一子问题(阶段)求解取决于前一子问题(阶段)的解。

与递归区别:与递归求解区别不大,都是划分成各个子问题(阶段),后一子问题(阶段)取决于前一子问题(阶段),但递归需要反复求解同一个子问题(阶段),相较于动态规划做了很多重复性工作。

适用解决问题

采用动态规划求解的问题一般具有如下性质:

  1. 最优化原理:求解问题包含最优子结构,即,可由前一子问题(阶段)最优推导得出后一子问题(阶段)最优解,递进得到初始问题的最优解。
  2. 无后效性:某状态以后的过程不会影响以前的状态,只与当前状态有关。
  3. 有重叠子问题:子问题(阶段)之间不是独立的,一个子问题(阶段)的解在下一子问题(阶段)中被用到。(不是必需的条件,但是动态规划优于其他方法的基础)

求解步骤

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

支持向量机入门简介

我们会通过分享有用的图书馆和资源而不是用复杂的数学知识来带你入门 SVM 。

3669
来自专栏AI研习社

论文推荐 | 提升100倍速度的切片递归神经网络

RNN训练慢、训练困难的问题已经是老生常谈了,循环结构带来的跨越多个步骤时的梯度消失和难以并行的特点几乎被认为是不可克服的,人们也已经接受了“RNN就是这样的”...

802
来自专栏AI研习社

让深度学习帮你创作爵士乐

数学与音乐有着内在的联系。 用算法作曲的历史,可以追溯到计算机科学出现的初期。翻译模型可以把一张图片转译为音乐。这都是基于规则的:如果图片里有一条水平的线,就会...

3408
来自专栏机器之心

教程 | 22分钟直冲Kaggle竞赛第二名!一文教你做到

选自微软机器学习博客 机器之心编译 参与:陈韵竹、路雪 本文介绍了如何使用微软 DVSM、利用迁移学习技术在 20 多分钟时间内达到 Kaggle 猫狗识别竞赛...

4048
来自专栏AI科技评论

学界 | UC伯克利大学AI实验室用一张单色图像生成高质量3D几何结构

AI科技评论按:用图像来重建3D数字几何结构是计算机视觉领域一个非常核心的问题。这种技术在许多领域都有广泛的应用,例如电影制作、视频游戏的内容生成、虚拟现实和增...

3736
来自专栏极客慕白的成长之路

高度不平衡的数据的处理方法

1332
来自专栏人工智能头条

应用深度学习时需要思考的问题

1453

支持向量机简介

在Statsbot团队发布关于时间序列异常检测的帖子之后,许多读者要求我们向他们介绍支持向量机的方法。现在是向您介绍SVM(支持向量机)的时候了,而不用您辛苦的...

2107
来自专栏机器之心

入门 | 极致的优化:智能手机是如何处理大型神经网络的

1606
来自专栏大数据智能实战

基于tensorflow实现AI图片鉴黄(NSFW)

       yahoo开源了用于检测图片是否包含不适宜工作场所(NSFW)内容的深度神经网络项目https://github.com/yahoo/open_n...

6729

扫码关注云+社区