概念

近似算法

贪心策略、动态规划与 LP 舍入等方法在多项式时间内给出有性能保证（近似比）的解，如背包、集合覆盖问题。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

近似算法运筹学

01定义

NP 难问题无法指望多项式时间的精确解，近似算法退而求其次：在多项式时间内给出带性能保证的解。近似比

\alpha

承诺解的质量不低于最优解的

\alpha

倍——贪心、LP 舍入、动态规划是三大构造工具。

近似比：与最优解的差距有明确保证

集合覆盖贪心比 $\ln n+1$ 且该界渐近紧（除非 P=NP 无法改进）；背包按性价比贪心 + 取单件最大，2-近似——贪心的成功需要次模性/拟阵结构支撑。

先解线性松弛得分数解，再确定或随机地舍入为整数：顶点覆盖 2-近似、最大覆盖 $(1-1/e)$ ；随机舍入用期望论证质量，集中不等式控制偏差。

实践中启发式常优于理论界；在线算法用竞争比替代近似比；参数化复杂度（FPT）开辟了另一条精确求解的窄门。

\frac{\mathrm{ALG}}{\mathrm{OPT}}\leq\alpha\ (\min),\quad \text{贪心集合覆盖}\leq(\ln n+1)\,\mathrm{OPT}

约翰逊 1974 年分析装箱问题的近似比，开创该领域；瓦兹拉尼 2001 年教材系统化方法；Håstad 1997 年的不可近似性结果划出理论边界。

物流路径的实用求解、广告投放的集合覆盖、云计算的资源调度、网络设计的买一送一式近似。

顶点覆盖的 2-近似：极大匹配端点贪心选取极大匹配的所有端点，覆盖大小 ≤ 2×最优

步骤0