7.3 拟阵理论——贪心正确性的数学充分条件
这一节回答什么问题？
有没有数学条件能判断贪心一定有效？
拟阵的定义
拟阵是一对 (E, I)，其中：
- E 是有限集合
- I 是 E 的独立子集族
满足两个性质：
- 遗传性：A ∈ I 且 B ⊆ A → B ∈ I
- 交换性：A, B ∈ I 且 |A| < |B| → 存在 x ∈ B-A 使得 A∪{x} ∈ I
贪心在拟阵上有效
如果问题能建模为拟阵，GREEDY 算法返回最优解。
经典例子：图拟阵 M_G 的 GREEDY 就是 Kruskal 最小生成树算法。
关键限制
拟阵是充分条件而非必要条件。
活动选择和 Huffman 不是拟阵实例，但贪心仍然正确。
本节小结
这一节解决了什么问题？
贪心何时有效有数学保证吗？
核心方法是什么？
拟阵理论：遗传性 + 交换性 → 贪心有效。
它为什么正确？
拟阵结构保证贪心每步不失去最优性。
它在什么情况下不适用？
非拟阵问题——但贪心可能仍然有效，需要其他证明方法。