一、起源:两类决策思路

1.1 每步取当前最优

有一类问题的输入是一串候选元素与一个约束,输出是候选的一个子集或一个执行顺序,目标函数在整份方案上取极值。区间调度要在若干时间区间中挑出互不重叠的最多区间,任务调度要在一批待办中安排收益最大的组合,布线要在图中选出总权最小的连通边集,编码要对字符分配长短不同的码字使总长度最小。它们的共同形态是:决策可以拆成若干步,每一步只需从当前尚未处理的元素中挑一个。

对这类问题,最直接的想法是每一步都挑当前看起来最好的那一个:区间调度中挑最早结束的区间,任务调度中挑收益最高的任务,布线中挑权最小的边。这样得到的算法通常只有排序加一次线性扫描,代价落在 O(n log n),实现简单,运行极快。这种每步取当前最优的策略就是贪心。

贪心的代价优势来自它不做回顾。它在第 k 步之后就不再考虑前 k−1 步的决策,也不保留任何候选方案集合,因此不需要保存状态、不需要比较方案,空间是 O(1) 至 O(n) 的输入本身。相比之下,任何需要"回头看看另一种可能"的方法都必须在某处保存这些可能性,代价随之上升。

代价优势的另一面是正确性风险。每步取当前最优,只有在当前最优与全局最优一致时才能得到正确答案。这一条件并非普遍成立:0-1 背包按单位价值挑选会在剩余容量无法容纳后续物品时卡住,硬币面值为 {1, 3, 4} 时找零 6 会先取 4 而多付一枚硬币。贪心算法本身只包含一个循环与一条选择规则,错误在形式上完全看不出来,必须单独论证。

1.2 穷举所有可能加剪枝

另一类问题没有可以安全提前确定的选择规则,或者要求给出全部可行方案而不是某一个最优方案。数独要从空格的所有候选数字中找出一组满足全部约束的赋值,N 皇后要在每一行选一个列位置并使任意两个皇后不互相攻击,子集求和要回答哪些子集的和恰好等于目标值。这些问题的最优解无法由局部信息推出,只能枚举全部可能并逐一验证。

枚举的自然载体是树:把决策过程展开成一棵解空间树,第 k 层对应第 k 个决策,从根到叶的一条路径对应一个完整方案,叶子对应候选解。枚举就是深度优先遍历这棵树,走到叶子时检查方案是否可行、是否比当前最优更好,然后退回上一层换一个分支继续。

纯枚举的代价由树的规模决定。n 个元素取或不取产生 2^n 个叶子,n 个元素的全排列产生 n! 个叶子,n 皇后在不加约束时需要搜索 n^n 个位置组合。规模一旦超过二十上下,纯枚举就不可用了(量级与实用边界的对照见 复杂度与算法分析 中量级一节)。

使枚举可用的手段是剪枝:在搜索的中途判断"沿当前分支继续走下去不可能得到答案或不可能比已知最优更好",从而整枝放弃。数独中一个空格没有候选数字时不必继续填完剩下的格子,N 皇后中已放置的两个皇后同列时不必再往下一行递归,装箱问题中当前重量已超出容量时不必再尝试剩余物品。剪枝不改变最坏情况下的解空间规模,但能把实际访问的节点数压缩若干个数量级,这正是回溯在实践中可用的原因。

1.3 两类思路的代价对比与本文边界

两类思路在几个维度上恰好相反:

维度 贪心 回溯
决策依据 局部最优,只依赖当前候选的排序键 枚举全部可能,依赖约束与当前部分解的可行性
典型代价 排序主导的 O(n log n) 或 O(n log n) 加堆操作 最坏为解空间规模(2^n、n!、n^n),实际由剪枝决定
输出 一个最优值或一份最优方案 一个最优解或全部可行解
空间 通常 O(1) 至 O(n) 递归深度乘每层状态,通常 O(n)
前提 需要证明贪心选择性质成立 需要约束可判定、解空间有限
主要风险 选择规则看似合理但结论错误 剪枝不足导致超时,剪枝过强导致漏解

由此可以确定本文的边界:

  • 讨论贪心的适用条件与正确性论证方法,给出常见问题的选择规则与证明思路,以及贪心失效时应当转向的方法;
  • 讨论回溯的搜索树模型、剪枝策略与问题分类模板,把子集、排列、组合、划分、棋盘与图搜索纳入同一套递归框架;
  • 复杂度口径、渐近记号与实测方法沿用 复杂度与算法分析 中的结论,本文只给出各问题自身的量级;
  • 最小生成树与最短路径中已经证明过的贪心性质在 最短路径与最小生成树 中给出,本文只说明它们在贪心框架中的位置;
  • 优先队列的结构与操作代价见 堆与优先队列;图的深度优先遍历与访问标记机制见 图的表示与遍历;抽象数据类型与存储结构的区分见 抽象数据类型(ADT)。

二、原理

2.1 贪心的适用条件

2.1.1 贪心选择性质与最优子结构

贪心算法正确需要两个性质同时成立。

贪心选择性质(greedy-choice property):存在一个全局最优解,它包含算法在第一步作出的那个选择。更一般地,在任意时刻,当前这一步的贪心选择一定属于某个从当前部分解出发的最优解。这一性质保证"提前确定这一步"不会损失最优性。

最优子结构(optimal substructure):作出贪心选择后,原问题化为一个规模更小的同类型子问题,且原问题的最优解由该选择加上子问题的最优解构成。这一性质保证"用同一个规则处理剩余部分"是合法的。

两个性质缺一不可。若只有最优子结构而没有贪心选择性质,问题仍可用动态规划求解,因为子问题的最优解可以被复用;若只有贪心选择性质而没有可复用的子结构,贪心的正确性论证通常也无从展开。区间调度同时具备两者:先确定最早结束的那个区间后,剩余问题是以该区间结束时刻为界、在其余区间中求最大兼容子集,形式完全一致。

2.1.2 局部最优推出全局最优的前提

"局部最优"能否推出"全局最优",取决于目标函数与约束的结构,而不是问题的表面描述。可以归纳为几条判断依据:

  • 目标函数对选择是单调可加的,且约束不因选择而发生性质变化。区间调度的目标是"选中的区间个数",每选一个加一,约束是两两不重叠;已选集合的结束时刻是唯一影响后续可行性的量,因此早期选择只需给出最宽松的余地。
  • 排序键与目标之间存在单调关系。按结束时间升序处理时,"结束越早越有利"是可以证明的(2.2.1 节);按开始时间或按区间长度排序则不具备这一关系。
  • 选择之间不存在交互的边界条件。若一个选择会改变另一个选择的可用性,且这种改变不单调,贪心通常失效。0-1 背包正是这种情况:取走一个物品后剩余容量变小,后续哪些物品可放变成一组离散情形,无法用单一排序键概括。

一个实用的经验判据是:若把贪心规则换一个方向(改排序键、改取大或取小)就能举出反例,说明规则的正反方向都被局部信息决定,此时应怀疑问题的约束中存在非单调交互,需要转向动态规划或搜索。

2.1.3 正确性论证:交换论证

交换论证(exchange argument)是贪心正确性最常用的证明形式,步骤固定:

  1. 设算法按规则选出的第一个元素为 g,设存在一个最优解 O。
  2. 若 O 已经包含 g,则贪心选择性质在这一步成立,递归处理剩余部分。
  3. 若 O 不包含 g,则 O 中包含某个元素 o(选择 g 后被替代的那个)。构造解 O′ = O − {o} + {g},需要证明两件事:O′ 仍然可行(满足约束),且O′ 的目标值与 O 相同或不劣。
  4. O′ 与 O 在第一步的选择上一致,问题规模缩小,重复上述过程即可得到"贪心解不劣于任何最优解"的结论。

交换论证的关键在第 3 步的两条断言。可行性依靠约束的单调性或贪心规则的排序依据:区间调度中"g 的结束时刻不晚于 o",因此把 o 换成 g 后,后面的区间受到的约束只会更松。目标值不劣则依靠问题结构:替换前后选中的元素个数相同,或替换后合并代价只降不升。若某一步无法证明这两条,通常说明贪心规则本身选错了。

2.1.4 正确性论证:归纳法与最优解对比

归纳法与交换论证在结构上接近,但把重点放在步数上:对决策步数 k 归纳,断言"算法前 k 步的选择与某个最优解的前 k 步一致"。基础情形 k = 0 显然成立;归纳步骤用一次局部交换把某个最优解的前 k 步调整为与算法一致,可行性由 2.1.3 中的同一论断保证。归纳结束时得到"存在最优解与算法给出的解完全一致"。

与最优解对比是另一种思路:不构造交换,而是给出一个非负的差距量,证明算法每一步都不增加这个差距。例如会议室安排中的扫描线做法,证明当前同时进行的会议数不超过任何方案的会议室数下界,同时算法恰好用这么多间,于是算法达到下界。

三种方法的适用范围略有差异:

方法 适合的结论形式 依赖的性质
交换论证 贪心解与最优解目标值相等 约束单调,替换后可行性保持
归纳法 贪心解的每一步都能对齐某个最优解 每步的局部交换成立
与最优解对比 算法达到某个可证明的下界 能构造出紧的下界

