常见算法思想之动态规划_贪婪算法

傷城~ 2022-11-21 01:06 162阅读 0赞

## 1.动态规划 ##

最近总是跟动态规划打交道，索性就将其弄明白一点。所谓的动态规划并不是一种具体的算法，而是一种算法的思想。思想总是抽象的，缥缈的。所以在学习动态规划的时候会有一种很尴尬的情况，就是感觉这个东西很简单，但是又不知道自己是不是真的学会了。  
简单的来说，动态规划就是将一个大问题分解为子问题，然后根据子问题的解求出原问题的解。它适用于有**重复子问题**(**在问题计算的过程中，子问题要被重复计算多次**)和**最优子结构**(**局部最优解能决定全局最优解**)的问题。  
根据问题的这两个特征，我们很容易去简化这类问题：1.重复子问题：将子问题的结果进行存储，下次使用的时候直接调用，而不是每次都重新计算一遍。 2.最优子结构： 按顺序计算子问题的解，并且推导出子问题和下一个子问题之间的状态转移方程。随着最后一个子问题的解决，整体的问题也就解决了。  
这就是动态规划的思想了，其实也就是针对某一类特定的问题，得到简化这类问题的办法。我们之前聊过的前向后向算法，维特比算法，CTC损失等都是这类思想的实际应用。当然，如何将思想在实地应用，还需要更多的努力。目前我还只是去学习别人在特定问题上应用的套路而已。

### 1.2.动态规划的例子 ###

这是一个简单的例子，  
斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……  
它遵循这样一个规律：每一数都是前面两个数的和  
我们可以使用传统的递归的方式来实现，但是其复杂度是指数级的，我们知道指数级就相当于是不可用。实际测试了一下，计算100的斐波拉契数列，那个慢呀？唐僧也会愁到骂娘的。  
我们使用动态规划的思想分析一下问题，首先计算每一数的时候，前面所有的数都得重新计算一下，符合重叠子问题。其次最终问题的最优解包含的前面的数也是最优解，符合最优子结构。所以可以使用动态规划的思想来解决。  
1.建立状态转移方程：results\[i\] = results\[i-1\]+results\[i-2\]  
2.使用results 存储已解决子问题的解  
3.从小到大的顺序计算每一个值  
整体的复杂度为 O ( n ) O(n) O(n),对比原来的 O ( 2 n ) O(2^n) O(2n)来说就是天壤之别，到这里就清爽了很多。

#简单递归 复杂度为指数级
    def fib(n):
        if n<2:
            return n
        else:
            return fib(n-1) + fib(n-2)
    #使用动态规划 存储子问题的值
    def fib2(n):
        results = list(range(n+1))
        for i in range(n+1):
            if i < 2:
                results[i] = i
            else:
                results[i] = results[i-1]+results[i-2]
        return results
    import datetime
    if __name__ == '__main__':
        start = datetime.datetime.now()
        print(fib(100))
        end = datetime.datetime.now()
        print(end - start)

### 1.3 动态规划总结 ###

我们介绍了动态规划的思想，主要用来解决有重复子问题和最优子结构的问题。具体分为三步，一建立状态转移方程 二存储已解决子问题的解，重复利用 三 按顺序从小到大 计算每个子问题。动态规划应用非常广泛，如前向后向算法、维特比算法、背包问题、最长子串问题、最长子序列问题等。还需要是实际生活中多观察、多思考，才能完全的领会这种思想的精髓。

## 2.贪婪算法 ##

贪婪算法和动态规划有一些相似的地方，比如其都需要把大问题分解为子问题，由局部最优推出全局最优。不一样的地方在于贪婪算法不会存储子问题的值，因此其也就没有会退的功能。而且使用贪婪算法得到的一般是近似解，而不是最优解，因为贪婪算法并不会去验证所有的可能性。  
比如背包问题，小偷背着一个能装4磅的包，面前有三种物品 音响 4磅 3000$；吉他 1磅 1500元；笔记本电脑 3磅 2000元；小偷如何使得包中所装物品的总价值最高(小偷也太难了)？  
如果是一个傻小偷，随便那几件直到装不下；如果是一个稍微有脑子的小偷，就算一算，所有可能的情况，选出一个最好的。这就是穷举法，适合物品较少的情况。如果有100件商品，估计小偷没有算出来就已经进去了。  
所以我们需要求的是针对这类问题的一种方法论级别的策略，有一个聪明的小偷，它每次都选择所有物品中最贵的来偷，直到装不下。这就是贪婪算法。  
还有一个小偷，人称小偷界的华罗庚。他使用动态规划算法，迅速的在心里面画这样一个图。从第一个单元格开始填，每个单元格的值为:  
 M a x ( 当 前 商 品 价 值 + c e l l \[ i − 1 \] \[ j − 当 前 物 品 质 量 \] , c e l l \[ i − 1 \] \[ j \] ) Max(当前商品价值+cell\[i-1\]\[j-当前物品质量\],cell\[i-1\]\[j\]) Max(当前商品价值\+cell\[i−1\]\[j−当前物品质量\],cell\[i−1\]\[j\])  
以这样的方式求出了最高的价值，我已经不由得在心里面竖起了大拇指。这应该就是传说中的盗亦有道吧。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]  
我们来总结一下贪婪算法：  
1.将原问题分解为多个子问题  
2.求出每一个子问题的最优解  
3.将子问题的最优解进行合并，成为原问题的最优解。  
它经常用在一些没有办法求得最优解的情况下，使用贪婪算法可以得到近似最优解的解。

## 3.不要挣钱 ##

一个人的时候，我喜欢做这样的游戏，怀疑自己的思想。我并不是像那些疯子一样，觉得这个世界有什么奇怪的，说不通的地方。虽然说现实系统确实有很多比较明显的bug,但是我才懒得去管它们呢，我只要开开心心的活着就行了。我所说的怀疑纯粹是一种乐趣，就是为了怀疑而怀疑。因为我受不了被一种思维方式束缚的感觉，从我出生起就毫无反抗的接受了的这种思维。这么多年让我受尽折磨，奇怪的是我居然一直都没有发现它才是罪魁祸首。异想天开在我这里其实是个褒义词，你就把天给想开了也没什么大不了的，就算它实际上没有开于你也没有什么损失。我喜欢对着镜子中那张英俊的脸思考，我怎么会站在这里？一切为什么会是现在这个样子的？毫无疑问，这是一种天理运行的规则，我只是规则下的产物而已。可是我为什么会怀疑呢？我用思想去怀疑思想本身，就像用360去卸载360一样，这说不通呀！有一些可信的猜想，这种怀疑本就是思想的一部分，思想的本质就是摧毁并且建造，要想练就这种绝世武功，它就得有扫平一切的力量，包括扫平自己。或者说思想本身就不属于这个世界，身体只是它和这个世界对话的工具而已，这样它就不用扫平自己了。可是不管怎么样，你发现没？我都好像站在一个圈内在思考，即使我从这个圈里面跳出去还会有更大的圈。我们觉得无比自由的思想其实依赖于这个圈的限制，除非有一天这思想没了，也许这就是老子的道吧！但是，这件事还是等到我老了再去干，我可不愿意这么高的颜值随着现有规则的摧毁就被浪费掉(看到没，其实这也是它的狡猾之处)。

【Heize吧中字】\[UNPRETTY RAPSTAR2\] Semi Final「不要挣钱」- Heize(feat.灿烈)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/592bd7fd7b4f425c80aab08320102af6.png