动态规划算法秘籍

本文来自通俗易懂算法入门书《趣学算法》。

动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和莱斯特·福特一起提出了求解最短路径的Bellman-Ford 算法,该算法解决了Dijkstra算法不能处理负权值边的问题。

Dynamic Programming,这里的Programming不是编程的意思,而是指一种表格处理法。我们把每一步得到的子问题结果存储在表格里,每次遇到该子问题时不需要再求解一遍,只需要查询表格即可。

4.1.1 算法思想

动态规划也是一种分治思想,但与分治算法不同的是,分治算法是把原问题分解为若干子问题,自顶向下,求解各子问题,合并子问题的解从而得到原问题的解。动态规划也是把原问题分解为若干子问题,然后自底向上,先求解最小的子问题,把结果存储在表格中,在求解大的子问题时,直接从表格中查询小的子问题的解,避免重复计算,从而提高算法效率。

4.1.2 算法要素

什么问题可以使用动态规划呢?我们首先要分析问题是否具有以下两个性质:

(1) 最优子结构

最优子结构性质是指问题的最优解包含其子问题的最优解。最优子结构是使用动态规划的最基本条件,如果不具有最优子结构性质就不可以使用动态规划解决。

(2) 子问题重叠

子问题重叠是指在求解子问题的过程中,有大量的子问题是重复的,那么只需要求解一次,然后把结果存储在表中,以后使用时可以直接查询,不需要再次求解。子问题重叠不是使用动态规划的必要条件,但问题存在子问题重叠更能够充分彰显动态规划的优势。

什么问题可以使用动态规划呢?我们首先要分析问题是否具有以下两个性质:

(1) 最优子结构

最优子结构性质是指问题的最优解包含其子问题的最优解。最优子结构是使用动态规划的最基本条件,如果不具有最优子结构性质就不可以使用动态规划解决。

(2) 子问题重叠

子问题重叠是指在求解子问题的过程中,有大量的子问题是重复的,那么只需要求解一次,然后把结果存储在表中,以后使用时可以直接查询,不需要再次求解。子问题重叠不是使用动态规划的必要条件,但问题存在子问题重叠更能够充分彰显动态规划的优势。

4.1.1 解题秘籍

遇到一个实际问题,如何采用动态规划来解决呢?

(1) 分析最优解的结构特征。

(2) 建立最优值的递归式。

(3) 自底向上计算最优值,并记录。

(4) 构造最优解。

本章通过8个实例,讲解了动态规划的解题过程。动态规划求解最优化问题时需要考虑两个性质:最优子结构和子问题重叠,只要满足最优子结构性质就可以使用动态规划,如果还具有子问题重叠,则更能彰显动态规划的优势。判断可以使用动态规划后,就可以分析其最优子结构特征,找到原问题和子问题的关系,从而得到最优解递归式。然后按照最优解递归式自底向上求解,采用备忘机制(查表法)有效解决子问题重叠,重复的子问题不需要重复求解,只需查表即可。

动态规划的关键:

(1)最优子结构判定

a. 作出一个选择;

b. 假定已经知道了哪种选择是最优的;

例如矩阵连乘问题,我们假设已经知道在第k个矩阵加括号是最优的,即(AiAi+1…Ak)(Ak+1Ak+2…Aj)。

c. 最优选择后会产生哪些子问题;

例如矩阵连乘问题,我们作出最优选择后产生两个子问题:(AiAi+1…Ak),(Ak+1Ak+2…Aj)。

d. 证明原问题的最优解包含其子问题的最优解。

通常使用“剪切—粘贴”反证法。证明如果原问题的解是最优解,那么子问题的解也是最优解。反证:假定子问题的解不是最优解,那么就可以将它“剪切”掉,把最优解“粘贴”进去,从而得到一个比原问题最优解更优的解,这与前提原问题的解是最优解矛盾。得证。

例如:矩阵连乘问题,c=a+b+d,我们只需要证明如果c是最优的,则a和b一定是最优的(即原问题的最优解包含子问题的最优解)。