工程中的实际做法是先用小规模随机数据把贪心解与暴力枚举的最优解对比,确认规则在取值范围内成立,再补写论证。这一顺序的理由是:反例的发现成本远低于证明的写作成本,且发现反例后无需再写证明。

2.1.5 拟阵:贪心正确性的结构性解释

有一类问题可以用统一的结构解释贪心为何正确:拟阵(matroid)。拟阵是一个对 (E, I),E 是元素集合,I 是 E 的若干子集构成的族,满足三条公理:

  • 空集属于 I;
  • 遗传性:若 A 属于 I 且 B ⊆ A,则 B 属于 I;
  • 交换性:若 A、B 属于 I 且 |A| < |B|,则存在元素 x ∈ B \ A 使 A ∪ {x} 属于 I。

I 中的集合称为独立集。对带权拟阵,按权从大到小(或从小到大)扫描元素,只要加入后仍是独立集就加入,得到的极大独立集就是最大(最小)权独立集。这正是贪心算法,其正确性由交换性公理直接给出,不需要针对每个问题单独论证。

图的边集与"不含环的边集"构成图拟阵(graphic matroid):边的森林满足遗传性,交换性由"两片森林中边数多者必有可加入的边"保证。Kruskal 按权升序取边、跳过成环的边,正是拟阵贪心在图拟阵上的实例,环性质(2.2.5 节)是这一结构在具体问题上的表述。任务调度中"在截止期前可安排的任务集合"、匹配问题中"可两两配对的集合"也各自构成拟阵或其变体(带拟阵约束的组合问题需额外处理)。

拟阵的价值在于给出判断方向的直觉:当候选元素的"可用性"只由"是否破坏独立性"决定,且独立集族满足交换性时,按权排序的贪心是安全的。当约束表现为"容量被消耗且消耗量依赖已选元素的组合"(背包的剩余容量),独立集族不满足交换性,贪心随之失效。

2.1.6 失败反例的构造思路

构造反例是确认贪心失效的标准手段,常用四类手法:

  • 用两个元素的取舍制造两难。设置一个"单位价值高但占用大"的元素与两个"单位价值略低但合计更优"的元素,容量恰好只能二选一。0-1 背包的反例多属此类。
  • 利用面值之间的整除关系制造错位。货币系统中引入一个介于两种面值之间的新面值,使贪心先取它后无法用更少的硬币凑齐余数,如面值 {1, 3, 4} 找零 6。
  • 用区间长度与位置分离排序键。构造一个覆盖范围极长但位置靠前的大区间,使按开始时间或按长度排序的规则先选中它。如区间 [0, 10]、[1, 2]、[3, 4],按开始时间排序会先选 [0, 10] 而只能选一个。
  • 利用目标函数的非线性。当目标是乘积、最大最小项或平方和时,局部最优与全局最优的关系常被破坏,需要把目标改写或改用动态规划。

反例一旦找到,说明贪心选择性质不成立,此时的处理方式是:若问题具有重叠子问题与最优子结构,改用动态规划;若状态无法有效压缩,改用带回溯的搜索并施加剪枝(2.3 节、2.7.3 节)。

2.2 典型贪心问题

2.2.1 区间调度

问题:给定若干区间 [sᵢ, fᵢ),选出尽可能多的两两不重叠区间。

选择规则:按结束时刻升序排序,依次扫描,若当前区间的开始时刻不早于上一个选中区间的结束时刻则选中。

证明思路(交换论证):

  1. 设所有区间中结束最早的是 g,其结束时刻为 f(g);设某个最优解中第一个区间为 o,其结束时刻为 f(o)。由 g 的定义有 f(g) ≤ f(o)。
  2. 把 o 替换为 g。替换后第一个区间的结束时刻不晚于原值,任何原本与 o 兼容的区间都与 g 兼容,可行性保持;区间个数不变,目标值不劣。
  3. 于是存在一个最优解以 g 为第一个区间。剩余问题是在结束时刻不早于 f(g) 的区间中求最大兼容子集,与原问题同形,递归使用同一条规则即可。

排序键的选择是这一问题最容易出错的地方:按开始时刻排序会先选中一个开始很早但结束很晚的区间;按区间长度排序会先选中一个短但位置居中的区间,两者都能给出反例。

2.2.2 活动选择与会议室安排

活动选择是区间调度的别名,规则与证明完全一致,差别只在输出形式:区间调度输出个数,活动选择输出选中的活动序列。

会议室安排换了一个目标:给定若干会议的时间区间,求容纳全部会议所需的最少会议室数量。这一问题的结论是:

最少会议室数 = 任意时刻同时进行的会议数的最大值。

两个方向都容易看出:任意时刻重叠的 k 个会议必须占用 k 间不同的会议室,因此最少数量不低于最大重叠数(下界);按某一间会议室安排不重叠的会议序列可以在重叠数给定的前提下依次安排,从而不超过最大重叠数(构造)。

实现上有两种等价做法:

  • 扫描线。把所有区间拆成"开始"(+1)与"结束"(−1)两个事件,按时刻排序(同一时刻先减后加),扫描前缀和,最大值即答案。代价 O(n log n),空间 O(n)。
  • 按开始时刻排序加小顶堆。堆中保存已占用会议室的结束时刻,扫描到新会议时若堆顶(最早空闲)不晚于当前开始时刻则复用一个会议室(弹出堆顶)再压入新的结束时刻,否则新开一间;扫描结束时堆的大小即答案。代价 O(n log n),空间 O(n)。

两种做法都只做了一次排序与一次线性推进,是扫描线类贪心的典型形态。会议室数这一量小顶堆的用法与 堆与优先队列 中"按到期时间维护最值"的模式相同,区别只在堆保存的是资源的释放时刻。

2.2.3 找零与货币系统

问题:用面值集合 D 中的硬币凑出金额 A,使硬币枚数最少。按面值从大到小贪心是常见做法,它的正确性完全取决于面值集合。

规范系统(canonical system):若对任意金额,按面值从大到小的贪心都给出最优解,则称该货币系统是规范的。多数真实货币系统是规范的,例如 {1, 5, 10, 25} 与 {1, 2, 5, 10, 20, 50},因此日常找零用贪心即可。

反例:面值集合 {1, 3, 4} 中凑金额 6。贪心先取 4,剩余 2 只能取两个 1,共 3 枚;最优解是 3 + 3,共 2 枚。此处贪心失效的原因是面值之间失去了整除链:4 不是 3 的倍数,取走 4 后剩余金额无法由较大的面值高效填充。

判定一个货币系统是否规范有基于"贪心只在有限个区间上可能出错"的算法,工程上更常用的做法是:面值集合固定且经过验证时用贪心,面值集合可配置或含任意值时用动态规划。动态规划解法以 dp[a] 表示凑出金额 a 的最少硬币数,转移为 dp[a] = 1 + min{dp[a − d]},复杂度 O(A · |D|),与金额成正比。

贪心有效的充分条件之一是"每个面值是前一个面值的倍数链"(如 {1, 5, 25}),此时大面值的取用不会破坏剩余金额的最优结构。倍数链不是必要条件(真实货币系统中 10 与 25 不构成倍数关系但仍规范),因此不能反推。

2.2.4 哈夫曼编码与合并代价

问题:给一组带频率的字符分配二进制码字,使编码后的总长度最小;等价地,给定 n 个权值,每次合并两个权值并付出两者之和的代价,使总代价最小。

选择规则:每次取出当前最小的两个权值合并,把和放回集合。使用的结构是小顶堆,代价 O(n log n)。

结论是总代价等于加权外部路径长度(WPL),即每个权值乘以其在树中的深度之和。正确性论证分两部分:

  • 贪心选择性质:最优编码树中,频率最小的两个字符必然位于最深层且互为兄弟。若不然,可以把更深的叶子(权更小)换到这两个字符的位置;交换后总代价不增(交换论证,利用"较小的权放在较深处"这一不等式)。
  • 最优子结构:把这两个字符合并成一个频率为两者之和的新字符后,问题规模减一,原问题的最优解与子问题的最优解相差一个固定量(两者频率之和,即这次合并的代价)。

实现细节与复杂度:

  • 用小顶堆时总代价 O(n log n),其中 n − 1 次合并各含两次弹出与一次插入,每次 O(log n)。
  • 若输入权值已有序,可用两个队列(一个存原始权值,一个存合并结果,两者各自有序)在 O(n) 内完成合并,加上排序的总代价为 O(n log n)。
  • 权值相同时合并顺序不唯一,编码不唯一,但最优总代价唯一。
  • 同一套机制可用于"合并果子""文件合并""石子合并(相邻约束除外)"等最小合并代价问题。

需要区分的是:哈夫曼编码解决的是无前缀约束下的最短编码,其解构成前缀码;若要求定长编码或要求码字长度受限,问题与解法都不同。

2.2.5 最小生成树的贪心性质

