贪心算法

liweiwei1419 ... 2021-12-26 About 9 min

# 贪心算法

贪心算法又称贪婪算法。

  • 在对问题求解时,总是做出在当前看来最好的选择。即贪心算法不从整体最优上加以考虑;
  • 贪心算法所作出的是在某种意义上的局部最优解。

贪心算法和动态规划算法都是由局部最优导出全局最优,二者的区别如下。

贪心算法:

  • 贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留;
  • 贪心法正确的前提是:每一步的最优解一定包含上一步的最优解。

动态规划:

  • 全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解;
  • 动态规划的关键是确定“状态转移方程”,即如何通过已经求出的局部最优解推导出全局最优解;
  • 边界条件:即最简单的,可以直接得出的局部最优解。

贪心算法(高度概括) 贪心算法(Greedy Algorithm)

贪心算法是这样一种算法,它在每一步总是做出,在当前看来最好的选择。「贪心算法」并不是在任何时候都奏效,适合使用贪心算法的问题,在每一步总是通过做出局部最优的选择,来达到全局最优的效果。

那么由于「贪心算法」是一个比较大的话题,我们会在以后的章节具体介绍,在这里,大家只需要知道「选择排序」中使用了「贪心算法」,对这个事情有一个印象即可。

(下面这段文字不用)「贪心算法」应用于「选择排序」是直观且自然的。需要说明的是,能够使用贪心算法在严格意义上是需要数学证明的,而不能够使用「贪心算法」则只需要举出一个反例即可,这里大家对「选择排序」应用了「贪心算法」这个事情有一个印象即可,(「贪心算法」在算法领域属于应用简单,但是证明困难)。我们以后还会使用专门的章节介绍「贪心算法」。 相对于「贪心算法」,一个更好理解的概念是「循环不变式」,「循环不变式」其实也是证明「贪心算法」可以应用在「选择排序」上的理论基础。

参考资料:http://www.sohu.com/a/334457483_298038

第一部分:贪心算法和动态规划的关系

第二部分:通过简单的例子突出贪心算法的直观描述

第三部分:贪心算法的理论证明

第四部分:贪心算法的应用:哈夫曼树、最小生成树、单源最短路径(机器学习的决策树)


# 贪心算法的直观描述

「贪心算法」的「贪心」的含义是「只关注眼前利益」、「只看当前最好的」,而不从「全局」考虑。相比而言,「动态规划」和遍历算法(「广度优先遍历」、「深度优先遍历」)就显得很暴力,因为它们需要考虑 所有的 情况。

我对「贪心算法」的证明是这样理解的,就像「时间复杂度」的具体推导过程一样,在初学的时候,不一定要知道得特别具体。

「贪心算法」的证明和「时间复杂度」的具体推导过程,最完备的说明应该是在《算法导论》这本书上。

在《算法导论》第 16 章第 1 节的思考题里提到了「找零问题」,这个问题的描述给出了一些已知的结论。感兴趣的朋友不妨看一看。

「力扣」上其实就有这样的问题,「力扣」的第 322 题:零钱兑换 就是这样的问题,我们可以很容易地举出反例,证明「贪心算法」不能有效工作。而原因在这道题里我们已经和大家介绍过了,和面值相关。

我个人觉得大家了解到这个层面就足以应付找工作过程中的面试和笔试问题了,「贪心选择性质」的证明是不要求掌握的。

我们先通过具体例子叙述「不可以使用贪心算法解决的问题」。

我们在第 14 章「0-1 背包问题」里也叙述了「0-1 背包问题」也不能够使用贪心算法。因此,不能使用贪心算法的问题,只需要举出一个反例就可以了

# 我们须要

贪心算法的坏处

贪心算法的好处,哲学意义。

生活中遇到的各种事情,是不是「正确」都很难有定论,所以贪心是不是可以,须要具体问题具体分析。

我们先介绍「贪心算法」适用的领域:

  • 贪心算法与动态规划算法都适用于求解最优化问题。

求解最优化问题的特点是:需要经过若干个步骤,每个步骤都面临多种选择。

而「贪心算法」是这样一种算法:在每一步都做出当时看起来最好的选择。贪心算法依然有一个比较的过程。

之所以叫「贪心」,是因为它有这样一个特点:「局部最优,则全局最优」。

使用「贪心算法」的注意事项:

1、不是任何最优化问题都可以使用贪心算法去做,「贪心算法」的使用前提是这个问题具有「贪心选择」的性质;

