拟阵贪心算法

拟阵把“任何局部可行独立集都能通过交换逐步扩展到基”抽象成公理。按权重从大到小扫描元素并保持独立时，交换性质保证“当前最好的可行元素”不会把未来堵死：可把任一最优基中的元素逐个交换成贪心元素而不降权。它给出了简单贪心对所有权重都正确的一类精确结构。

图拟阵中独立集是森林；按边权非增扫描得到最大权生成森林，原图连通时才是最大权生成树。通常所称的 Kruskal 最小生成树算法采用最小权版本，按边权非减扫描，或等价地在固定基大小下对权重取负。线性拟阵中独立性是向量线性无关，可贪心选最大权基。普通背包可行集不是拟阵；高价值重量比贪心会失败。定理依赖同一个拟阵上的加性元素权重，不自动覆盖次模目标、交两个拟阵或带容量的复杂约束。

图拟阵的元素是边，独立集是森林；按边权从大到小取且不成环得到最大权生成森林，正是 Kruskal 的拟阵版本。均匀拟阵中所有大小至多 $k$ 的集合独立，算法退化为取权重最大的 $k$ 个元素。

背包可行集满足向下封闭，却不满足拟阵交换公理，所以按价值或价值密度的简单贪心可失败。若目标不是元素权重可加和，拟阵结构本身也不保证该算法最优。

该算法统一解释最小生成树、向量基选择和调度中的贪心正确性，并提供检验某类可行系统能否被简单权重排序完全解决的结构标准。

拟阵公理库拟阵Matroid用遗传性和交换公理抽象线性无关集与森林结构的组合系统。 定义独立系统，拟阵贪心定理公理库拟阵贪心定理Matroid greedy theorem有限独立系统中，按非增权重加入可行元素对每个非负权重都产生最大权独立集，当且仅当该系统是拟阵。 给出充要性质，贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。 提供扫描框架。图拟阵、线性拟阵和分割拟阵把生成树、向量独立与配额选择统一到同一证明中。

单拟阵最大权独立集因交换公理可由排序贪心精确求解；拟阵交公理库拟阵交算法Matroid intersection algorithm · Unweighted matroid intersection在两个有限拟阵的交换有向图中寻找最短增广路，以独立性 oracle 构造最大公共独立集并在无路时输出秩和证书。要求集合同时独立于两个拟阵，普通贪心即使每步可行也可能卡在非最优基，需交换图增广。单调子模最大化公理库单调次模函数最大化monotone submodular maximization在基数约束下按最大边际收益贪心，利用收益递减取得 1−1/e 近似。在拟阵/基数约束下利用边际递减，通常只获近似。三者都出现“独立/边际选择”，但精确性分别来自单拟阵交换、增广结构和近似势分析。