最小生成树的目标是在连通无向图中选出总权最小的 n − 1 条边使全体顶点连通。它同时也是贪心的经典实例,其正确性由两条结构性定理给出(详细表述、证明思路与算法实现见 最短路径与最小生成树 中最小生成树一节):

  • 割性质:对任意割,横跨该割的权最小的边一定存在于某棵最小生成树中。
  • 环性质:对任意环,该环上权最大的边一定不出现在任何最小生成树中。

两条性质分别对应两种算法:

算法 视角 每步的贪心选择 依赖的性质 实现结构
Prim 从顶点集合扩张 连接"树内"与"树外"的最小边 割性质 距离数组或优先队列
Kruskal 从边集合筛选 按权升序取边,若不成环则加入 环性质(图拟阵) 排序加并查集

Kruskal 是 2.1.5 节中图拟阵贪心的直接实例:边按权排序后依次尝试,只要加入后仍是无环边集(独立集)就保留。并查集用于判定"加入后是否成环",其路径压缩与按秩合并的实现见 线段树与并查集。Prim 的每一步是"当前割的最小边",其正确性与 Dijkstra 的取最小操作同构,区别在于比较的键:Dijkstra 比较源点到该点的累计距离,Prim 比较该点到树中任意点的单边权。

2.2.6 Dijkstra 的贪心选择

Dijkstra 用贪心求解非负边权图上的单源最短路径(推导与复杂度见 最短路径与最小生成树 中 Dijkstra 一节)。它在主循环中反复执行同一动作:从尚未确定最短距离的顶点中取出当前距离最小的一个,标记其距离为最终值,并用它松弛所有出边。

贪心选择性质在这一问题中的形态是:若所有边权非负,则当前距离最小的未确定顶点的距离不可能再被后续路径改进。理由是任何经过其他未确定顶点的路径都要先付出一个非负的额外边权,总长度不可能小于当前的最小值。非负边权这一前提不可去掉:一旦存在负权边,"绕远路反而更短"成为可能,本地最小不再等于全局最小,算法给出错误结果,此时需改用 Bellman-Ford 或 Johnson 一类方法。

Dijkstra 与 Prim 的对比也说明了贪心的一个特点:同一个"每步取最小"的外壳,换掉比较键就换了问题。两者的主循环结构完全相同,堆的实现细节可以复用(堆的删除最值与减少键语义见 堆与优先队列)。

2.2.7 排序不等式与均摊分配

重排不等式(排序不等式):对两组升序排列的实数 a₁ ≤ a₂ ≤ … ≤ aₙ 与 b₁ ≤ b₂ ≤ … ≤ bₙ,有

a₁b₁ + a₂b₂ + … + aₙbₙ  ≥  任意乱序配对的和  ≥  a₁bₙ + a₂bₙ₋₁ + … + aₙb₁

即同序相乘之和最大,逆序相乘之和最小。证明用交换论证:若配对 (aᵢ, bⱼ) 与 (aₖ, bₗ) 满足 aᵢ ≤ aₖ 且 bⱼ ≤ bₗ 却交叉配对,则交换为同序配对后有

(aᵢbⱼ + aₖbₗ) − (aᵢbₗ + aₖbⱼ) = (aₖ − aᵢ)(bₗ − bⱼ) ≥ 0

每次交换不降低总和,反复交换得到同序配对,结论成立。

这一不等式给出一类"配对"问题的贪心规则:要使总和最大就同向排序配对,要使总和最小就反向排序配对。会议室分配、机架资源与任务的配对、折扣与成本的分摊、单位成本与数量的分配都属于此类。它的实用价值在于:这类问题的最优规则可以一次性写成排序后顺序或逆序配对,而无需为每一对单独决策。

2.2.8 任务截止时间与收益安排

一类调度问题:给定若干任务,每个任务有截止时刻与所需时长,求最多能完成多少个任务或最大总收益。

单位时长、最大化完成任务数:每个任务占用一个单位时间,需在截止时刻前完成。规则是按截止时刻升序排序,依次尝试安排;若当前已安排任务数未超过截止时刻则可安排,否则放弃。更强的做法是用并查集或有序表维护"每个时刻之前最近的可用空位",把任务安排在最靠后的可用空位,从而为后续任务留出余地。这一做法同样是贪心:按截止时刻处理保证紧迫的任务优先占用时间资源。

带收益、最大化总收益:按截止时刻升序处理,用小顶堆保存已选任务的收益;当已选任务数超过当前截止时刻允许的容量时,弹出收益最小的任务(放弃它)。堆的大小始终是当前可行的最大任务数,堆中收益之和在每一步都是该前缀规模下的最大收益。这里的堆同时承担"保存已选集合"与"撤销最差选择"两个职责,是贪心与优先队列配合的标准形态。

放弃已选元素的合法性来自一个交换论证:若某一步必须淘汰一个任务,淘汰收益最小的那个不会使任何后续决策变得不可行(被淘汰任务的截止时刻不晚于后续任务,占用同一个时间槽的机会成本相同),因此局部淘汰最小收益是安全的。

2.3 贪心与动态规划的边界

2.3.1 反例:背包与硬币

贪心失效的两类经典反例都指向同一个原因:当前选择会以非单调的方式改变后续可用资源。

分数背包与 0-1 背包。分数背包允许取物品的一部分,按单位价值降序贪心取满容量即可,正确性由"最后取的那件物品的单位价值必然最低"这一交换论证给出。0-1 背包不允许分割,按单位价值降序贪心会失败:容量 10,物品为 (重量 6, 价值 7)、(重量 5, 价值 5)、(重量 5, 价值 5),单位价值依次为 1.17、1、1,贪心先取第一件后剩余容量 4,总价值 7;最优解取后两件,总价值 10。差别在于不可分割性使"剩余容量能装什么"成为一组离散情形。

货币系统。2.2.3 节的 {1, 3, 4} 找零 6 是同类反例:取走面值 4 之后,剩余金额 2 的最优结构与大面值无关,而这一步的信息在贪心规则中无法体现。

两类问题的正确解法都是动态规划:0-1 背包以容量为状态维,dp[c] 表示容量 c 下的最大价值;找零以金额为状态维。状态设计、转移方程与两种实现方式的取舍见 动态规划。它们的共同点是子问题由"剩余资源的数量"参数化,且该数量在每一步都会变化。当状态维度只有一维且取值有限时,动态规划的代价是 O(n · A),在 A 较大时可进一步用单调队列、二进制拆分或状态压缩优化。

贪心与动态规划的边界可以表述为:

判据 倾向贪心 倾向动态规划
选择是否改变后续可行域 不改变,或改变方式单调 改变方式依赖已选组合
是否需要保留多个候选状态 不需要,唯一部分解即可 需要按状态维保留最优值
排序键能否概括选择优先级 能,且可证明 不能,选优依赖剩余资源
约束结构 拟阵或简单容量型 组合约束、多资源约束

实践中有一条低成本路径:先写出暴力枚举或动态规划作为正确性基准,用它在小规模随机数据上验证贪心规则;确认一致后再证明,或直接在小规模上用动态规划、在大规模上用贪心。

2.3.2 贪心加优先队列与 DP 加优化

两类方法常在同一问题上交替出现,区别在于保留多少状态。

  • 贪心加优先队列:部分解只有一个(当前最优的已选集合),但需要支持"插入候选后取出最值"和"撤销最差选择"。堆在此处既是数据结构也是算法的一部分。2.2.8 节的收益调度、多路归并、Top K 都属于这一形态。
  • 动态规划加优化:部分解按状态维保留一组最优值,优化手段为滚动数组(降低空间)、单调队列或斜率优化(降低转移代价)、状态压缩(把集合状态压成位掩码)。

二者的关系可以这样理解:贪心加堆是"只保留一个部分解,但允许局部反悔";动态规划是"保留全部可达状态的最优值"。当反悔的粒度足够小(只需替换一个已选元素)时,堆的形式就能覆盖动态规划的效果;当需要同时调整多个已选元素时,必须回到状态维。

2.3.3 可后悔贪心与反悔堆

可后悔贪心(regret greedy) 指在贪心过程中允许撤销先前选择的变体,其典型实现是维护一个堆,堆中保存已选元素;处理新元素时,若替换堆中某个元素能得到更优的局部结果,则执行替换。判定替换的结构可以写成:

若新元素与堆中某元素的"代价差"使当前总量下降(或收益上升),则弹出堆顶(最差者),改为压入新元素

2.2.8 节的收益调度是这一模式的直接应用。另一类常见情形是"带惩罚的选择":每个元素有收益与代价,需要选出若干使净收益最大且满足次序约束,此时堆中保存已选元素的代价,遇到冲突就丢弃代价最大者。可后悔贪心的使用前提是替换操作的正确性可以通过交换论证局部化:任意一次替换只比较两个元素,不牵动更多已选元素,这要求问题的约束能写成"占用同一类资源"的形式。

反悔堆与动态规划在效果上部分重叠,选择依据是替换窗口的大小:窗口为常数(只需与最差元素比较)时用堆;窗口需要回溯多个元素时用动态规划。

2.4 回溯的搜索树

2.4.1 解空间树与深度优先枚举

