数据结构与算法 / 系统课时
近似算法
近似算法
当优化问题难以在可接受时间内求得最优解时,近似算法用可证明的解质量换取多项式时间。本课以无权顶点覆盖为例,说明近似比如何定义、2-近似算法为何成立,以及怎样验证实现结果。
学习目标
- 理解最小化问题中近似比与最坏情况性能保证的含义。
- 掌握无权顶点覆盖的 2-近似构造过程与证明思路。
- 能够实现并验证一个线性扫描的顶点覆盖近似算法。
问题定义与性能保证
优化问题不仅要求得到合法解,还要求目标值尽可能好。设输入实例为 ,最优目标值为 ,算法得到的目标值为 。对最小化问题,若对所有合法输入都有 ,就称该算法具有近似比 ;其中 ,越接近 1,保证越强。
近似比描述的是最坏情况上界,而不是某组测试数据上的平均表现。一个算法在多数样例中接近最优,但没有覆盖所有输入的证明,不能仅凭实验结果称为具有固定近似比的算法。
顶点覆盖问题给定无向图 ,要求选择尽可能少的顶点,使每条边至少有一个端点被选中。该问题的解必须先满足“覆盖全部边”,再比较所选顶点数量。
顶点覆盖的 2-近似思路
算法反复选择一条尚未被覆盖的边 ,把两个端点都加入覆盖集合,并把所有与 或 相连的边视为已覆盖,直到不存在未覆盖边。

被选中的边两两不共享端点,因此构成一个匹配 。任何顶点覆盖都必须覆盖 中的每条边;由于这些边互不共享端点,最优解至少需要 个顶点。算法恰好加入 个顶点,所以有 ,近似比为 2。
完整可运行示例
下面的 Java 17 程序按输入边的顺序扫描图。若一条边的两个端点都未进入覆盖集合,就同时选择这两个端点。使用 LinkedHashSet 可以保留选择顺序,便于核对输出。
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
public class VertexCoverApproxDemo {
record Edge(int u, int v) {
}
static Set<Integer> approximateVertexCover(List<Edge> edges) {
Set<Integer> cover = new LinkedHashSet<>();
for (Edge edge : edges) {
// 两个端点都未被选择时,这条边仍未被当前集合覆盖。
if (!cover.contains(edge.u()) && !cover.contains(edge.v())) {
cover.add(edge.u());
cover.add(edge.v());
}
}
return cover;
}
static boolean coversAllEdges(List<Edge> edges, Set<Integer> cover) {
for (Edge edge : edges) {
if (!cover.contains(edge.u()) && !cover.contains(edge.v())) {
return false;
}
}
return true;
}
public static void main(String[] args) {
List<Edge> edges = List.of(
new Edge(0, 1),
new Edge(0, 2),
new Edge(1, 2),
new Edge(1, 3),
new Edge(2, 4),
new Edge(3, 4)
);
Set<Integer> cover = approximateVertexCover(edges);
System.out.println("近似顶点覆盖: " + cover);
System.out.println("覆盖全部边: " + coversAllEdges(edges, cover));
}
}将代码保存为 VertexCoverApproxDemo.java,然后编译并运行:
javac VertexCoverApproxDemo.java
java VertexCoverApproxDemo预期输出:
近似顶点覆盖: [0, 1, 2, 4]
覆盖全部边: true该图的最优顶点覆盖大小为 3,示例算法返回 4 个顶点,实际质量比为 ,同时满足不超过 2 的理论保证。
复杂度、验证与适用边界
若集合的查询和插入按均摊常数时间计算,扫描每条边一次的时间复杂度为 ,覆盖集合的额外空间复杂度为 。实现完成后至少要验证每条边是否有端点位于结果集合中;只检查结果大小,不能证明它是合法顶点覆盖。
该方法适用于无权顶点覆盖。若顶点具有不同权重,直接选择一条边的两个端点可能付出极高代价,原有 2-近似证明不再成立,需要使用针对加权问题设计的算法。近似保证始终依赖明确的问题模型和假设,不能跨模型直接复用。
本课练习
- 为示例增加顶点
5,加入边(4,5)与(3,5),运行程序并记录选择集合。验收条件是coversAllEdges返回true,并能解释边顺序为何影响具体集合但不破坏 2-近似保证。 - 编写一个只用于小图的穷举函数,计算最优顶点覆盖大小,再随机生成 8 个顶点以内的图,对比近似解与最优解。验收条件是每个样例都满足近似解大小不超过最优解的 2 倍。
本课总结
- 近似算法同时要求解合法、运行高效,并对所有合法输入给出可证明的最坏情况质量界限。
- 顶点覆盖 2-近似算法通过选择匹配边的两个端点构造解,匹配大小为最优解提供下界。
- 性能保证依赖问题模型;从无权问题切换到加权问题后,必须重新检查算法与证明。
下一课预告
下一课将学习“启发式方法的使用边界”,重点比较启发式算法与近似算法在性能承诺、实验评估和工程风险控制上的差异。