拟阵贪心算法

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

图拟阵中独立集是森林；按边权非增扫描得到最大权生成森林，原图连通时才是最大权生成树。图示的五条边依次为 $ab:9,bc:8,ac:7,cd:6,bd:5$：先接受 $ab,bc$，拒绝会闭合三角形的 $ac$，再接受 $cd$，最后拒绝成环的 $bd$。结果是权重 $9+8+6=23$ 的基。通常所称的 Kruskal 最小生成树算法采用最小权版本，按边权非减扫描；因所有基大小相同，也可对权重取负后使用本算法。

线性拟阵以向量线性无关为独立性判据，可贪心选最大权向量基。均匀拟阵中所有大小至多 $k$ 的集合独立，最大权基问题退化为取权重最大的 $k$ 个元素；即使其中有负权，也要填满这 $k$ 个位置。

背包可行集虽向下封闭，却通常不满足拟阵交换公理。例如容量 $2$，一件物品重量 $2$、价值 $3$，另两件各重量 $1$、价值 $2$；按单件价值先取前者只得 $3$，另两件却合计 $4$。本定理针对单个拟阵上的可加元素权重；次模目标、两个拟阵的交等结构需要各自的算法和保证。

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

这里将贪心算法理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。的“选择—可行性检查—接受”框架具体化为权重排序与独立性查询。图拟阵、线性拟阵和分割拟阵分别把生成树、向量独立与配额选择接入同一交换证明。

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

连续贪心理路连续贪心算法Continuous greedy algorithm每轮用最大权拟阵基给多线性目标选择增长方向，以有限Euler步、显式梯度误差和可输出基分解实现接近1−1/e的近似。将本页算法反复用作线性方向工具：当前权重是多线性目标的梯度，输出基只贡献一个小步长。每轮最大权基求解精确，并不意味着原非线性目标也被一次排序精确最大化。