回溯把问题的决策过程展开成一棵解空间树:

  • 根表示尚未作出任何决策的初始状态;
  • 第 k 层的一条边表示第 k 个决策的一种取值;
  • 从根到第 k 层节点的路径表示一个部分解;
  • 叶子表示一个完整方案。

按树形分类,常见三类:

解空间树 每层的分支 叶子数 典型问题
子集树 取 / 不取 2ⁿ 子集枚举、0-1 背包、子集和
排列树 剩余未用元素中的任意一个 n! 全排列、旅行商、作业排序
组合树(可重排列树) 从当前位置起的元素 C(n, k) 或含重复的多种形态 组合数枚举、组合总和、找零方案

遍历方式为深度优先:沿一条路径一直走到叶子或剪枝点,再退回上一层换分支。深度优先与回溯天然匹配,因为"退回上一层"对应递归调用返回,调用栈本身就保存了路径。

与图的深度优先遍历(见 图的表示与遍历)的差别在于是否撤销状态:图遍历的访问标记一旦置位就不再清除,保证每个顶点只访问一次,代价 O(V + E);回溯的路径状态在返回时必须撤销,因为同一个元素可以在不同的分支中以不同位置出现,代价由解空间规模决定,而非 O(V + E)。

2.4.2 路径、选择列表与结束条件

任何回溯算法都由三部分构成,可以逐项对照检查:

  1. 路径(path):已经作出的选择序列,即当前的部分解。它决定了现在处于解空间树的哪个节点。
  2. 选择列表(choices):当前节点下还可以作出的选择。它由路径与问题约束共同决定,通常表现为"从某个下标之后继续取"(组合)、"尚未使用过的元素"(排列)或"满足约束的取值"(棋盘)。
  3. 结束条件(terminal):路径长度达到要求、目标和满足、或者没有可行选择时停止递归。结束条件既包括"收集解"的出口,也包括"剪枝返回"的出口。

三者的关系决定递归函数的形态:

backtrack(路径, 选择列表):
    若 满足结束条件:
        记录结果(或更新最优解)
        返回
    若 不可能继续(剪枝条件成立):
        返回
    对 选择列表 中的每个选择:
        做选择(修改路径与辅助状态)
        backtrack(新路径, 新的选择列表)
        撤销选择(恢复路径与辅助状态)

选择列表的表示方式影响剪枝的写法:用起始下标 start 表示"只能从 start 之后取"适用于组合与子集;用布尔数组 used 表示"任意未用元素"适用于排列;用行号或位置指针适用于棋盘与网格。

2.4.3 做选择与撤销选择的对称性

回溯代码中最容易出错的地方是"做选择"与"撤销选择"必须严格对称:

  • 修改了哪些状态,就要在同一个位置恢复哪些状态;
  • 状态的类型一致(布尔标记配布尔复位,计数配减一,位掩码配按位与非);
  • 修改与恢复在同一个作用域内成对出现,中间不夹带 return、异常或提前 continue;
  • 对递归返回后仍需读取的状态,检查是否被更深层的调用改动过。

这一要求可以用不可变性的视角重新理解:若把路径当作不可变值传递(每层新建一份路径副本),则不存在需要撤销的状态,代码天然正确,代价是每层一次 O(k) 的复制,总代价上升。若共享一份可变路径,则必须严格撤销,收益是 O(1) 的增删,风险是遗漏撤销。两种写法在不同问题的取舍见 3.2 节,共享状态与不可变对象的一般权衡见 Java 并发编程 中不可变对象一节。

另一个相关的正确性要求是收集结果时必须拷贝。若把路径对象直接放入结果集,后续的撤销会让结果集中的对象变为空列表,所有结果指向同一个对象。

2.5 剪枝与优化

2.5.1 可行性剪枝与最优性剪枝

可行性剪枝在"沿当前分支继续不可能得到可行解"时返回。判据来自问题的约束:

  • 剩余元素的总和已经不足以达到目标和(子集和、组合总和);
  • 当前部分解已违反约束(皇后互相攻击、任务超出截止期、容量为负);
  • 当前位置没有任何合法取值(数独空格候选集为空)。

可行性剪枝要求约束可单调判定:一旦违反,继续加深不可能恢复。若约束可能被后续选择修复,则不能剪。

最优性剪枝(分支限界) 在"沿当前分支继续不可能优于已知最优解"时返回。做法是给出当前部分解的下界或上界估计:

  • 若已知一个可行解的目标值为 best,而当前节点能取得的最优值不可能优于 best,则剪枝;
  • 估计必须是乐观的(对最小化问题给出下界估计,对最大化问题给出上界估计),估计过于保守会削弱剪枝效果,估计过于激进会剪掉最优解。

分支限界与回溯的区别主要在搜索顺序与剪枝依据:回溯是深度优先且以求全部解或第一个解为目标,分支限界通常按估计值优先扩展最有希望的节点(配合优先队列),目标是尽快找到并证明最优解。

2.5.2 重复状态剪枝与对称性

同一状态可能由多条不同路径到达,重复搜索会带来指数级的浪费。三类处理方式:

  • 记忆化:以状态为键缓存"从该状态出发的结论"(最优值或可行与否)。适用于状态可压缩为少量参数的情形,是回溯向动态规划靠拢的形式(2.7.3 节)。键的构造需注意参数顺序无关时应对参数排序或使用集合结构。
  • 对称性剪枝:若若干状态互为对称(如棋盘的旋转与镜像、同一批任务的等价排列),只搜索其中一个代表。做法是固定某个元素的相对次序,例如"第一个位置只放编号最小的等价元素"。
  • 路径去重:在同一层的选择中跳过取值相同的候选(2.5.4 节),避免生成内容相同的结果。

2.5.3 排序后剪枝

先排序再搜索可以显著增强剪枝:

  • 同类元素相邻,便于去重。组合与子集问题中,排序后相同的取值连在一起,可以用"与前一个位置取值相同则跳过"判定重复,无需哈希集合。
  • 确定提前终止条件。组合总和中若候选值已大于剩余目标,由于升序排列,后续候选只会更大,可以在循环中直接 break(而不是 continue),整段剪掉。
  • 先处理"更重"的元素。装箱、划分、装载类问题中先放大元素,能尽早填满容量或尽早暴露不可行,减少后续分支;反之,若目标是尽快构造可行解,先放约束最强的元素(候选最少的格子、使用次数受限的元素)效果更好。
  • 为最优性剪枝提供有序的搜索顺序。按单位价值或估计值降序搜索,能在早期得到较好的可行解,使后续的最优性剪枝更有效。

用"先大后小"还是"先小后大"由目标决定,没有通用结论:最小化数量的划分问题适合先放大的,避免小元素占用零散空间导致后续无法填充;需要快速得到任意可行解或解的分布较均匀时,先放小元素可以更早进入深层。

2.5.4 位掩码与集合去重

位掩码用一个整数的第 i 位表示第 i 个元素是否被使用,适合元素个数在 64 以内的场景:

int n = nums.length;
for (int mask = 0; mask < (1 << n); mask++) {          // 枚举全部子集,共 2^n 个
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) { /* 元素 i 在子集中 */ }
    }
}

位掩码的优点与限制都很明确:

  • 判断与修改是 O(1) 的位运算,适合做状态键与记忆化的键;
  • 集合运算(并、交、差、子集判断)由位运算直接表达,如"与目标集合无交集"为 (mask & target) == 0,"mask 是全集 i 的子集"为 (mask & ~i) == 0;
  • 元素个数超过 64 时无法用原生整数表达,需要改用 bitset 或布尔数组,判定代价随之上升。

枚举一个集合的全部子集有专门写法,代价是 3ⁿ 级别的总和(对每个子集枚举其子集):

for (int s = mask; ; s = (s - 1) & mask) {   // s 依次取 mask 的全部子集
    // 处理子集 s
    if (s == 0) break;
}

去重的两类写法对应两类重复来源:

  • 同层重复(同一父节点下的兄弟分支取值相同):排序后判定 i > start && nums[i] == nums[i-1],跳过。适用于组合与子集。
  • 同枝重复(同一路径中元素顺序不同导致排列重复):排序后判定 nums[i] == nums[i-1] && !used[i-1],跳过。适用于带重复元素的排列。

两者的判定条件之所以不同,是因为同层重复只关心"当前层已经尝试过哪个取值",同枝重复还要确认"前一个相同元素是否仍在当前路径中"。

2.5.5 迭代加深与双向搜索

迭代加深(IDDFS) 按深度上限逐轮加深:先限制深度为 1 搜索,再限制为 2,依次递增,直到找到解。它把广度优先的"层序保证"与深度优先的"低空间开销"结合起来,空间只需 O(d)(d 为解所在深度)。代价是浅层节点被重复访问,但由于树的规模按层指数增长,重复访问的总量与最后一轮相当,不改变量级。适用于解深度未知且状态空间宽大的搜索,例如最短步数类问题(每次操作改变状态)。

双向搜索从起点与目标同时展开,两侧在中间相遇时即得到解。若单向广度优先需要展开 O(b^d) 个节点(b 为分支因子,d 为解的距离),双向搜索只需约 O(b^(d/2)),对分支因子大于 1 的问题收益显著。实现上需要两侧都保存已访问状态,并在扩展一侧时检查是否出现在另一侧,空间代价高于单向深度优先。

