拟阵贪心定理

贪心每次取当前最重且仍保持独立的元素。交换公理保证，若最优基没有选这一步的元素，总能从最优基中换掉一个不更重的元素而保持为基，因此局部选择不会封死全局最优。反过来，若独立系统不满足交换性，可以设计权重放大某次错误选择，使贪心失败；这使拟阵成为“所有权重下贪心都正确”的精确结构。

在图拟阵上，算法就是 Kruskal 型的最大权生成森林算法；在线性拟阵上，它按权重选择保持线性无关的向量。非负条件对“最大权独立集”版本不可省略：若所有权重为负，空集优于任何非空基，而强制扫描并加入的算法会失败。对一般背包可行集，遗传性成立但交换性失败，按单位价值或总价值排序都不能获得普遍正确的贪心算法。定理只保证给定独立性判定器后的组合正确性，不自动保证判定本身高效。

交换公理缺失时，贪心会明确失败。设

并令 $w(a)=3$、$w(b)=w(c)=2$。按权重先取 $a$ 后无法再扩张，只得权重 $3$；最优集 $\{b,c\}$ 权重为 $4$。问题正出在 $\{a\}$ 无法用 $\{b,c\}$ 中元素作交换扩张。

贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。在拟阵公理库拟阵Matroid用遗传性和交换公理抽象线性无关集与森林结构的组合系统。上获得对任意权重的正确性保证，图拟阵公理库图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。的轻边优先版本给出最小生成树实例。基交换既提供证明，也支持动态更新和敏感性分析；秩函数公理库拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat用最大独立子集的大小定义拟阵秩，并以不增加秩的元素定义闭包与平坦。把可扩充性写成数值约束。两个拟阵约束的共同独立集通常不再适用同一贪心，而由拟阵交定理公理库拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。的增广结构和 min–max 证书处理。