基本算法之贪心

贪心算法的基本核心就是将问题分解成多个步骤，在每个步骤中选取当前步骤的最佳解决方案，直到所有步骤选择结束。在每一步骤选择时不考虑对后续步骤的影响，在后续步骤中再也不回头改变前面的选择。

有一些高级算法是基于贪心思想的，例如最小生成树算法，单源最短路径Dijkstra算法，哈夫曼编码等。

但是贪心法不容易得到最优解，如何判断能够使用贪心法，可以看看问题是否满足以下特征：

使用拟阵能够在很多情况下确定贪心法是否可以产生最优解。

拟阵

拟阵的定义是建立在一个有限集合和该集合上的一个独立子集族上的。给定一个有限集合 $E$ 和一个独立子集的族 $\mathcal{I}$ ， $(E, \mathcal{I})$ 构成一个拟阵，如果它满足以下三个公理：

非空性（Non-empty）：独立子集族 $\mathcal{I}$ 包含空集，即 $\emptyset \in \mathcal{I}$ 。
遗传性（Hereditary）：如果一个集合 $A$ 属于独立子集族 $\mathcal{I}$ ，那么 $A$ 的任何子集也属于 $\mathcal{I}$ 。
交换性（Exchange property）：如果 $A$ 和 $B$ 都属于独立子集族 $\mathcal{I}$ ，并且 $A$ 的大小小于 $B$ 的大小，那么存在一个元素 $x \in B \setminus A$ ，使得 $A \cup \{x\}$ 也属于 $\mathcal{I}$ 。

这些公理捕捉了线性独立的本质特征。例如，在向量空间中，线性独立的向量集合满足上述条件：空集是线性独立的（非空性），线性独立集合的任何子集也是线性独立的（遗传性），并且如果一个线性独立集合的大小小于另一个，则可以从较大的集合中取出一个向量添加到较小的集合中，保持线性独立（交换性）。

如果一个问题可以构造成拟阵，则一定能用贪心法。能用贪心法的不一定可以构造成拟阵。