两者共同的特点是改变搜索的组织方式而不改变最坏情况下的解空间规模:迭代加深把空间从 O(b^d) 降到 O(d),双向搜索把节点数从 O(b^d) 降到 O(b^(d/2)),都是工程上常用的可行性手段。

2.6 问题分类模板

2.6.1 子集、排列与组合

三类最基础的枚举问题可以统一在同一个递归框架下,差别只在选择列表与结束条件:

问题 路径含义 选择列表 结束条件 解的数量
子集 已选元素集合 从 start 起的每个元素(取或不取) 每个节点都是一个解 2ⁿ
排列 已排定前缀 所有未使用元素 路径长度等于 n n!
组合 已选元素集合 从 start 起的每个元素 路径长度等于 k C(n, k)

三者的递归写法可以写成同一形态,用参数区分:

// 组合/子集:用 start 控制"只能向后取",天然不重复
void dfs(int start, ...) {
    // 子集在此处收集解;组合在路径长度等于 k 时收集
    for (int i = start; i < n; i++) {
        // 选择 nums[i]
        dfs(i + 1, ...);
        // 撤销
    }
}

// 排列:用 used 控制"任意未用元素"
void dfs(...) {
    if (path.size() == n) { 收集解; return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        // 选择 nums[i]
        dfs(...);
        // 撤销
    }
}

组合与子集使用 start 而不用 used,是因为组合不区分顺序,start 保证每个元素组合只被生成一次;排列区分顺序,必须允许已放置元素之外的所有元素参与选择。

2.6.2 划分问题

划分问题的目标是把集合切成若干满足约束的部分,与前三类的差别在于解由多个子集合构成。常见形态:

  • 等和划分:判断能否把数组分成两个和相等的子集,等价于寻找和为总和一半的子集,用子集树加可行性剪枝(剩余元素不足则剪);
  • k 等分:把数组分成 k 个和相等的组,需要同时维护 k 个部分和,并用"桶按剩余容量降序尝试""已填满的桶不再作为选择"等对称性剪枝;
  • 装箱:把物品装入容量固定的若干箱子使箱子数最少,属于 NP 困难问题,精确解需回溯加最优性剪枝,实际常用首次适应递减(FFD)等近似贪心;
  • 回文划分:按位置切分并判定每段是否回文,用预处理好的回文判定表加剪枝。

划分问题的剪枝强度决定了可行性:等和划分在 n = 20 上下仍可精确求解,装箱问题的精确解在 n 超过三四十后基本不可行,此时应当使用近似算法并接受"可行解而非最优解"的结论(近似与启发式的理论边界见 复杂度与算法分析 中理论的边界一节)。

2.6.3 棋盘问题:N 皇后与数独

棋盘问题的共同结构是在网格上逐格或逐行赋值,约束作用于行列与局部区域。处理方式是把约束编码为数组或位掩码,在"做选择"时更新、在"撤销"时恢复。

N 皇后:逐行放置,每行一个皇后。约束有三类:列不重复、主对角线不重复(row + col 相同)、副对角线不重复(row − col 相同)。用三个布尔数组或位掩码表示三类占用,放置与撤销只修改三个位置,判定为 O(1)。搜索空间从 nⁿ 降到实际约 n! 级别(每行至多 n 个候选,且随放置过程快速减少)。对称性剪枝可以进一步缩小:整体对称(左右镜像)的解成对出现,只搜索第一行左半部分的列可减半搜索量。

数独:逐格填数,约束为行、列、九宫格内数字不重复。用三个长度为 9 的位掩码表示各行列宫的已用数字,候选集为三个掩码取反后的交集。两种强化手段:

  • 最小剩余值启发(MRV):优先选择候选数最少的空格,使搜索树尽量窄;
  • 约束传播:每填一个数就更新三个掩码,某个空格候选集为空时立即回溯,而不是等到填到那一格才发现。

数独的最坏复杂度是指数级,但配合上述两个手段,标准九宫格数独的求解通常在毫秒级完成,节点数远小于理论规模。这也是"最坏复杂度与实际表现差异极大"的典型例子。

2.6.4 图搜索:路径与连通块

回溯在图上的应用分两类,区别在于是否撤销访问标记:

  • 枚举路径:求两点之间的所有简单路径、求最短路径(在无权图上与广度优先等价)、求满足某种约束的路径。此时访问标记必须在返回时撤销,否则同一条路径的不同延伸分支之间会互相干扰。代价与路径数量成正比,最坏为指数级。
  • 连通块与可达性:求连通分量、判断可达、求区域的边界。此时访问标记不撤销,每个顶点只访问一次,代价 O(V + E)。遍历的实现、访问标记的时机与前驱记录见 图的表示与遍历 中深度优先一节。

回溯在这两类问题中的用途不同:前者用于枚举解空间,后者是遍历结构本身。区分方法是问一句"同一个顶点是否需要被不同的解重复使用":需要,则撤销标记;不需要,则保留标记。

图的搜索与动态规划、贪心的关系同样值得注意:最短路在非负权图上用贪心(Dijkstra),在有向无环图上用动态规划(拓扑序松弛),在状态含环且需求全部解时用回溯。方法的切换依据是问题需要"一个最优值"还是"全部可行方案"。

2.6.5 去重策略的统一处理

把去重规则集中成一张对照表,可以避免在每道题里重新推导:

问题类型 重复来源 预处理 判定条件
子集(含重复元素) 同一层选到相同取值 排序 i > start && nums[i] == nums[i-1] 则跳过
组合总和(含重复元素) 同上 排序 同上,并可对超和目标提前 break
全排列(含重复元素) 相同取值的元素互换位置 排序 nums[i] == nums[i-1] && !used[i-1] 则跳过
划分成多个组 组之间次序无关 排序 只在"与已有组等价"时跳过,或固定桶的尝试顺序
棋盘(对称) 旋转与镜像等价 无 固定等价类中一个代表(如第一行只取左半)
路径枚举(有环图) 同一顶点重复进入 无 路径内 visited 标记,进入置位、返回复位

统一的判据是:先确定"两个解在什么条件下被视为相同",再把该条件翻译成搜索树上的"某个分支无需展开"。翻译完成后才选择排序、掩码或哈希表等具体手段。

2.7 复杂度与可行性

2.7.1 解空间规模估算

在写下搜索代码之前,应先用最坏情况的叶子数估算可行性,可处理的规模上限见 复杂度与算法分析 中量级一节。

解空间形态 叶子数 每秒 10^8 次操作下的大致可处理规模
子集枚举 2ⁿ n 约 20 至 25
排列枚举 n! n 约 11 至 12
组合枚举 C(n, k) 与 k 有关,n = 30、k = 15 时约 1.6×10⁸
每格 m 种取值的网格 m^(格数) 数独为 9^81,必须依赖剪枝
图的简单路径枚举 指数级 与图的结构强相关,稀疏图上可能远小于上界

估算时要注意两类常见偏差:一是把"剪枝后的规模"当作解空间规模,导致对最坏输入的判断失误;二是把"结果数量"当作"搜索节点数",实际访问的节点数通常是解数量的若干倍(每层循环的分支开销)。

2.7.2 剪枝效果与最坏情况

剪枝改变的是实际访问节点数,不改变最坏复杂度。两者的差距可以很大:

问题 最坏复杂度 典型实践表现 主要剪枝手段
N 皇后 上界 O(n!) n = 8 时节点数在千级 列与对角线标记、对称性
数独 9^81 的上界 标准题毫秒级 位掩码、最小剩余值、约束传播
等和划分 2ⁿ n = 20 左右可精确求解 排序、剩余和不足即剪、对称性
0-1 背包(精确) 2ⁿ 小规模可精确,大规模用 DP 或分支限界 按单位价值排序、分数背包上界
装箱(精确) 2ⁿ 级 n 超过三四十基本不可行 先放大物品、下界估计

剪枝效果的测量方式是统计搜索过程中访问的节点数与剪枝命中次数,把它们与解空间上界对比,而不是只看运行时间。计数本身有开销,适合在测试与诊断时开启;不同剪枝策略的实测对比需要遵循基准测试的规范,避免把测量噪声当作策略差异(见 3.4 节与 JMH 微基准测试)。

2.7.3 方法选择:DP、贪心与搜索加记忆化

在同一问题上,三种方法的适用条件可以按下列顺序判断:

  1. 贪心:能给出一个排序键或单一选择规则,并且该规则下的贪心选择性质可以用交换论证或拟阵结构证明。适用于区间调度、会议室、哈夫曼、最小生成树、Dijkstra、排序不等式类配对、收益调度(配堆)。代价最低,通常 O(n log n)。
  2. 动态规划:问题具有最优子结构,但选择会改变剩余资源的形态(如背包的剩余容量),需要按状态维保存最优值。代价为状态数与每状态转移代价的乘积,常见 O(n·A)、O(n²)、O(2ⁿ·n)。
  3. 搜索加记忆化:状态空间较大、无法直接用表格填,但"从某状态出发的结论"可以被复用。记忆化的键即状态,命中时直接返回。这一形态介于回溯与动态规划之间,是所有解法中最通用的形态。
  4. 纯回溯:需要输出全部可行方案、或状态无法压缩、或约束需要逐步构造才能判定。此时必须配合剪枝,并对最坏规模做出可接受的估计。

