贪心与调度 · HTML
数学 / 逻辑形态
比较相邻对象 a,b 的贡献 F(a,b) 与 F(b,a)。若可传递规则 a≼b 保证最小化时 F(a,b)<=F(b,a)，消除所有逆序即可得到全局最优顺序。
识别信号
- 方案本质是排序或逐个安排对象。
- 目标能拆为相邻次序或完成时刻贡献。
- 交换相邻项不改变其余部分可行性。
- 可写出 a-before-b 与 b-before-a 的代数差。
- 局部关系可传递或可化为排序键。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 局部最小看起来合理 | 没有 exchange、cut property 或 stays-ahead 证明，直觉不是正确性。 |
| 决策改变后续可选集 | 交换会破坏未来可行性时，纯排序贪心往往失效。 |
| 比较关系不传递 | 若出现 a≺b≺c≺a，sort comparator 无法定义一致全序。 |
核心不变量
贪心前缀无局部逆序，而且至少存在一个全局最优解与该前缀完全一致。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 按推导 key 排序的对象，以及扫描中的累计资源、时间或收益。 |
| Transition | 取排序后的下一项；若还需可行性筛选，只在保持前缀不变量时接受。 |
| Frontier / order | 排序后的首个未处理对象；证明视角是不断交换最优解中的逆序来对齐前缀。 |
Python 骨架
def greedy_order(items, key, initial_state, feasible, step):
state = initial_state
chosen = []
for item in sorted(items, key=key):
if feasible(state, item):
state = step(state, item)
chosen.append(item)
return chosen, state
正确性思路
- 取任一最优解，找到首个与贪心次序不同的位置，局部出现逆序 b,a。
- 由交换不等式将 b,a 换成 a,b，不降低目标且不破坏可行性。
- 有限次交换后得到与贪心顺序一致的最优解，因此每个贪心前缀都可扩展到最优。
复杂度
| Time | Space | Parameters |
|---|
| 通常 O(n log n) 排序 + O(n) 扫描 | O(n) 或依排序实现 | n 为对象数；关键前提是比较可传递且交换保持可行。 |
边界条件
- 排序键相同
- 交叉乘法溢出
- 零/负权改变不等式
- 稳定性或次级目标
- accept 依赖历史状态
错误模式
| Pattern | Why it fails / fix |
|---|
| 先猜 key 再补故事 | 应先写两种相邻顺序的成本差，再整理出 key。 |
| 只证明局部更好 | 还需证明交换不影响其余可行性，并可重复覆盖全局。 |
| 浮点比率排序 | 精度会改变顺序；尽量用交叉乘积并处理溢出。 |
| 忽略 tie 的次级目标 | 主目标相同但需字典序/稳定性时必须明确第二键。 |
选择与排除规则
- 先写 F(a,b) 与 F(b,a)，再导出 key。
- 验证交换不改变剩余可行集合。
- 检查比较关系能形成全序。
- 若选择依赖状态，另证 accept 规则或转 DP。
相关模板
| Relation | Template | Boundary |
|---|
| fallback | 有限状态机 DP | 决策改变未来状态，交换不再保持可行。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 顺序 1,2,5 最优，结论来自代数差。 |
| Setup | 任务耗时 2,5,1，目标最小化所有完成时刻之和。 |
| Trace | 相邻 a>b 时，顺序 ab 比 ba 多 a-b；因此不断交换逆序。 |
Recall prompts
我的补充