而一个问题是否有「贪心选择」性质,也是需要严格证明的,但是在算法面试,甚至是平常我们做问题的过程中,都不会要求大家去证明「贪心算法」的正确性。

为此,我们只需要:

  • 凭直觉,感觉可以「贪心」去做,局部最优,全局最优;

说明:一般贪心问题都需要事先「排序」,所以选最优的过程,不需要经过比较。这一点属于定义的问题,怎么才能叫做「贪心」,其实不是我们研究问题的核心。

  • 尝试举出反例,如果举不出反例,大概贪心选择性质就是成立的。

做「贪心算法」的一般步骤,通常还是先考虑暴力怎么做,然后考虑是否可以贪心地去做。

我们先来看第 1 个问题。

# 贪心算法的哲学意义

所谓「哲学意义」,泛指对我们生活中做出某种选择的指导思想,不一定能得到最优解,但是得到一个差不多的解很多时候就可以。

我们在对一个复杂问题还一无所知的时候,常常考虑的就是「贪心算法」。例如:

  • 高考,只考察几门课程的学习成绩是无法衡量一个学生真实水平的,但是筛选出来的人至少不会太差,而且目前还没有更好的代替高考的方案。我们国家对于一些特长生还有特殊的选拔机制;
  • 找工作,用人单位选择候选人的时候也只会看几个重要指标,我们求职的时候选择公司,也只会关注一些重要的方面。

这一类的例子还有很多。

例如「机器学习」领域「决策树」的「剪枝」策略,就是采用一种基于「贪心算法」的策略,虽然不一定得到最优解,但是基于「贪心算法」得到的结果还不错。

# 总结

「贪心算法」 和 「动态规划」「回溯搜索」 一样,完成一件事情,是分步决策的,但是

  • 「贪心算法」在贪心选择性质成立的前提下,由于每一步都「最贪心」,因此只会剩下一个子问题;
  • 「动态规划」「回溯搜索」子问题一般而言不止一个。

「贪心算法」 在每一步总是做出在当前看来最好的选择,可以这样理解「最好」 :

  • 「最好」的意思往往根据题目而来,可能是「最小」,也可能是「最大」;
  • 贪心算法和动态规划相比,它既不看前面(也就是说它不需要从前面的状态转移过来),也不看后面(无后效性,后面的选择不会对前面的选择有影响),因此贪心算法时间复杂度一般是线性的,空间复杂度是常数级别的。

「田忌赛马」就不是贪心算法,因为田忌采用的策略是很高明的,用自己最次的马去和对方最好的马比较,好让自己剩余的两匹马在接下来的比赛中都能

# 贪心算法

第 2 节:基础

每一步都最优,轻微扰动,只有一个结果,变得更差

122. 买卖股票的最佳时机 II 561. 数组拆分 I


第 3 节:根据具体例子讲解动态规划于贪心算法的区别

135. 分发糖果 53. 最大子序和 376. 摆动序列


第 4 节:活动问题

56. 合并区间

435. 无重叠区间 452. 用最少数量的箭引爆气球 253. 会议室 II

第 5 节:跳跃游戏是典型的贪心算法的问题,注意贪心的点不一样。

55. 跳跃游戏 45. 跳跃游戏 II

第 6 节:

738. 单调递增的数字

402. 移掉K位数字


会员专享的 LB

0056-合并区间(简单)

860. 柠檬水找零 (opens new window)

861. 翻转矩阵后的得分

1400. 构造 K 个回文字符串 (opens new window)

392. 判断子序列

# 392. 判断子序列 (opens new window)

这篇题解讲到了无后效性:https://leetcode-cn.com/problems/is-subsequence/solution/mei-tian-yi-dao-suan-fa-ti-tan-xin-suan-fa-by-one-/

1710. 卡车上的最大单元数 1217. 玩筹码 (opens new window)

1247. 交换字符使得字符串相同 1605. 给定行和列的和求可行矩阵 (opens new window)

1209. 删除字符串中的所有相邻重复项 II (opens new window)

921. 使括号有效的最少添加



<40-1.png,40-2.png>

image.png

console.log('Hello world!')
1
print('Hello world!')
1
puts 'Hello world!'
1

image.png

@rang-ni-lai-duo-mi-wo

#include <iostream>

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int left = 1;
        int right = x;
        while (left < right) {
            int mid = left + (right - left + 1) >> 1;
            if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Last update: December 26, 2021 18:30
Contributors: liweiwei1419