贪心算法

贪心算法


蒋炎岩

南京大学计算机科学与技术系

jyy@nju.edu.cn

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

先来玩一个游戏

你要偷走桌上的物品 (已经标好价格)

  • 每次可以拿一个放到背包里
  • 警察随时会到达,到达时立即带着背包逃跑
    • 给出警察在每个时刻出现的概率
  • 你应该怎么拿?

(看起来很显然)

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

贪心算法

解决的问题:

从大集合里

  • 选出一些东西
  • 排成一个顺序

达成某个目标


贪心算法

  • 按照某个顺序 (规则) 选,拿到就拿到,不后悔
  • 非常符合人类的 System 1
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

为什么从大到小就是对的?

算一算收益

  • 警察在 到达:收益 ,概率
  • 警察在 到达:收益 ,概率
  • 警察在 到达:收益 ,概率
  • ……

总收益

  • 整理系数,就能给一个更严更的说明了
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

换一个问题

个同学排队接水,接水的时间分别是

  • 如何安排同学接水的顺序
  • 使所有同学的平均等待时间最小?

不那么直观,但好像还是有点直观

  • 越困难的问题,越需要数学符号的辅助
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

什么样的顺序更好?用一点点符号

两个同学,打水时间分别是 ,


四个同学,打水时间分别是

    • 熟悉的式子
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

排成更好的顺序

还记得冒泡排序吗?

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] > a[j]) {
            swap(a[i], a[j]);
        }

和它的另一个版本

while (!is_sorted(a)) {
    auto [i, j] = find_unordered(); // 返回任意 i < j, a[i] > a[j]
    swap(a[i], a[j]);
}
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

基于比较的排序

第二个版本很有趣

  • 如果不存在 就一定排好序了
  • 如果不存在 也就一定排好序了
    • 为什么?

交换论证:反过来假设存在一个不按照从小到大排序的最优解

  • 存在
  • 交换它们能的到更好的解
  • 矛盾
    • 我们得到了第一个贪心算法的证明
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

如果游戏变了?

依然是偷走桌上的物品

  • 每个物品有自己的重量
    • 而且背包有一个重量上限
  • 放进背包就不能取出

似乎就有点 “难以决定” 了

  • 排在第一位的系数:
  • 排在第二位的系数:
  • ……
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

一些尝试

还按照价值从大到小放?

  • 如果警察几乎总是最后赶到,可能会错过一些更好的配置

先求背包放满的最大价值,再从大到小拿?

  • 如果警察几乎总是第一时间赶到,那就应该优先拿一个价值大的

并不适合贪心

  • 我们依旧从大到小挑,但我们无法立即决定应该选谁
  • 需要留下更多的候选 (动态规划)
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法

小结

贪心:排好顺序,不后悔

  • 根据 “前一部分” 做的决定就总是最好的
  • 一般需要题目有比较好的数学性质
    • 尽量不要猜;动笔算

有时,排序的条件很有趣

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

拼数与排序

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

拼数问题

给定 个正整数,将它们联成一排,相邻数字首尾相接,问能拼成的最大的多位整数

    • ← 这个看起来更大一些
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

另一种贪心的方法

“局部搜索”

  • 最优解一定是不可调的;调了也许就是最优解呢
do {
    b = have_some_try(a);
    if (cost(b) < cost(a)) {
        a = b;
    }
} while (!should_terminate());
  • 经典应用:Gradient Descend 和优化问题
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

改变世界的贪心算法

GPT-4-turbo回复:想象你在一个山上,目标是要到达山谷的最低点。但是,山上雾很大,你看不清远处的路。你只能感觉到脚下地面的倾斜方向,然后决定下一步往哪个方向走。在这个比喻中,山谷的最低点就像是我们训练深度神经网络时想要找到的最佳模型(即错误最小的模型),而你脚下地面的倾斜方向就像是梯度(Gradient),它告诉我们参数应该如何调整才能让模型的错误减少。

梯度下降的原理就是:通过计算当前位置(当前模型参数)的梯度(即错误变化的方向和大小),然后向梯度的反方向(因为我们是要下山,而梯度指向的是上升最快的方向)调整一小步,重复这个过程,直到找到山谷的最低点,也就是模型的错误最小的地方。

  • (这些文字是由贪心算法训练的神经网络生成的!)
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

拼数问题的局部搜索

do {
    bool fixedpoint = true;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            b = a;

            swap(b[i], b[j]);
            if (cost(b) < cost(a)) { // 交换使代价变小
                a = b;
                fixedpoint = false;
            }
        }
} while (!fixedpoint);
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

局部可调?

