前置知识
可以参见：拟阵的相关知识，图拟阵
问题描述：
输入：拟阵 M=(S, I)，M的加权函数W
输出：对于加权函数W，M的最优子集
算法描述：
1. 确定贪心思想
这一步直接给出代码，描述有些繁琐。
贪心(M, W)
A = null;
按权W值大小排序S;
For 任意的x是S的元素（按W(x)递减顺序）DO
If AU{x} ∈ I /*选择目前W(x)最大的x */
Then A = AU{x};
Return A.
说明：构造一个集合M来作为最优子集的边集。
2.算法复杂性分析
- 令n = |S|
- 第3行的时间复杂度是O(nlogn);
- 第5~6行的算法复杂度是O(f(n))，那么4~6行的算法复杂度是O(nf(n))；
- 总的时间复杂度是：T(n) = O(nlogn) + O(nf(n))。
2. 分析贪心选择性。
定理1：设M=(S, I)是一个加权拟阵, W是M的权函数, S按W值递减排序. 令x是S中满足{x}∈I的第一个元素, 则存在一个M的优化子集A, x∈A。
证明：如果不存在一个M的优化子集A, x∈A。假设B是M的任意一个优化子集，且x不是B中的元素，那么可以以下列方法构造一个子集A：
- 初始时，A={x}；
- 由于A，B都是I的元素，且，|A| < |B|，由拟阵的变换性可知，存在x属于B-A，使得AU{x} 属于I。找到x，且令A = AU{x}。
- 重复第二步，直到|A| = |B|，而只要|A| < |B|，第二步可以一直进行。
由此构造方法，一定存在z是B的元素，使得A = (B - {z}) U {x}。
故而，W(A) = W(B) - W(z) +W(x) > W(B)，这与B是优化子集矛盾，假设不成立。
对于定理1，值得一提的是，x要求其W值最小，而这种最小之外是附有条件的，即{x} ∈I，一旦去掉这个条件，那么定理将不会成立。因为可能存在一种情况，虽然x的W值最小，但是{x}!∈I，那么就无法满足构造中的第二步条件。
至于其反例：W(x) < W(S/{x})，而{x}!∈I，而S/{x}∈I，此时的最大独立集合不包含x，即S/{x}。
3.分析优化子结构
对于优化子结构的证明需要额外附加一个条件，即存在x∈I，|x| ≥ 2。如果不满足该条件，那么算法只需要选出第一个元素即可，没有必要进行下一步，那么自然也不需要优化子结构。引理2默认该条件成立。
引理2：设x是第一个被贪心算法选中的元素. 对于包含x的优化子集A而言，A'=A-{x}是子问题M'=(S', I')的优化子集。M'=(S', I')定义如下:
- S' = {y∈S | {x,y}∈I}
- I' = {B |B是S-{x}的子集，且BU{x}是I的元素}
- 权函数相同
证明：
- 这里还需要证明我们所构建的二元组M'是一个拟阵。
- 需要说明的是，贪心算法所选中的第一个元素x，满足{x}∈I，且，其W值在Q中最小，Q = {y|{y}∈I}。
- S'非空。由于引理2的前置条件，即存在q∈I，|q| ≥ 2，那么，对于任意的q而言，|q|>|{x}|，且q,{x}∈I，依据拟阵M变换性，一定存在m∈q/{x}，使得{x}U{q}∈I，那么，s非空。
- I'是某些非空的S'子集的集合。由于BU{x}∈I，且，B是S-{x}的子集，那么B中的元素一定都是S'中的元素。对于B中的任意元素n，可知，{n}U{x} 是BU{x}的子集合，由拟阵M的遗传性，可知，{n}U{x}∈I，n∈S' 。
- 遗传性。BU{x}是I的元素，那么对于B的任意子集合A，AU{x}是BU{x}的子集合，由拟阵M的遗传性，AU{x}∈I，那么A属于I'。
- 变换性。任意的A，B∈I'，|A| < |B|，那么AU{x}∈I，且BU{x}∈I，|AU{x}|<|BU{x}|，由拟阵M的变换性，可知存在k∈BU{x}-AU{x}，即k∈B-A，使得，AU{k}U{x} ∈I，故而AU{k}∈I'。得证。
- 对于原问题的证明，如果A'=A-{x}不是子问题M'=(S', I')的优化子集，那么一定存在C'是子问题M'=(S', I')的优化子集,而且W(C') > W(A')。那么，可以构造一个集合C = C'U{x}，由于C'∈I'，故而C'U{x} 是I的元素，故而C是原问题某个子集，而W(C) = W(C') + W(x)，而W(A) = W(A') +W(x)，而W(A) < W(C)，这与A是原问题的优化子集矛盾，假设不成立。
4.分析算法正确性
完全可以由引理1以及引理2使用数学归纳法推出该算法的正确性。