四者的关系是表达能力与代价的递增序列:纯回溯能表达一切但代价最高;加上记忆化后相同状态不再重复;再加上最优子结构就得到动态规划;当状态维退化为一维且选择规则可证明时,动态规划退化为贪心。

工程上的判断进一步考虑两点:一是是否需要全部解(需要则回溯不可替代,因为动态规划只保留一个最优值);二是是否需要最优性保证(不需要时可用近似贪心或启发式,代价下降若干数量级)。


三、实现

3.1 贪心实现要点

排序键的选择。 贪心代码的核心是"按什么排序",而排序键的错误在运行结果上往往只表现为"结果偏小或偏大",不易察觉。选键时应当从证明中反推:交换论证里用到了哪个量的单调性,排序键就该是哪个量。区间调度用结束时刻,收益调度用截止时刻,哈夫曼用权值,Kruskal 用边权,均摊分配用数值本身。

排序的稳定性与实现。 键相同时元素之间是否需要保持原次序,取决于问题。需要稳定语义时,可在比较器中追加一个次序键(插入序号),把比较结果变为全序;Java 中 Arrays.sort 对对象数组使用稳定排序,对基本类型数组(如 int[])使用不稳定排序,同一问题的两种写法可能得到不同结果,这一点在需要输出具体方案时会影响正确性。

比较器的契约。 比较器必须满足自反、反对称、传递,并保持与等值判定一致。比较结果的实现应使用 Integer.compare(a, b) 一类写法,而不是 a - b(差值可能溢出)。这些要求的完整表述与后果见 堆与优先队列 中比较器与相等元素一节,比较器与自然序在有序集合中的契约见 Java 集合框架实现原理 中比较器与自然序一节。

优先队列的配合。 贪心需要"每步取当前最优候选"时,用优先队列代替每次重新排序:

  • 最小化问题默认使用小顶堆(Java 的 PriorityQueue 默认即小顶堆),最大化问题传入 Comparator.reverseOrder();
  • 需要"取最值后还需要定位并删除任意元素"时,普通堆不提供该能力,需改用索引堆或惰性删除;
  • 需要"撤销最差选择"时,堆中保存的元素应与决策对象一一对应,并在替换时同步更新外部状态(如已占用容量)。

一次排序与多次排序的取舍。 贪心的排序通常只做一次,之后线性推进;若在循环内部反复排序,总代价会退化到 O(n² log n) 量级。识别这类退化的方法是检查循环体内是否存在隐藏的线性或对数复杂度调用。

3.2 回溯实现要点

递归框架。 回溯的递归函数一般由三段构成:结束条件判断、候选枚举循环、递归调用与状态恢复。

void backtrack(状态, 选择起点):
    if 满足收集条件: 收集结果(拷贝); return
    if 剪枝条件成立: return
    for 每个候选:
        更新状态
        backtrack(状态, 新的选择起点)
        恢复状态

状态恢复的正确性。 恢复操作必须与更新操作严格对应,且发生在递归返回之后、下一次循环迭代之前。常见缺陷有三类:

  • 提前 return 绕过了恢复,导致状态被上一层的兄弟分支继承;
  • 恢复语句写在了 if 分支内部,某些路径上没有执行;
  • 更新了多个状态(路径列表、used 数组、部分和、可用集合)而只恢复其中一部分。

可变共享状态与不可变视角。 两种写法各有适用场景:

写法 状态恢复 每层代价 适用场景
共享一份可变路径,进入时增、返回时删 必须手动严格撤销 O(1) 路径长度大、结果数量多时优先
每层传入新的不可变路径副本 无需撤销 O(k) 复制 逻辑简单优先、路径短、并发使用同一份结果的场景

第二种写法的正确性由不可变性直接保证,代价是复制开销与分配压力;第一种写法性能更好但正确性依赖人工对称。共享可变状态在并发场景下不可复用(同一份路径不能同时被多个搜索任务使用),这一约束与 Java 并发编程 中关于共享状态与不可变对象的讨论一致。

去重与排序预处理。 需要在"同一层跳过重复取值"的问题必须先排序,使相同取值相邻;未排序时判定条件不成立,去重失效。排序本身是 O(n log n),在解空间规模指数级的问题中可以忽略。

剪枝条件的放置位置。 位置选择影响剪枝的粒度:

  • 递归入口判断:进入函数后立即检查,能一次性剪掉整棵子树,适合依赖路径长度、部分和、剩余元素总数的条件;
  • 循环内判断:在枚举候选时逐个判定,能跳过具体取值,适合"当前候选不合法"的条件(超和、与已选冲突、与前一取值相同);
  • 排序配合的提前终止:升序排列下,若当前候选已超出可行范围,则后续候选同样超出,用 break 而非 continue 整段剪掉。

判断条件放在越靠近叶子的位置,剪掉的节点越少;放在越靠近根的位置,越可能因为估计过于保守而剪掉最优解。实际取舍是"条件可判定性与估计紧度"的权衡。

3.3 典型实现

3.3.1 区间调度与会议室数量

区间调度:按结束时刻升序排序,一次线性扫描即可。

public int maxNonOverlapping(int[][] intervals) {
    // 按结束时刻升序;键相同时元素次序不影响结果
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int count = 0;
    long lastEnd = Long.MIN_VALUE;          // 已选区间的结束时刻
    for (int[] it : intervals) {
        if (it[0] >= lastEnd) {             // 与上一个选中区间不重叠
            count++;
            lastEnd = it[1];
        }
    }
    return count;
}

复杂度:排序 O(n log n),扫描 O(n),总 O(n log n),额外空间 O(1)(忽略排序本身的开销)。

会议室数量:按开始时刻排序,用小顶堆保存各会议室的释放时刻。

public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();   // 小顶堆:最早空闲的会议室
    for (int[] it : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= it[0]) {
            endTimes.poll();               // 复用已释放的会议室
        }
        endTimes.offer(it[1]);             // 占用一间(新的或复用的)
    }
    return endTimes.size();                // 堆的大小即所需会议室数
}

复杂度:排序 O(n log n),堆操作每次 O(log n) 共 n 次,总 O(n log n),空间 O(n)。等价的扫描线写法只需一次排序与一次前缀和扫描,空间开销相同但不需堆;两者在小规模下的常数因子接近,具体差异受比较器成本与堆实现影响。

3.3.2 哈夫曼编码构建

import heapq

def huffman_merge_cost(weights):
    """返回最小合并代价;weights 为各字符的频率。"""
    heap = list(weights)
    heapq.heapify(heap)                  # 就地建堆,O(n)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)          # 取出最小的两个
        b = heapq.heappop(heap)
        total += a + b                   # 合并代价计入总代价
        heapq.heappush(heap, a + b)      # 合并结果放回
    return total                         # 只剩一个元素时结束;空输入与单元素输入为 0

代码要点与复杂度:

  • 权值个数为 n 时循环执行 n − 1 轮,每轮三次堆操作,总代价 O(n log n);
  • 输入权值为空或只有一个时循环不执行,返回 0,边界需显式确认;
  • 若只需总代价而不需要码表,不需要真正构建树,只维护合并结果即可;若需要码表,则需要在合并时记录父子关系并自顶向下遍历赋码字;
  • 权值相同时的合并顺序不影响总代价,但影响具体码表,测试应比较总代价而非码表内容。

3.3.3 全排列、子集与组合总和

全排列(元素互不相同):

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrackPermute(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

private void backtrackPermute(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));         // 必须拷贝,否则后续撤销会清空已收集的列表
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrackPermute(nums, used, path, res);
        path.remove(path.size() - 1);           // 撤销与选择严格对称
        used[i] = false;
    }
}

带重复元素的全排列:先排序,并在循环中加入同枝去重判定。

private void backtrackPermuteUnique(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        // 前一个相同取值仍在路径中时保留(保证同枝只走一次)
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrackPermuteUnique(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

子集(含重复元素):

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);                          // 去重前提:相同取值相邻
    List<List<Integer>> res = new ArrayList<>();
    backtrackSubsets(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrackSubsets(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));             // 每个节点都是一个解
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;   // 同层跳过重复取值
        path.add(nums[i]);
        backtrackSubsets(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

组合总和(候选含重复取值,每个元素至多用一次):

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    dfs(candidates, target, 0, new ArrayList<>(), res);
    return res;
}

private void dfs(int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) break;                              // 升序:后续只会更大
        if (i > start && candidates[i] == candidates[i - 1]) continue;  // 同层去重
        path.add(candidates[i]);
        dfs(candidates, remain - candidates[i], i + 1, path, res);      // 每个元素用一次,从 i + 1 继续
        path.remove(path.size() - 1);
    }
}

