Skip to content

约 5 分钟阅读

贪心算法 ​

贪心在当前可选项中按某个规则做出选择,并继续处理剩余问题。它是否能得到全局最优,取决于这个规则与问题约束的配合。选择会影响后续可行空间,不能因为“每一步看起来最好”就断言答案最优。

例如一间会议室,希望安排尽可能多场预约。每场价值相同、不可拆分,结束时刻可以紧接下一场开始。按结束时间从早到晚选择不冲突的预约,可以得到最多场数;如果目标换成总收入最大,相同规则就可能失败。

会议室预约按结束时间选择的结果

会议室:先结束,为后续留下空间 ​

四场预约分别为 A=[0,6)、B=[1,3)、C=[3,5)、D=[5,7)。时间单位可理解为从某个起点起的小时。A 最早开始,但选它后只能再接 D,共两场;按结束时间选择 B、C、D,可以安排三场。

把所有预约按结束时间排序,依次检查开始时间是否不小于上一场结束时间。排序后的每个被接受预约,都成为新的时间边界;与它重叠的预约被拒绝。这个扫描只针对一间会议室和“最大场数”的目标。

为什么第一步安全?设某个最优方案的第一场为 O,结束最早的预约为 G,有 end(G) <= end(O)。把 O 换成 G,后续场次仍不冲突,场数也不减少。因此存在一个以 G 开头的最优方案。对 G 结束后的剩余预约重复这个论证,即可证明整个策略。证明依赖无权、正时长和同一资源等条件。

完整实现:不修改输入的预约选择 ​

以下 Python 3 示例限定同一天内的整数分钟,使用半开区间 [start, end);end == next.start 允许衔接。编号必须唯一,零时长、跨午夜或非法时间应在进入本模型前处理。

python
from dataclasses import dataclass


@dataclass(frozen=True)
class Booking:
    booking_id: str
    start: int
    end: int


def select_bookings(bookings):
    bookings = tuple(bookings)
    ids = set()
    for item in bookings:
        if not isinstance(item, Booking):
            raise TypeError("预约必须使用 Booking")
        if not isinstance(item.booking_id, str) or not item.booking_id.strip():
            raise ValueError("预约编号不能为空")
        if item.booking_id in ids:
            raise ValueError("预约编号必须唯一")
        if type(item.start) is not int or type(item.end) is not int:
            raise ValueError("时间必须是整数分钟")
        if not 0 <= item.start < item.end <= 24 * 60:
            raise ValueError("预约必须为同一天内的正时长区间")
        ids.add(item.booking_id)

    ordered = sorted(bookings, key=lambda item: (item.end, item.start, item.booking_id))
    selected = []
    last_end = None
    for item in ordered:
        if last_end is None or item.start >= last_end:
            selected.append(item)
            last_end = item.end
    return tuple(selected)


bookings = (
    Booking("A", 0, 6 * 60),
    Booking("B", 1 * 60, 3 * 60),
    Booking("C", 3 * 60, 5 * 60),
    Booking("D", 5 * 60, 7 * 60),
)
assert tuple(item.booking_id for item in select_bookings(bookings)) == ("B", "C", "D")
assert select_bookings(()) == ()
print(tuple(item.booking_id for item in select_bookings(bookings)))

输出 ('B', 'C', 'D')。结束时间相同时,以开始时间、编号固定排序,仅保证结果可重复,不表示它们是业务优先级。排序 O(n log n),扫描 O(n),输入快照、排序和输出合计 O(n) 额外空间。上述分析把时间与编号比较近似视作常数;特别长的编号会增加比较成本。

如果会议室需要清洁时间,应把占用结束时间扩展后重新建模。若预约之间还有必须同时接受、指定会议室或人员冲突等约束,原来的交换证明未必成立,不能直接添加几个 if 就继续声称最优。

三种直觉为什么会失效 ​

看似合理的规则反例正确解释
最早开始优先A=[0,6),B=[1,3),C=[3,5),D=[5,7)选 A、D 只有 2 场,B、C、D 为 3 场
时长最短优先A=[0,3),B=[3,6),X=[2,4)X 最短,却同时阻挡 A、B,只安排 1 场
收入最高优先A=[0,4)收入9,B=[0,2)收入5,C=[2,4)收入5A 收入 9,B+C 收入 10

即使按结束时间选择,也只保证无权最大场数。令 A=[0,4)收入100,B=[0,2)收入1,C=[2,4)收入1,会先选 B 再选 C,只得 2,最优却为 A 的 100。

带权区间调度可以按结束时间排序,令 p(i) 是第 i 场之前最后一个不冲突预约的位置,再比较“不选 i 的最佳收入”和“选 i 的收入加上 p(i) 的最佳收入”。这属于动态规划,需要定义空前缀、允许拒绝全部预约及平分规则。不能把带权代码放在贪心名下而省略模型变化。

其他贪心模型的前提 ​

模型安全选择依据容易越界的条件
分数背包正重量、非负价值,物品可按比例分割,按单位重量价值选0-1 背包不可拆;容量、零重量和负价值必须另定合同
最小生成树无向带权图上的割性质不连通时只能得到最小生成森林,不能宣称生成一棵树
Dijkstra每次确定未完成顶点中的最小距离需要非负边权;负权需换算法,见图算法
Huffman 编码合并最小的两个正权重构造前缀码空输入和单符号需单独定义,压缩大小还含码表与填充位
区间覆盖在能覆盖当前端点的区间中选伸展最远者先定义闭/开端点与目标;发现缺口返回失败,不能当作空解
删除 k 位求最小数在固定删除数量下维护单调栈,再去掉尾部多余位k 范围、字符集、前导零与全删后的表示必须明确
找零某些币值体系具备特定结构任意币值不成立:1、3、4 凑 6,最大面值优先为3枚,最优为2枚3

Huffman 的前缀码必须支持唯一解码。解码遇到非二进制字符或结束在非叶节点,应报告非法或截断码流;不能把任意字符都当作 1。单符号若约定编码为 0,还需要原始长度或等价终止信息。使用字符串长度当作压缩后字节数,会忽略存储表示与元数据。

“删除最少字符,使字符串非递减”也不能照搬删除固定 k 位的单调栈。例如 bcda,每遇到更小字符就弹出前面的字符,会只留下 a,删除 3 个;保留 bcd 只需删 1 个。这类问题可转成最长非递减子序列:最少删除数为原长度减去其长度。严格递增与非递减的比较符不同,详见搜索算法与字符串算法。

怎样验证策略 ​

先说清优化目标、可行性和输入边界,再给交换论证、割性质或其他正确性依据。随后用小规模穷举枚举所有可行集合,与贪心返回的目标值比较;测试可以暴露反例,不能替代对任意输入的证明。

预约例应覆盖空输入、完全重叠、首尾相接、相同结束时间、重复区间不同编号、零时长和越界时间。验证时同时检查场数最优、输出互不冲突、返回对象来自输入、原输入顺序未变。若业务目标改成收入、优先级或公平性,应重新确认模型;“旧用例仍通过”不足以证明新目标也正确。

对暂时无法证明的选择规则,可以把它作为启发式获得可行方案,并用穷举或精确算法测量小实例差距。报告中应写清是否有最优性保证,避免把运行快等同于解得对。

别急,先让缓存热一下。