bool swap_is_useful(const string &i, const string &j) {
    string mid;
    for (int k = i + 1; k < j; k++) {
        mid += a[k];
    }

    return BigInteger(a[i] + mid + a[j])
            < BigInteger(a[j] + mid + a[i]);
    // 长度相同,因此等价于
    //     a[i] + mid + a[j] < a[j] + mid + a[i]
}

如果只考虑相邻的 (mid 为空)?

a[i] + a[i+1] < a[i+1] + a[i]
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

最优解

最优解一定没有

  • 否则交换它们可以变得更大
  • 但找不到相邻可交换的解就是全局最优解吗?

局部最优解是否是全局最优解?

  • 如果构成了一个 “正确的顺序”,排序就是正确的
    • 两两可比、且满足传递性
    • 证明有点困难
    • 更实际的方法:验证 + 观察
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 拼数与排序

小结

局部搜索:向更好的方向调整

  • 无法调整时,是否是最优解?

计算机为什么叫电脑

  • 人类思维活动的延伸
    • 编程语言实现机械过程的自动化
    • AI 实现人脑思维过程的延伸
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 区间与选择

区间与选择

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 区间与选择

刷题高手

有若干场比赛,每场比赛是连续进行的,覆盖时间段

  • 同一时刻至多只能参加一场比赛
  • 问最多可以参加多少场比赛

(先假设所有区间端点都不同,容易处理)

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 区间与选择

选择困难症

到底应该选什么好呢?


我们是在解决问题

  • 不是 “套公式套模板”
    • 而是 “理解问题的结构”

观察法

  • 画出三个区间 (6 个端点) 的所有可能情况
  • A. C. (Anno. ChatGPT) 时代:靠手
  • 今天:我们有 AI 啊
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 区间与选择

观察与求解

什么是 “不会后悔” 的选择?

  • 避免 “不小心选了一个,损失了两个”
  • 给未来留出最多的空间

选最先结束的!

  • 所有区间按照右端点排序
  • 能取就取,不能取就不取
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 区间与选择

证明

一定存在一个最优解,包含最先结束的区间

  • 假设另一个最优解首先选了一个比 结束的晚的
  • 总是可以把它 “换成” ,保持数量不变
    • 去掉不能选的,我们就得到了一个更小的问题

所以,如果区间有代价,贪心就不对了

  • 看到证明哪里不对了?
  • 我们可以牺牲数量换质量
  • 不能 “妄下定论”
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 区间与选择

一个有趣的推论

以下算法也是正确的

  • 任意选一组不相交的区间
  • 如果能多放进来一个区间,就放进来
  • 如果能把任何一个区间换成更早结束的,就交换
    • 最早结束的总会被选中
    • 然后是剩下里最早结束的……
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 不显然的结论和推导

不显然的结论和推导

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 不显然的结论和推导

国王游戏

国王邀请 个大臣玩一个有奖游戏

  • 每个人 (国王和大臣) 在左、右手上各写下一个整数 (给出这些数字)
  • 所有人排成一队,国王站在队伍的最前面
  • 所有的大臣都会获得国王奖赏的若干金币,每个大臣获得排在该大臣前面的所有人 (包括国王) 的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果

国王不希望某个大臣获得特别多的奖赏,所以他想请你帮他安排一下队伍的顺序,使得获得奖赏最多的大臣所获奖赏尽可能的少

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 不显然的结论和推导

看起来就很复杂

就算你猜是贪心,按什么排序呢?

  • 甚至都不知道是不是贪心

怎么办?

  • 不要猜,试图去理解问题
    • 套过所有 “模板”,找不到就放弃?
  • 数学是帮我们简化问题的手段
    • 符号弥补了人类短时记忆有限的缺点
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 不显然的结论和推导

从特殊到一般

  • 没有学过直接处理这个式子的方法?
    • 我们学过初中不等式!
    • : 把绝对值去掉
  • 逐个 case 分析即可

特别提示:准确性训练

  • 草稿纸:可以帮你 replay 步骤,找到出错的地方
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 不显然的结论和推导

Case Analysis


    • (与题目假设矛盾)
      • 题目的奥秘:从整数换到实数,就不好做了
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 不显然的结论和推导

小结

不要怕公式

  • 公式有时是帮我们的
  • 直觉并不总是能帮我们

用好草稿纸

  • 符号推导的准确性训练
  • 不要猜,推导 + 检查
蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 总结

总结

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 总结

总结

贪心的两种表达方式

  • 排好顺序、做出选择、不后悔
  • 局部搜索 (向 “排序” 的方向调整)

学习贪心算法

蒋炎岩 (南京大学计算机科学与技术系)
贪心算法 / 总结

End. (Notebook)

蒋炎岩 (南京大学计算机科学与技术系)