数据结构与算法 / 系统课时

近似算法

近似算法

当优化问题难以在可接受时间内求得最优解时,近似算法用可证明的解质量换取多项式时间。本课以无权顶点覆盖为例,说明近似比如何定义、2-近似算法为何成立,以及怎样验证实现结果。

学习目标

  • 理解最小化问题中近似比与最坏情况性能保证的含义。
  • 掌握无权顶点覆盖的 2-近似构造过程与证明思路。
  • 能够实现并验证一个线性扫描的顶点覆盖近似算法。

问题定义与性能保证

优化问题不仅要求得到合法解,还要求目标值尽可能好。设输入实例为 II,最优目标值为 OPT(I)OPT(I),算法得到的目标值为 A(I)A(I)。对最小化问题,若对所有合法输入都有 A(I)/OPT(I)≤ρA(I) / OPT(I) ≤ ρ,就称该算法具有近似比 ρρ;其中 ρ≥1ρ ≥ 1,越接近 1,保证越强。

近似比描述的是最坏情况上界,而不是某组测试数据上的平均表现。一个算法在多数样例中接近最优,但没有覆盖所有输入的证明,不能仅凭实验结果称为具有固定近似比的算法。

顶点覆盖问题给定无向图 G=(V,E)G=(V,E),要求选择尽可能少的顶点,使每条边至少有一个端点被选中。该问题的解必须先满足“覆盖全部边”,再比较所选顶点数量。

顶点覆盖的 2-近似思路

算法反复选择一条尚未被覆盖的边 (u,v)(u,v),把两个端点都加入覆盖集合,并把所有与 uu 或 vv 相连的边视为已覆盖,直到不存在未覆盖边。

顶点覆盖 2-近似算法的选择过程与性能证明

被选中的边两两不共享端点,因此构成一个匹配 MM。任何顶点覆盖都必须覆盖 MM 中的每条边;由于这些边互不共享端点,最优解至少需要 ∣M∣|M| 个顶点。算法恰好加入 2∣M∣2|M| 个顶点,所以有 ∣A∣=2∣M∣≤2∣OPT∣|A| = 2|M| ≤ 2|OPT|,近似比为 2。

完整可运行示例

下面的 Java 17 程序按输入边的顺序扫描图。若一条边的两个端点都未进入覆盖集合,就同时选择这两个端点。使用 LinkedHashSet 可以保留选择顺序,便于核对输出。

java
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,然后编译并运行:

bash
javac VertexCoverApproxDemo.java
java VertexCoverApproxDemo

预期输出:

text
近似顶点覆盖: [0, 1, 2, 4]
覆盖全部边: true

该图的最优顶点覆盖大小为 3,示例算法返回 4 个顶点,实际质量比为 4/34/3,同时满足不超过 2 的理论保证。

复杂度、验证与适用边界

若集合的查询和插入按均摊常数时间计算,扫描每条边一次的时间复杂度为 O(∣E∣)O(|E|),覆盖集合的额外空间复杂度为 O(∣V∣)O(|V|)。实现完成后至少要验证每条边是否有端点位于结果集合中;只检查结果大小,不能证明它是合法顶点覆盖。

该方法适用于无权顶点覆盖。若顶点具有不同权重,直接选择一条边的两个端点可能付出极高代价,原有 2-近似证明不再成立,需要使用针对加权问题设计的算法。近似保证始终依赖明确的问题模型和假设,不能跨模型直接复用。

本课练习

  1. 为示例增加顶点 5,加入边 (4,5) 与 (3,5),运行程序并记录选择集合。验收条件是 coversAllEdges 返回 true,并能解释边顺序为何影响具体集合但不破坏 2-近似保证。
  2. 编写一个只用于小图的穷举函数,计算最优顶点覆盖大小,再随机生成 8 个顶点以内的图,对比近似解与最优解。验收条件是每个样例都满足近似解大小不超过最优解的 2 倍。

本课总结

  • 近似算法同时要求解合法、运行高效,并对所有合法输入给出可证明的最坏情况质量界限。
  • 顶点覆盖 2-近似算法通过选择匹配边的两个端点构造解,匹配大小为最优解提供下界。
  • 性能保证依赖问题模型;从无权问题切换到加权问题后,必须重新检查算法与证明。

下一课预告

下一课将学习“启发式方法的使用边界”,重点比较启发式算法与近似算法在性能承诺、实验评估和工程风险控制上的差异。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

近似算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通