反证法:如果a不是最优的,(AiAi+1…Ak) 存在一个最优解aˊ,aˊ<a,那么,aˊ+b+d<c,这与假设c是最优的矛盾,因此如果c是最优的,则a一定是最优的。同理可证b也是最优的。因此如果c是最优的,则a和b一定是最优的。因此,矩阵连乘问题具有最优子结构性质。

(2)如何得到最优解递归式

a.分析原问题最优解和子问题最优解的关系;

例如矩阵连乘问题,我们假设已经知道在第k个矩阵加括号是最优的,即(AiAi+1…Ak)(Ak+1Ak+2…Aj)。作出最优选择后产生两个子问题:(AiAi+1…Ak),(Ak+1Ak+2…Aj)。如果我们用m[i][j]表示AiAi+1…Aj矩阵连乘的最优解,那么两个子问题:(AiAi+1…Ak),(Ak+1Ak+2…Aj)对应的最优解分别是m[i][k],m[k+1][j]。剩下的只需要考察(AiAi+1…Ak)和(Ak+1Ak+2…Aj)的结果矩阵相乘的乘法次数了。两个结果矩阵相乘的乘法次数是pi*pk+1*qj。

因此,原问题最优解和子问题最优解的关系:m[i][j]= m[i][k]+m[k+1][j]+ pi*pk+1*qj

b.考察有多少种选择;

实质上,我们并不知道哪种选择是最优的,因此就需要考察有多少种选择,然后从这些选择中找到最优解。

例如矩阵连乘问题,加括号的位置k(AiAi+1…Ak)(Ak+1Ak+2…Aj),k的取值范围是{i,i+1,…,j-1},即i≤k<j,那么我们考察每一种选择,找到最优值。

c.得到最优解递归式。

例如矩阵连乘问题,m[i][j]表示AiAi+1…Aj矩阵连乘的最优解,根据最优解和子问题最优解的关系,并考察所有的选择,找到最小值就是我们要的最优解。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

深度学习中的基础线代知识-初学者指南

导语:在经过一天之后,我们的活动人数已经达到40人了,感谢大家对小编的支持,同时在本文末附上前一天的众筹榜单。希望能跟小伙伴们度过愉快的6天! ? 上过 Jer...

34760
来自专栏机器之心

教程 | 无监督学习中的两个非概率模型:稀疏编码与自编码器

机器之心整理 作者:Ruslan Salakhutdinov 参与:Smith 「无监督学习」(Unsupervised Learning)现在已经成为深度学习...

36670
来自专栏机器学习之旅

总结:机器学习面试之常见决策树异同

历史回顾:1984年提出的cart,1986年提出的ID3,1993年提出的c4.5

10010
来自专栏技术随笔

[译] Deep Residual Learning for Image Recognition (ResNet)

38880
来自专栏崔庆才的专栏

深度学习效果不好?试试 Batch Normalization 吧!

Batch Normalization(简称BN)自从提出之后,因为效果特别好,很快被作为深度学习的标准工具应用在了各种场合。BN大法虽然好,但是也存在一些局...

1.5K30
来自专栏云时之间

聚类分析的简单理解(1)

各位小伙伴们大家好,这几天我在学习聚类分析这个统计方法,所以希望通过这个文章来概括下自己所学的知识,并且希望大家可以指出不足 1:什么是聚类分析? 聚类分析(...

37260
来自专栏书山有路勤为径

卡尔曼滤波器(Kalman Filters)

卡尔曼滤波器,这是一种使用噪声传感器测量(和贝叶斯规则)来生成未知量的可靠估计的算法(例如车辆可能在3秒内的位置)。

49230
来自专栏机器之心

专栏 | 云脑科技-实习僧文本匹配模型及基于百度PaddlePaddle的应用

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

Python数据分析笔记:聚类算法之K均值

我们之前接触的所有机器学习算法都有一个共同特点,那就是分类器会接受2个向量:一个是训练样本的特征向量X,一个是样本实际所属的类型向量Y。由于训练数据必须指定其真...

421100
来自专栏Python数据科学

【Python数据分析基础】: 异常值检测和处理

在机器学习中,异常检测和处理是一个比较小的分支,或者说,是机器学习的一个副产物,因为在一般的预测问题中,模型通常是对整体样本数据结构的一种表达方式,这种表达方式...

77430

扫码关注云+社区

领取腾讯云代金券