动态规划算法

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

基本思想原理

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

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

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

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

适用解决问题

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

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

求解步骤

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习思考者

DL开源框架Caffe | 模型微调 (finetune)的场景、问题、技巧以及解决方案

前言 什么是模型的微调?   使用别人训练好的网络模型进行训练,前提是必须和别人用同一个网络,因为参数是根据网络而来的。当然最后一层是可以修改的,因为我们...

4616
来自专栏深度学习自然语言处理

如何直观地解释 back propagation 算法?

BackPropagation算法是多层神经网络的训练中举足轻重的算法。 简单的理解,它的确就是复合函数的链式法则,但其在实际运算中的意义比链式法则要大的多。 ...

1052
来自专栏ATYUN订阅号

智能主题检测与无监督机器学习:识别颜色教程

介绍 人工智能学习通常由两种主要方法组成:监督学习和无监督的学习。监督学习包括使用现有的训练集,这种训练集由预先标记的分类数据列组成。机器学习算法会发现数据的...

4314
来自专栏大数据挖掘DT机器学习

R语言中的情感分析与机器学习

利用机器学习可以很方便的做情感分析。本篇文章将介绍在R语言中如何利用机器学习方法来做情感分析。在R语言中,由Timothy P.Jurka开发的情感分析以及更...

3543
来自专栏Coding迪斯尼

用Python从零开始设计数字图片识别神经网络--搭建基本架构

1154
来自专栏刘笑江的专栏

R 语言线性回归应用:拟合 iOS 录音波形图

1106
来自专栏机器学习原理

深度学习——RNN(2)双向RNN深度RNN几种变种

1.2K3
来自专栏磐创AI技术团队的专栏

使用Keras进行深度学习:(六)LSTM和双向LSTM讲解及实践

1324
来自专栏腾讯大数据的专栏

深度卷积神经网络 CNNs 的多 GPU 并行框架 及其在图像识别的应用

将深度卷积神经网络(Convolutional Neural Networks, 简称CNNs)用于图像识别在研究领域吸引着越来越多目光。由于卷积神经网...

2185
来自专栏深度学习那些事儿

浅谈深度学习中超参数调整策略

深度学习中,设计模型以及保证模型的正确性是首要需要考虑的。当模型设置完成时,理论上模型不存在问题,实现效果也通过计算可以复现出来。一切准备就绪后,那么接下来需要...

1565

扫码关注云+社区