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

什么是动态规划法

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

与贪心法的异同

相同

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

不同

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

与分治法的异同

相同

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

不同

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

最优子结构

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

强化学习(六)时序差分在线控制算法SARSA

    在强化学习(五)用时序差分法(TD)求解中,我们讨论了用时序差分来求解强化学习预测问题的方法,但是对控制算法的求解过程没有深入,本文我们就对时序差分的在...

572
来自专栏机器学习-数据挖掘

基于日志分析的母机故障定位 ——机器学习应用

随着腾讯云业务的扩大,母机数量越来越多。为减少人力并实现母机故障的自动化定位,本文尝试利用机器学习算法,通过对历史故障母机的日志数据学习,训练模型实现自动化分析...

2664
来自专栏新智元

谷歌发布 TensorFlow Fold,支持动态计算图,GPU 增速 100 倍

【新智元导读】谷歌官方博客最新发布TensorFlow Fold,通过为每个输入构建单独的计算图解决由于输入的大小和结构不同导致的问题。此外,通过动态批处理,实...

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

非均衡数据处理--如何评价?

在分类问题中, 常见的数据预处理包括: 数据缺失(Missing), 奇值处理(Outlier), 数据变换(Transformation), 特征选择(Fea...

631
来自专栏李强强的专栏

【SPA大赛】腾讯广告点击大赛:对stacking的一些基本介绍

这次给大家分享的是 stacking 的一些基本知识,希望对大家有帮助。现在比赛进入了白热化阶段,并且马上要切换决赛B榜了,很多队伍都开始想着融合模型进行提高,...

4791
来自专栏机器之心

深度 | 因果推理和监督学习的统一概念框架:两者并不是对立的

1425
来自专栏深度学习之tensorflow实战篇

泊松分布 二项分布 正态分布之间的联系

二项分布有两个参数,一个 n 表示试验次数,一个 p 表示一次试验成功概率。现在考虑一列二项分布,其中试验次数 n 无限增加,而 p 是 n 的函数。   1...

2827
来自专栏LET

谈谈我对投影的理解

1526
来自专栏AI科技评论

数据库领域即将迎来革命?Jeff Dean 带队用机器学习颠覆数据索引方法

AI 科技评论按:伴随着机器学习理论和技术的发展、以及机器学习作为一门学科有越来越多的人关注以及参与,机器学习的落地应用场景也越来越多、越来越多样化。这两年的热...

3235
来自专栏AI研习社

IBM高级研发工程师武维:如何分布式训练深度学习模型?| 分享总结

AI 研习社按:随着深度学习神经网络规模越来越大,训练一个深度神经网络(Deep Neural Networks, DNNs)往往需要几天甚至几周的时间。为了加...

2685

扫码关注云+社区