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

什么是动态规划法

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

与贪心法的异同

相同

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

不同

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

与分治法的异同

相同

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

不同

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

最优子结构

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WD学习记录

机器学习 学习笔记(9)支持向量机

函数间隔,对于给定的训练数据集T和超平面(w,b),定义超平面(w,b)关于样本点(xi,yi)的函数间隔为:

982
来自专栏梦里茶室

西瓜书概念整理(chapter 1-2)熟悉机器学习术语

括号表示概念出现的其他页码, 如有兴趣协同整理,请到issue中认领章节 完整版见我的github:ahangchen 觉得还不错的话可以点个star ^_^ ...

29110
来自专栏和蔼的张星的图像处理专栏

2.霍夫变换

霍夫变换是检测直线或者圆的一种比较简单的方法。霍夫变换检测直线是比较简单的,做完以后是一个二维平面上的许多曲线,通过统计平面上交点的个数,就可以得出哪些点事处于...

873
来自专栏数据结构与算法

圆的反演变换

挺神奇的东西,网上没有多少资料,我也不是太懂,代码什么的都没写过,那就抄一下百度百科吧

1072

如何在Python中规范化和标准化时间序列数据

如果您的时间序列数据具有连续的尺度或分布,则在某些机器学习算法将获得更好的性能。

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

(数据科学学习手札40)tensorflow实现LSTM时间序列预测

  上一篇中我们较为详细地铺垫了关于RNN及其变种LSTM的一些基本知识,也提到了LSTM在时间序列预测上优越的性能,本篇就将对如何利用tensorflow,在...

2654
来自专栏kevindroid

mahout学习之聚类(1)——向量的引入与距离测度

1404
来自专栏算法channel

机器学习|聚类算法之DBSCAN

DBSCAN,全称:Density-Based Spatial Clustering of Applications with Noise,是一个比较有代表性的...

3299
来自专栏烂笔头

常用样本相似性和距离度量方法

目录[-] 数据挖掘中经常需要度量样本的相似度或距离,来评价样本间的相似性。特征数据不同,度量方法也不相同。 欧式距离 欧式距离(Euclidean ...

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

反向传播神经网络极简入门

我一直在找一份简明的神经网络入门,然而在中文圈里并没有找到。直到我看到了这份162行的Python实现,以及对应的油管视频之后,我才觉得这就是我需要的极简入门资...

34215

扫描关注云+社区