算法详解系列图书共有4卷，本书是第4卷——NP-Hard问题算法。全书共有6章，主要介绍了快速识别NP-Hard问题的方法和处理NP的算法工具。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。
本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维与计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。

第1章什么是NP问题1
1.1MST和TSP：算法的难解之谜2
1.1.1最小生成树问题2
1.1.2旅行商问题3
1.1.3解决TSP的尝试和失败4
1.1.4小测验1.1–1.2的答案6
1.2读者的不同专业层次7
1.3容易的问题和困难的问题8
1.3.1多项式时间的算法9
1.3.2多项式时间与指数级时间10
1.3.3容易的问题11
1.3.4相对难以处理12
1.3.5困难的问题12
1.3.6P≠NP猜想14
1.3.7NP问题的临时定义14
1.3.8随机化和量子算法15
1.3.9微妙性15
1.4NP问题的算法策略16
1.4.1通用、正确、快速（选择其二）17
1.4.2通用性的妥协18
1.4.3正确性的妥协19
1.4.4最坏情况运行时间的妥协20
1.4.5关键思路21
1.5证明NP问题：一个简单的方案21
1.5.1转化22
1.5.2使用转化来设计快速算法23
1.5.3使用转化对NP问题进行扩展25
1.5.4无环最短路径是NP问题26
1.5.5小测验1.3的答案30
1.6新手错误和可接受的不准确说法30
1.7本章要点33
1.8章末习题34
1.8.1挑战题36
1.8.2编程题37
第2章正确性的妥协：高效的不准确算法38
2.1完成工时最小化38
2.1.1问题定义39
2.1.2贪心算法40
2.1.3Graham算法41
2.1.4运行时间42
2.1.5近似的正确性42
2.1.6定理2.1的证明44
2.1.7最长处理时间优先（LPT）46
2.1.8定理2.4的证明49
2.1.9小测验2.1–2.3的答案50
2.2最大覆盖51
2.2.1问题定义51
2.2.2更多的应用53
2.2.3一种贪心算法54
2.2.4GreedyCoverage算法的糟糕例子55
2.2.5近似正确性57
2.2.6一个关键的辅助结论58
2.2.7定理2.6的证明60
2.2.8小测验2.4–2.5的答案61
*2.3影响最大化62
2.3.1社交网络的瀑布模型62
2.3.2例子63
2.3.3影响最大化问题64
2.3.4一种贪心算法65
2.3.5近似正确性66
2.3.6影响是覆盖函数的一个加权和66
2.3.7定理2.8的证明67
2.3.8小测验2.6的答案69
2.4TSP的2-OPT启发式算法70
2.4.1处理TSP70
2.4.2通过2-变换改进路线72
2.4.32-OPT算法74
2.4.4运行时间75
2.4.5解决方案质量76
2.4.6小测验2.7–2.8的答案76
2.5局部搜索的原则77
2.5.1可行解决方案的元图（Meta-Graph）77
2.5.2局部搜索算法设计范例79
2.5.3三个建模决策80
2.5.4两个算法设计决策83
2.5.5运行时间和