贪心算法

快速概览

贪心算法在每一步选择中都采取当前状态下最优的选择，希望通过局部最优达到全局最优。它简单、高效，但在处理复杂生物学问题时常因陷入局部最优而失效。

理解贪心策略的"短视"特征及其优缺点
掌握反转排序中的简单贪心与基于断点的改进策略
了解贪心算法在 Motif Finding 中的应用及其局限
理解贪心算法与近似算法的关系

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

1. 贪心策略的核心

贪心算法（Greedy Algorithm）遵循一个简单的准则：每一步都做当前看起来最好的选择。它不回头、不反悔，一旦做出选择就不再改变。

贪心算法的三个特征

贪心选择性质（Greedy Choice Property）：可以通过局部最优选择产生全局最优解。这是贪心算法正确性的前提。
无后效性（No Aftereffect）：某个状态以前的过程不会影响以后的状态，只与当前状态有关。这意味着当前的选择不会限制未来的选择空间（在满足贪心选择性质的前提下）。
简单高效：通常只需一次遍历或少量迭代，时间复杂度远低于动态规划或分支定界。

何时贪心算法有效

贪心算法并非总是失败的。在以下条件下，贪心策略可以保证找到全局最优解：

活动选择问题（Activity Selection）：选择最多数量的互不重叠的活动。按结束时间排序后贪心选择可以保证最优。
Huffman 编码：构建最优前缀码。每次合并频率最低的两个节点，可以保证编码总长度最短。
Dijkstra 最短路径：在非负权图中，每次选择距离最近的未访问顶点，可以保证找到最短路径。
最小生成树（Kruskal / Prim）：每次选择权重最小的边（不形成环），可以保证总权重最小。

这些问题的共同特征是：局部最优选择与全局最优之间有严格的数学联系（通常可以通过交换论证法证明）。然而，生物信息学中的大多数问题并不满足这一条件。

2. 贪心算法的失效：局部最优陷阱

贪心算法最致命的缺点是它不考虑长远后果。当前看起来最好的选择，可能导致后续无法达到全局最优。

示例：换钱问题

如果在币制 $\{25, 20, 1\}$ 下要凑够 $40$ 分：

贪心策略：先选最大的 $25$ ，剩下 $15$ 只能选 $15$ 个 $1$ ，总计 $16$ 枚硬币。
全局最优：选 $2$ 个 $20$ ，总计 $2$ 枚硬币。

贪心策略在这个币制下完全失败，因为它贪心地选了面值最大的硬币，却没有考虑到 $20 + 20$ 的组合更优。

关键观察：在标准美元币制 $\{25, 10, 5, 1\}$ 下，贪心策略恰好是最优的。但这并不是一个普遍性质，而是该特定币制的”幸运”结果。

在生物信息学中的表现

在生物信息学中，许多问题（如序列比对、进化树搜索、Motif 寻找）的搜索空间充满这种”局部陷阱”。贪心算法在这些场景下往往只能找到”还不错”的解，而无法保证最优。

问题	贪心策略	失效原因
进化树搜索	每步选择使似然增量最大的分支	可能错过需要暂时”牺牲”当前得分的拓扑结构
Motif 搜索	每步选择与当前 Profile 最匹配的位置	第一步的错误选择会被放大（“滚雪球”效应）
基因组重排	每步增加已排序前缀长度	可能需要暂时破坏已排序部分才能找到更短的反转序列

3. 应用案例：反转排序（Reversal Sort）

在研究物种进化时，我们需要通过最少次数的”反转”操作将一个基因排列转换为另一个。这个问题是贪心算法在生物信息学中的经典案例。

简单贪心：前缀固定法

每一步将数字 $i$ 移到位置 $i$ 。

排列：6 1 2 3 4 5

贪心步骤（需要 5 步，依次将 1, 2, 3, 4, 5 翻转到前面）：

初始：  6 1 2 3 4 5  (prefix = 0)
步骤1： 1 6 2 3 4 5  (反转 [1,2]，prefix = 1)
步骤2： 1 2 6 3 4 5  (反转 [2,3]，prefix = 2)
步骤3： 1 2 3 6 4 5  (反转 [3,4]，prefix = 3)
步骤4： 1 2 3 4 6 5  (反转 [4,6]，prefix = 4)
步骤5： 1 2 3 4 5 6  (反转 [5,6]，prefix = 6)

实际最优（只需 2 步）：

初始：  6 1 2 3 4 5
步骤1： 5 4 3 2 1 6  (反转 [1,5]，翻转全序列)
步骤2： 1 2 3 4 5 6  (反转 [1,5]，翻转前 5 位)