复杂度对照(n 为元素个数,k 为组合长度,结果数为收集到的解个数):

问题 解空间规模 输出代价 备注
全排列 O(n!) Θ(n · n!) 每个解的长度为 n,拷贝需 O(n)
子集 O(2ⁿ) Θ(n · 2ⁿ) 含空集;含重复取值时结果数减少
组合总和 O(2ⁿ) 上界 依结果数而定 剪枝与去重降低实际节点数
带重复元素的上述问题 不变 结果数减少 去重本身不改变最坏量级,只减少常数级分支

若目标只是"取值集合"而非"元素下标的组合",可用集合结构对已生成的解去重,但需要额外 O(结果数) 的空间,且哈希开销可能超过排序加判定的成本。选择依据是解的数量级与元素取值是否已排序。

3.3.4 N 皇后与数独求解

N 皇后:逐行放置,用三个布尔数组标记列与两条对角线的占用。

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    place(board, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], res);
    return res;
}

private void place(char[][] board, int row, boolean[] col, boolean[] diag1, boolean[] diag2,
                   List<List<String>> res) {
    int n = board.length;
    if (row == n) {                                  // 全部行放置完成,得到一个解
        List<String> snapshot = new ArrayList<>(n);
        for (char[] r : board) snapshot.add(new String(r));
        res.add(snapshot);
        return;
    }
    for (int c = 0; c < n; c++) {
        int d1 = row + c, d2 = row - c + n - 1;      // 主对角线与副对角线的索引
        if (col[c] || diag1[d1] || diag2[d2]) continue;   // 可行性剪枝:O(1) 判定
        col[c] = diag1[d1] = diag2[d2] = true;
        board[row][c] = 'Q';
        place(board, row + 1, col, diag1, diag2, res);
        board[row][c] = '.';
        col[c] = diag1[d1] = diag2[d2] = false;      // 撤销与设置严格对称
    }
}

要点与复杂度:

  • 三个标记数组把"是否与已放置皇后冲突"的判定降到 O(1),避免了每次遍历已放置皇后;
  • 索引 row + c 与 row - c + n - 1 的取值范围都是 [0, 2n − 2],数组长度取 2n − 1;
  • 搜索树规模的上界是 O(n!),实际节点数远小于上界(每行可用列随放置快速减少);
  • 解的对称性(左右镜像)可用于减半搜索量,代价是需要额外的对称性判定逻辑。

数独:用位掩码表示行、列、九宫格的已用数字,配合最小剩余值启发。

public void solveSudoku(char[][] board) {
    int[] rowMask = new int[9], colMask = new int[9], boxMask = new int[9];
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') continue;
            int bit = 1 << (board[r][c] - '1');
            rowMask[r] |= bit;
            colMask[c] |= bit;
            boxMask[boxIndex(r, c)] |= bit;
        }
    }
    fill(board, rowMask, colMask, boxMask);
}

private boolean fill(char[][] board, int[] rowMask, int[] colMask, int[] boxMask) {
    int bestR = -1, bestC = -1, bestCandidates = 0, fewest = 10;
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;
            int candidates = ~(rowMask[r] | colMask[c] | boxMask[boxIndex(r, c)]) & 0x1FF;
            int count = Integer.bitCount(candidates);
            if (count == 0) return false;                 // 无候选,回溯
            if (count < fewest) {                         // 最小剩余值启发
                fewest = count; bestR = r; bestC = c; bestCandidates = candidates;
            }
        }
    }
    if (bestR == -1) return true;                          // 无空格,求解完成
    for (int bits = bestCandidates; bits != 0; bits &= bits - 1) {
        int value = Integer.numberOfTrailingZeros(bits);
        board[bestR][bestC] = (char) ('1' + value);
        rowMask[bestR] |= 1 << value;
        colMask[bestC] |= 1 << value;
        boxMask[boxIndex(bestR, bestC)] |= 1 << value;
        if (fill(board, rowMask, colMask, boxMask)) return true;
        board[bestR][bestC] = '.';                         // 撤销
        rowMask[bestR] &= ~(1 << value);
        colMask[bestC] &= ~(1 << value);
        boxMask[boxIndex(bestR, bestC)] &= ~(1 << value);
    }
    return false;
}

private static int boxIndex(int r, int c) { return r / 3 * 3 + c / 3; }

要点与复杂度:

  • 掩码的第 k 位表示数字 k + 1 已被占用,候选集用 ~(三个掩码取或) & 0x1FF 得到;
  • 最小剩余值启发改变的是搜索顺序而非解空间,它使分支因子小的位置先被填定,从而更早发现矛盾;
  • 每层扫描 81 格选取目标格的代价是常数级,相对指数级的解空间可以忽略;若追求更低常数,可用位运算预取候选最少的行;
  • 最坏复杂度为指数级,实际表现取决于题目与启发强度,测量方法见 3.4 节。

3.4 复杂度与实测

贪心的复杂度主体是排序。 只要排序做一次、主循环线性推进,总代价就是 O(n log n);堆参与时主循环为 O(n log n)。判断贪心实现是否退化,只需检查循环体内是否存在隐藏的排序、remove、contains 等线性或对数操作。几个典型结论:

问题 排序代价 主循环代价 总代价 主要空间
区间调度 O(n log n) O(n) O(n log n) O(1)
会议室数量(堆) O(n log n) O(n log n) O(n log n) O(n)
哈夫曼编码 O(n log n)(堆内排序) O(n log n) O(n log n) O(n)
Kruskal O(E log E) O(E α(V)) O(E log E) O(V + E)
收益调度(堆) O(n log n) O(n log n) O(n log n) O(n)

回溯的复杂度由剪枝决定,因此必须实测。 实测的三项内容:

  1. 节点计数:统计递归函数被调用的次数与剪枝返回的次数,以及"因候选耗尽而返回"与"因剪枝而返回"的比例。该比例反映剪枝条件是否有效。
  2. 解的数量:结果数量与访问节点数的比值反映搜索的冗余程度;比值过低说明存在大量无效探索。
  3. 运行时间:仅在节点数结论确认后才有解释力。

节点计数会改变被测代码的执行形态(计数本身有开销,且可能阻碍内联),因此应当与最终版本分开测量,并把计数版本的结果用于定位问题而非用于性能结论。相同实现不同剪枝策略的比较需要区分预热与测量阶段、固定输入并覆盖多组规模,规范与陷阱见 JMH 微基准测试。

递归深度与栈开销。 递归深度等于决策步数:子集问题为 n,排列问题为 n,棋盘问题为行数或空格数。深度过大时可能触发栈溢出,处理方式是把递归改写为显式栈(用栈保存"当前路径 + 下一个候选下标"),或按语言与运行时的限制调整栈空间。改写为显式栈的收益是深度上限不受调用栈限制,代价是代码复杂度上升与局部变量需要显式入栈。

常数因子的影响在两类算法中不同。 贪心的时间几乎全在排序与比较器内,比较器的实现(一次对象字段访问还是字符串比较)可以造成数倍差异;回溯的时间在递归调用与状态更新上,路径对象的分配次数与深拷贝频率是主要成本项。两者的优化位置因此不同:前者优化比较键,后者优化状态传递方式。

3.5 工程应用

任务调度与资源分配。 定时任务的到期时间排序、向固定数量的执行槽分发任务、在多个资源间分配作业,都是"按某个键排序后逐步分配"的贪心形态。资源释放后的槽位复用规则见 2.2.2 节,按截止时刻排序的收益调度见 2.2.8 节;操作系统侧的定时触发机制(cron、systemd timer、时间轮的实现与取舍)见 linux: 计划任务与定时器,堆与时间轮在延迟任务中的选择见 堆与优先队列 中工程应用一节。

排班与容量分配。 值班排班、机位分配、会议室与车辆的调度,约束是"同一时段内资源不能被重复占用",目标是最小化资源数或最大化利用率。区间调度的按结束时刻排序、会议室数量的最大重叠数结论、排序不等式的配对规则在此类场景中可直接使用。约束增加(技能匹配、连续班次限制、休息间隔)后问题不再是单纯区间调度,需要退回带剪枝的搜索或专门的整数规划方法,此时贪心可作为初始解与下界估计。

组合优化在预算与装箱中的应用。 预算在多个项目间的分配(单位收益递减时为分数背包,可直接贪心)、物品装箱(最小化箱子数,NP 困难,首次适应递减等近似贪心提供常数近似比)、背包与选择问题的近似求解,都属于"精确方法不可行时退化为近似贪心"的场景。近似解与小规模精确解的对比应当作为正确性回归的一部分;近似算法的界与启发式的经验表现的差别见 复杂度与算法分析 中理论的边界一节。

配置与规则匹配中的搜索。 规则引擎在匹配阶段需要在多条规则与多组条件中找出适用者,其执行模型(状态机、流程编排、规则网络)与状态空间的推进方式见 工作流与规则引擎 中规则引擎模型一节。规则之间存在互斥与优先级约束时,选择哪几条规则同时生效可以建模为带约束的搜索或按优先级排序的贪心;规则网络的结构设计(共享条件判断、避免重复求值)与搜索中"共享已计算状态"的思路一致。

