[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法,这类问题有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解,而不是最优解,因为可能有多个解都达到最优值。

钢条切割问题

Serling公司购买长钢条,将其切割为短钢条出售。不同长度i的价格如下表:

问题描述为:给定一段长度为n英寸的钢条和一个价格表pi,求切钢条方案,使得销售收益最大。

课本上举了一个当n=4英寸的栗子,n=4时,有8种切割方案,其中切为两段2英寸的方案,收益最大为10.

最优子结构

为了求解规模为n的原问题,我们先求解形式完全一样,但规模更小的两个子问题,即当首次切割后,我们将两段钢条看成独立的钢条切割问题。我们通过组合两个相关子问题的最优解,并在所有可能的两段切割方案中选取组合收益最大者,构成原问题的最优解。我们称钢条切割问题满足 最优子结构性质:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。

自顶向上递归实现

除了上面说的方法,还有一种求解方法。利用递归的思想,首先将钢条从左边切割下长度为i的一段,只对右边剩下的长度为n-i的一段继续进行切割,对左边切割过的一段不再切割。问题分解的方式为:将长度为n的钢条分解为左边开始一段,以及剩余部分继续分解的结果。这样,不做任何切割的方案就可以描述为:第一段长度为n,收益为pn,剩余长度部分为0.对应的收益为0.

伪代码如下:

CUT-ROD(p,n)
# 如果n=0,则直接返回0
if n == 0
    return 0

q = 负无穷
for i =1 to n
    # 对于i从1到n,循环计算第i段和剩下n-i段的最大收益

    q = max(q, p[i] + CUT-ROD(p, n-i))

return q

CUT-ROD的输入是价格数组p[1..n]和整数n,输出是最大收益。

CUT-ROD过程是非常耗时的,原因在于其反复用相同参数值对自身进行递归调用,即他反复求解相同子问题。时间为n的指数函数,T(n)=2^n

使用动态规划求解

刚才看到用递归的方法求解太费时间了,然后看看用动态规划怎么求解。动态规划对每个子问题只求解一次,并将结果保存下来。如果随后再次需要此字问题的解,只需要查找保存的结果,而不必重新计算。注意这里要保存之前的计算结果,所以会消耗一定的存储空间,所以动态规划是典型的时空权衡的例子。

动态规划有2中等价求解方法,先看第一种

1. 带备忘的自顶向下法

此方法扔按照自然的递归形式编写过程,但过程会保存每个子问题的解,通常保存在一个数组或者散列表中,(散列表后面再说)当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间。否则,按通常方式计算这个子问题,我们称这个递归过程是带备忘的,因为他“记住了”之前已经计算过的结果。

2.自底向上法

刚才是自顶向下,现在刚好相反,是自底向上。通俗理解一下,自底向上就是先把原问题分解为规模大小按顺序排列的子问题,使得每个子问题的解只依赖规模更小的子问题的解,然后按规模大小排序,那么当求解某个子问题时,他所依赖的更小的子问题的解已经保存了,那么每个子问题也就只需要求解一次。

下面是带备忘的自顶向上的CUT-ROD过程的伪代码

# 主过程
MEMOIZED-CUT-ROD(p,n)
let r[0..n] be a new array
for i=0 to n
        # 令新建数组r的值都为负无穷,
        # 然后调用辅助过程MEMOIZED-CUT-ROD-AUX
        r[i] = 负无穷

return MEMOIZED-CUT-ROD-AUX(p,n,r)
MEMOIZED-CUT-ROD-AUX(p,n,r)
if r[n] >=0
        return r[n]

# 如果长度为0,则直接返回0.
if n ==0
        q = 0

# 和前面的CUT-ROD方法一样
else q = 负无穷
        for i = 1 to n

                  q = max(q, p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i, r))
r[n] = q
return q
自底向上版本的伪代码
BOTTOM-UP-CUT-ROD(p,n)
# 新建数组r,保存子问题的解
let r[0..n] be a new array
# 如果长度为0, 则解为0.
r[0]=0
# 对j由升序方式求解每个规模为j的子问题,求解规模为j的子问题方法
# 和CUT- ROD所采用的方法相同,只是现在直接访问数组元素r[j-i] 来
# 获得规模为j-i的子问题的解,避免重复求解带来的时间消耗。
for j = 1 to n
        q = 负无穷

        for i = 1 to j
                q = max(q, p[i] + r[j - i]
        r[j] = q

return r[n]

这一章内容挺多的,先介绍到这里了,下次继续。

原文发布于微信公众号 - 机器学习和数学(ML_And_Maths)

原文发表时间:2017-09-22

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.12数据流中的频繁元素

No.12期 数据流中的频繁元素 Mr. 王:我们再来讲一个例子,数据流中的频繁元素。我们先来说说大数据的数据流模型。 小可:数据流,是流动的数据的意思吗?和...

33070
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习_二分查找算法

22640
来自专栏机器之心

资源 | Tensorlang:基于TensorFlow的可微编程语言

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

2018.10.23NOIP模拟赛解题报告

比赛开场看T1一点思路都没有,不管怎么想都是\(O(n^2)\)的复杂度,做了好久终于发现自己傻逼了这就是个傻逼题。。

10830
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

32350
来自专栏ACM算法日常

不同路径(动态规划)- leetcode 62

最近在看leetcode的题目,都是面试题,需要面试的同学可以努力刷这里的题目,因为很多公司的面试笔试题都是参考这个上面的。相对OJ上的题目,感...

17840
来自专栏java 成神之路

高亮标红

30580
来自专栏Pytorch实践

python实现字符串模糊匹配

之前笔者写过一篇文章关于如何做搜索,但那篇文章的角度是从文本相似度角度写的。那种方式是目前发展的趋势,但是真正的搜索特别是网页搜索不可能在大范围的文本之间两两算...

4K60
来自专栏SimpleAI

Hello,1024背后可爱的人儿

14940
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

25930

扫码关注云+社区

领取腾讯云代金券