《算法详解 (卷4)：NP-Hard问题算法》PDF下载

《算法详解（卷 4）：NP-Hard 问题算法》聚焦算法设计中最棘手的一类问题：当一个问题没有已知的快速精确算法时，应该怎么办。全书从 P、NP 和 NP-Hard 的基本直觉出发，帮助读者快速判断现实问题是否可能属于计算上难以处理的类别。

面对 NP-Hard 问题，作者首先介绍“牺牲正确性换取速度”的路线，包括贪心启发式、局部搜索、最大覆盖、影响力最大化以及旅行商问题的 2-OPT 方法。这些算法不保证总能找到最优解，却可能在实际规模的数据上快速得到高质量结果。

另一条路线则是牺牲速度来保持答案正确，书中讨论动态规划、混合整数规划和 SAT 求解器等技术。随后通过 3-SAT、独立集、哈密尔顿路径、TSP 和子集和等问题介绍归约方法，并进一步建立 NP 完全性和 P≠NP 问题的理论框架。

最后的 FCC 频谱激励拍卖案例展示理论算法如何进入大型现实系统。本书适合已经掌握基础图算法、贪心和动态规划的计算机专业学生与工程师，也适合算法面试准备者进一步建立复杂性理论和困难问题处理思维。