动态规划算法

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

基本思想原理

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

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

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

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

适用解决问题

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

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

求解步骤

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(五)——奇异值分解实现推荐算法

一、奇异值分解简介         奇异值分解简称SVD(singular value decomposition),可以理解为:将一个比较复杂的矩阵用更小更简...

19910
来自专栏大数据

数据挖掘干货总结(一)-NLP基础

本文共计1463字,预计阅读时长八分钟 NLP-基础和中文分词 一、本质 NLP (Natural Language Processing)自然语言处理是一门研...

2038
来自专栏贾志刚-OpenCV学堂

图形图像算法中必须要了解的设计模式(1)

随着信息的多元化,信息的概念不仅仅指的是文字,它还包含图片、声音、视频等其它丰富的信息。文字信息越来越多地被图片、声音、视频信息所替代,而视频又是由一针一针的图...

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

详解机器学习之感知机理论与实践

阅读大概需要5分钟 上期回顾 详解机器学习之the Learning Problem 导读 本章讲的是让他机器学习说yes/no,目录分为: 感知机假设集合 ...

35012
来自专栏开心的学习之路

基于协同过滤的推荐引擎(理论部分)

记得原来和朋友猜测过网易云的推荐是怎么实现的,大概的猜测有两种:一种是看你听过的和收藏过的音乐,再看和你一样听过这些音乐的人他们喜欢听什么音乐,把他喜欢的你没听...

3249
来自专栏AI2ML人工智能to机器学习

变分の美

变分法(Variational method)已经成为微积分后主流的分析工具, 在物理和应用数学有着极大的功能。 变分法的诞生起源于最强大的数学家家族两个兄弟之...

761
来自专栏AI科技大本营的专栏

技术详解 | 如何用GAN实现阴影检测和阴影去除?

作者 | 江亦凡 最近两天刚看到的论文,写一篇文章当做笔记,论文原文取自https://arxiv.org/abs/1712.02478 继去年底Phillip...

3355
来自专栏懒人开发

(4.7)James Stewart Calculus 5th Edition:Optimization Problems

根据下图,可以得到大体表达式: 已知 2x + y = 2400 求 A = xy = ? 的最大值

583
来自专栏数据科学学习手札

(数据科学学习手札13)K-medoids聚类算法原理简介&Python与R的实现

前几篇我们较为详细地介绍了K-means聚类法的实现方法和具体实战,这种方法虽然快速高效,是大规模数据聚类分析中首选的方法,但是它也有一些短板,比如在数据集中有...

3627
来自专栏wym

opencv学习笔记 python实现 图像梯度与图像边缘

        图像梯度即求导数,导数能反映出图像变化最大的地方,图像变化最大的地方也就是图像的边缘。

852

扫码关注云+社区