贪心算法用了 5 步，而最优解只需要 2 步。差距的根源在于贪心策略”急功近利”——每步只增加一个已排序元素，而最优解通过暂时”打乱”整个序列来一次性解决问题。

改进：基于断点（Breakpoints）的贪心

断点是指排列中不连续的邻接关系。为了改进贪心算法，我们需要一个更好的”进度度量”（Progress Metric）：

断点数：排列 $\pi$ 中断点的数量记为 $b(\pi)$ 。
目标：每次反转选择能最大程度减少断点数量的操作。
理论保证：恒等排列 $1\ 2\ \cdots\ n$ 是唯一没有断点的排列。每次反转最多可以消除 2 个断点，因此最少反转次数 $d(\pi) \geq b(\pi) / 2$ 。

这种策略虽然仍是贪心的，但它使用了更科学的”势能函数”来引导搜索，其近似比为 4（即返回的解最多是最优解的 4 倍）。

详见：基因组重排与反转排序

4. 贪心算法在 Motif 搜索中的影子

在寻找 DNA 序列中的保守模式（Motif）时，一种贪心思路是：

在第一条序列中选一个可能的起始位置。
根据这个位置构建 Profile（位置权重矩阵）。
在下一条序列中选与 Profile 最匹配的位置并更新 Profile。
重复直到所有序列都被处理。

贪心 Motif 搜索伪代码

GREEDYMOTIFSEARCH(Dna, k, t)
1  BestMotifs ← k-mers from first string of Dna
2  for each k-mer Motif in first string of Dna
3      Profile ← Profile(Motif)
4      Motifs ← [Motif]
5      for i ← 2 to t
6          Motifs[i] ← Profile-most probable k-mer in Dna[i]
7          Profile ← Profile(Motifs)
8      if Score(Motifs) < Score(BestMotifs)
9          BestMotifs ← Motifs
10 return BestMotifs

问题与对策

问题：这种”滚雪球”式的方法极度依赖第一步的选择。如果第一条序列中选择的 k-mer 偏离了真实的 Motif，后续所有序列的选择都会被带偏，导致 Profile 越来越偏离真实分布。

对策：实际工具（如 MEME）通常结合以下策略来弥补贪心的不足：

多起点重启（Multiple Random Restarts）：从不同的初始位置出发，运行多次贪心搜索，取最好的结果。
期望最大化（Expectation-Maximization, EM）：迭代地估计 Profile 参数和 Motif 位置，可以避免贪心算法的”一步定终身”问题。
Gibbs 采样（Gibbs Sampling）：随机化方法，在每一步随机排除一条序列，根据其余序列的 Profile 重新选择该序列的 Motif 位置，可以跳出局部最优。

5. 贪心与近似算法（Approximation）

虽然贪心算法不一定能找到最优解，但我们常能证明它找到的解”不会太差”。这就是**近似算法（Approximation Algorithm）**的核心思想。

近似比（Approximation Ratio）

对于一个最小化问题，设算法返回的解为 $A$ ，最优解为 $OPT$ 。如果存在常数 $c \geq 1$ 使得：

$A \leq c \cdot OPT$

对所有输入成立，则称该算法是一个 $c$ -近似算法， $c$ 称为近似比。

生物信息学中的近似算法实例

问题	贪心策略	近似比	说明
反转排序	基于断点的贪心	4	每次反转减少最多的断点
反转排序（改进）	断点 + 条带策略	2	目前最好的已知近似比为 1.375
最短公共超串	贪心合并最长重叠	2-4	用于基因组组装的早期方法
Steiner 树（网络）	贪心添加最近节点	2	用于构建基因调控网络

为什么近似算法在生物信息学中重要

许多生物信息学问题已被证明是 NP 困难（NP-hard） 的，意味着不存在多项式时间的精确算法（除非 P=NP）。在这种情况下，近似算法提供了一种折中：

理论上可分析：我们可以证明算法的解不会差于最优解的某个倍数。
实践中高效：贪心策略通常只需要线性或近线性时间。
结果可接受：在生物学中，“接近最优”往往已经足够有用。

6. 贪心算法与启发式方法的区别

在实践中，“贪心算法”和”启发式方法（Heuristic）“这两个概念有时会被混淆：

维度	贪心算法	启发式方法
选择策略	每步选当前最优	基于经验规则或直觉
理论保证	可能有近似比保证	通常没有理论保证
设计依据	数学上的贪心选择性质	实践中的经验和实验
可分析性	较高	较低

许多生物信息学工具使用的方法严格来说是”启发式”而非”贪心”。例如，BLAST 的种子-扩展策略是一种启发式方法——它不能保证找到所有相似区域，但在实践中效果极好。