回溯在解析与模式匹配中的位置。 回溯型正则引擎的匹配过程就是带剪枝的深度优先搜索,嵌套量词会引发指数级的回溯,工程上通过限制回溯次数、改写表达式或使用自动机型引擎来规避。正则匹配的回溯触发条件、改写方式与替代方案见 字符串算法 中正则表达式回溯与性能一节。结构化文本与词表的匹配通常改用字典树与 AC 自动机(多模式匹配),其构造与遍历方式见 字典树与字符串索引;这类结构把"逐字符回溯"替换为"沿状态转移前进",把最坏复杂度从指数级降到线性级,但只能表达无回溯的匹配语义。

选择判断。 工程实现中区分四类需求即可确定方法:需要最优值且规则可证明时用贪心;需要最优值但选择改变剩余资源时用动态规划;需要全部可行方案时用回溯;只需要可行解且规模大时用近似贪心或启发式。

3.6 常见误用与排查

现象 常见原因 排查手段
贪心结果与预期不符,小规模数据上时对时错 贪心选择性质不成立,规则在部分取值上失效 用暴力枚举或动态规划作基准,在小规模随机数据上穷举对比;按 2.1.6 节构造反例
贪心在大规模数据上结果偏差固定 排序键选错方向(结束时刻与开始时刻、升序与降序) 核对排序键与证明中用到的单调量是否一致;检查相等元素的处理
贪心结果偶发不同 比较器不满足传递性或与等值判定不一致;排序不稳定 检查比较器实现是否使用 Integer.compare、是否把多个键的次序写全
回溯结果中出现空列表或所有结果相同 收集结果时直接引用路径对象而未拷贝 在收集处创建副本;用断点检查结果集中各元素的引用是否相同
回溯结果被污染,后续结果混入了前面的选择 撤销语句缺失、位置错误或与更新不对称 在"做选择"与"撤销选择"两处成对检查;对比两处修改的状态集合
结果数量偏少,漏掉部分可行解 剪枝条件过强,或提前 break 的范围过大 逐条剪枝条件单独关闭后对比结果数量;核对排序前提是否成立(未排序时 break 会漏解)
结果中出现重复方案 去重条件写错(同层与同枝混淆),或未做排序预处理 对照 2.6.5 节的去重表逐项核对;输出前统计重复数作为回归断言
运行时间远高于预期 剪枝不足、状态传递使用深拷贝、或每层做了线性扫描 统计节点数与剪枝命中率;检查路径对象的分配次数;把 O(n) 的判定改为增量维护
递归抛出栈溢出 决策深度等于元素个数或状态空间过大 估算递归深度上界;改用显式栈或迭代加深;确认是否存在自环导致无限递归
求解同一输入偶发超时 输入规模处在剪枝效果的临界点,或搜索顺序依赖输入次序 固定并测试多组边界输入;引入排序与启发式搜索顺序(先处理约束最强的元素)

排查这类问题的通用手段有两类:

  1. 对照基准:为每个贪心与回溯实现配一个规模可控的暴力枚举或动态规划版本,用随机数据对比结果。这一做法能发现绝大多数规则性错误,代价是一次 O(2ⁿ) 的参考实现。
  2. 过程量统计:记录排序键的取值分布、节点访问数、剪枝命中数、结果数与重复结果数。这些量能把"结果不对"定位到"规则错"还是"实现错",也是 3.4 节测量方法的一部分。

3.7 检查清单

贪心正确性。

  • 是否存在可以说明"第一步的贪心选择属于某个最优解"的论证(交换论证、归纳或与下界对比)。
  • 是否在证明中明确用到了排序键的单调性,且代码中的排序方向与该单调性一致。
  • 是否有小规模数据上与暴力解或动态规划解的对比记录,覆盖键相等、极端值与边界容量。
  • 是否已确认约束满足拟阵式的独立性条件(或已说明为何不能这样理解)。
  • 排序键相同时是否需要稳定语义;比较器是否满足自反、反对称、传递。
  • 是否检查过循环体内不存在隐藏的排序或线性查找。
  • 贪心失效时是否有明确的降级路径(动态规划或搜索加剪枝)。

回溯实现。

  • 结束条件是否覆盖"收集解"与"无需继续"两种情况,且收集时对路径做了拷贝。
  • 剪枝条件的推导是否正确,每条剪枝是否单独验证过不漏解。
  • 做选择与撤销选择是否严格对称,涉及的每个状态是否都在两处出现。
  • 去重是否先排序,判定条件是否与重复来源匹配(同层或同枝)。
  • 是否有重复状态可通过记忆化或对称性剪枝消除。
  • 递归深度上界是否已估算;深度过大时是否有迭代化的方案。
  • 解空间规模上界是否已估算,是否落在可接受的量级内;若是 NP 困难问题,是否使用近似方法并明确标注。
  • 结果数量是否有回归断言;节点访问数与剪枝命中率是否可以在测试环境输出。
  • 状态传递方式(共享可变路径还是每层副本)是否与性能要求和并发使用方式一致。
  • 性能结论是否来自基准测试,是否记录了输入规模与搜索顺序。

四、总结

两类思路的分工。 贪心每步取当前最优、不做回顾,代价落在排序主导的 O(n log n),前提是贪心选择性质可证;回溯穷举全部可能并以剪枝压缩实际搜索量,能表达任何决策问题,最坏代价由解空间规模决定。选择依据是问题需要"一个最优值"还是"全部可行方案",以及选择是否会非单调地改变后续可行域。

贪心的两个条件。 贪心选择性质保证"提前确定这一步不损失最优性",最优子结构保证"剩余部分可用同一规则处理"。只具备后者时问题可用动态规划。局部最优推出全局最优依赖目标函数的单调可加性与排序键的单调性,以及选择之间不存在非单调交互。

证明方法。 交换论证通过"替换最优解中的元素并证明可行性与目标值不劣"完成证明;归纳法把断言放在决策步数上;与最优解对比则构造下界并证明算法达到下界。拟阵给出结构性的解释:独立集族满足遗传性与交换性时,按权排序、只取不破坏独立性的元素即为最优解,Kruskal 是这一结构在图拟阵上的实例。失败反例的构造围绕"取值取舍、整除关系、排序键分离、目标函数非线性"四类手法展开。

典型问题。 区间调度按结束时刻排序,证明用交换论证;会议室数量的答案是最大重叠数,实现为扫描线或按开始时刻排序加小顶堆;找零只在规范货币系统中贪心有效,面值可配置时改用动态规划;哈夫曼编码每次合并两个最小权值,总代价即加权外部路径长度,堆实现为 O(n log n);最小生成树由割性质与环性质支撑 Prim 与 Kruskal 两种贪心;Dijkstra 的取最小依赖非负边权;排序不等式给出同序最大、逆序最小的配对规则;任务调度按截止时刻排序,配小顶堆实现"撤销最差选择"的可后悔贪心。

贪心与动态规划的边界。 分界点是"选择是否以非单调方式改变剩余资源"。分数背包与 0-1 背包、规范货币系统与非规范系统是同一分界的两个实例。贪心加堆是"只保留一个部分解但允许局部反悔",动态规划是"保留全部状态维的最优值";反悔窗口为常数时用堆,需要回溯多个已选元素时用动态规划。

回溯的模型。 决策过程展开为解空间树,子集树有 2ⁿ 个叶子、排列树有 n! 个叶子、组合树按组合数展开;深度优先遍历这棵树,路径、选择列表与结束条件构成递归函数的三要素;做选择与撤销选择必须严格对称,路径以不可变副本传递可免除撤销但增加复制开销。

剪枝与去重。 可行性剪枝依赖约束的单调可判定性,最优性剪枝(分支限界)依赖对目标值的乐观估计;重复状态可用记忆化、对称性剪枝与路径去重消除;排序预处理同时服务于去重、提前终止、搜索顺序与最优性剪枝;位掩码适合 64 个元素以内的集合表示与状态键。迭代加深把空间从 O(b^d) 降到 O(d),双向搜索把节点数降到 O(b^(d/2))。

统一框架。 子集、排列、组合、划分、棋盘与图搜索可以纳入同一套递归框架,差别只在选择列表的表示(start 或 used)、结束条件与去重判据。去重的统一方法是先确定"两个解何时被视为相同",再把它翻译成"某个分支无需展开"。

复杂度与可行性。 贪心的代价主体是排序与堆操作;回溯的最坏复杂度是解空间规模,实际表现由剪枝强度决定,两者可能相差多个数量级,因此判断可行性时不能只看前者的量级,也不能把剪枝后的经验规模当作最坏规模。方法选择沿着"表达能力与代价递增"的序列展开:纯回溯、加记忆化、动态规划、贪心,选择依据是状态能否压缩、选择是否改变剩余资源、是否需要全部解。

贪心与回溯是同一棵决策树上的两种访问方式:贪心只沿一条被证明安全的分支走到底,回溯则遍历全部分支并用剪枝砍掉不可能的子树。前者的难点在证明,后者的难点在剪枝;两者共同的判断依据是"当前部分解离最优解有多远、还能不能更近"。