算法详解（卷4）——NP-Hard问题算法

蒂姆·拉夫加登

扉页
版权信息
+书签
内容提要
前言
本书涵盖的内容
“算法详解”系列图书前三卷所涵盖的主题
读者的收获
其他算法教材
本书的目标读者
致谢
第1章什么是NP问题
1.1 MST和TSP：算法的难解之谜
1.1.1 最小生成树问题
1.1.2 旅行商问题
1.1.3 解决TSP的尝试和失败
1.1.4 小测验1.1和小测验1.2的答案
1.2 读者的不同专业层次
1.3 容易的问题和困难的问题
1.3.1 多项式时间的算法
1.3.2 多项式时间与指数级时间
1.3.3 容易的问题
1.3.4 相对难以处理
1.3.5 困难的问题
1.3.6 P≠NP猜想
1.3.7 NP问题的临时定义
1.3.8 随机化和量子算法
1.3.9 微妙性
1.4 NP问题的算法策略
1.4.1 通用、正确、快速（选择其二）
1.4.2 通用性的妥协
1.4.3 正确性的妥协
1.4.4 最坏情况运行时间的妥协
1.4.5 关键思路
1.5 证明NP问题：一个简单的方案
1.5.1 转化
1.5.2 使用转化来设计快速算法
1.5.3 使用转化对NP问题进行扩展
1.5.4 无环最短路径是NP问题
1.5.5 小测验1.3的答案
1.6 新手错误和可接受的不准确说法
1.7 本章要点
1.8 章末习题
1.8.1 挑战题
1.8.2 编程题
第2章正确性的妥协：高效的不准确算法
2.1 完成工时最小化
2.1.1 问题定义
2.1.2 贪心算法
2.1.3 Graham算法
2.1.4 运行时间
2.1.5 近似的正确性
2.1.6 定理2.1的证明
2.1.7 最长处理时间优先(LPT)
2.1.8 定理2.2的证明
2.1.9 小测验2.1～2.3的答案
2.2 最大覆盖
2.2.1 问题定义
2.2.2 更多的应用
2.2.3 一种贪心算法
2.2.4 GreedyCoverage算法的糟糕例子
2.2.5 近似正确性
2.2.6 一个关键的辅助结论
2.2.7 定理2.3的证明
2.2.8 小测验2.4和小测试2.5的答案
*2.3 影响最大化
2.3.1 社交网络的瀑布模型
2.3.2 例子
2.3.3 影响最大化问题
2.3.4 一种贪心算法
2.3.5 近似正确性
2.3.6 影响是覆盖函数的一个加权和
2.3.7 定理2.4的证明
2.3.8 小测验2.6的答案
2.4 TSP的2-OPT启发式算法
2.4.1 处理TSP
2.4.2 通过2-变换改进路线
2.4.3 2-OPT算法
2.4.4 运行时间
2.4.5 解决方案质量
2.4.6 小测验2.7和小测验2.8的答案
2.5 局部搜索的原则
2.5.1 可行解决方案的元图(Meta-Graph)
2.5.2 局部搜索算法设计范例
2.5.3 三个建模决策
2.5.4 两个算法设计决策
2.5.5 运行时间和解决方案质量
2.5.6 避免低质量的局部最优解
2.5.7 什么时候应该使用局部搜索？
2.5.8 小测验2.9和小测验2.10的答案
2.6 本章要点
2.7 章末习题
2.7.1 挑战题
2.7.2 编程题
第3章速度的妥协：准确的非高效算法
3.1 TSP的Bellman-Held-Karp算法
3.1.1 底线：穷举搜索
3.1.2 动态规划
3.1.3 最优子结构
3.1.4 推导公式
3.1.5 子问题
3.1.6 Bellman-Held-Karp算法
3.1.7 小测验3.1的答案
*3.2 通过颜色编码寻找最长路径
3.2.1 动机
3.2.2 问题定义
3.2.3 子问题的初次试探
3.2.4 颜色编码
3.2.5 计算最低成本全色路径
3.2.6 正确性和运行时间
3.2.7 随机化挽救危局
3.2.8 最终的算法
3.2.9 运行时间和正确性
3.2.10 再论PPI网络
3.2.11 小测验3.2～3.4的答案
3.3 问题特定的算法与万能魔盒
3.3.1 转化和万能魔盒
3.3.2 MIP和SAT解决程序
3.3.3 将要学习的和不会学习的
3.3.4 再论新手易犯的错误
3.4 混合整数规划解决程序
3.4.1 例子：背包问题
3.4.2 更基本意义上的MIP
3.4.3 MIP解决程序的一些起点
3.5 可满足性解决程序
3.5.1 示例：图形着色
3.5.2 可满足性
3.5.3 把图形着色问题表达为SAT
3.5.4 SAT解决程序：一些起点
3.6 本章要点
3.7 章末习题
3.7.1 挑战题
3.7.2 编程题
第4章证明NP问题
4.1 再论转化
4.2 3-SAT问题和Cook-Levin定理
4.3 整体思路
4.3.1 再论新手易犯的错误
4.3.2 18个转化
4.3.3 为什么要啃艰涩的NP问题证明？
4.3.4 小测验4.1的答案
4.4 一个转化模板
4.5 独立子集问题是NP问题
4.5.1 主要思路
4.5.2 定理4.2的证明
*4.6 有向汉密尔顿路径问题是NP问题
4.6.1 变量的编码和真值指派
4.6.2 约束条件的编码
4.6.3 定理4.3的证明
4.7 TSP是NP问题
4.7.1 无向汉密尔顿路径问题
4.7.2 定理4.4的证明
4.8 子集求和问题是NP问题
4.8.1 基本方法
4.8.2 例子：4顶点环路
4.8.3 例子：5顶点环路
4.8.4 定理4.5的证明
4.9 本章要点
4.10 章末习题
挑战题
第5章 P、NP及相关概念
*5.1 难处理性的累积证据
5.1.1 通过转化创建一个案例
5.1.2 为TSP选择集合C
*5.2 决策、搜索和优化
*5.3 NP：具有容易识别的解决方案的问题
5.3.1 复杂类NP的定义
5.3.2 NP中的问题实例
5.3.3 NP问题是可以通过穷举搜索解决的
5.3.4 NP问题
5.3.5 再论Cook-Levin定理
5.3.6 小测验5.1的答案
*5.4 P≠NP猜想
5.4.1 多项式时间可解决的NP问题
5.4.2 P≠NP猜想的正式定义
5.4.3 P≠NP猜想的状态
*5.5 指数级时间假设
5.5.1 NP问题需要指数级的时间吗？
5.5.2 强指数级时间假设(SETH)
5.5.3 容易问题的运行时间下界
*5.6 NP完全问题
5.6.1 Levin转化
5.6.2 NP中最难的问题
5.6.3 NP完全问题的存在
5.7 本章要点
5.8 章末习题
挑战题
第6章案例研究：FCC激励拍卖
6.1 无线频谱再利用
6.1.1 从电视到移动电话
6.1.2 无线频谱的一次最近重分配
6.2 回购执照的启发式贪心算法
6.2.1 4个临时的简化假设
6.2.2 遭遇加权独立子集问题
6.2.3 启发式贪心算法
6.2.4 多频道情况
6.2.5 遭遇图形着色问题
6.2.6 小测验6.1的答案
6.3 可行性检查
6.3.1 改编为可满足性问题
6.3.2 加入边际约束条件
6.3.3 重新安置问题
6.3.4 技巧#1：预解决程序（寻求一种容易的解决之道）
6.3.5 技巧#2：预处理和简化
6.3.6 技巧#3：SAT解决程序的组合
6.3.7 容忍失败
6.3.8 小测验6.2的答案
6.4 降序时钟拍卖的实现
6.4.1 拍卖和算法
6.4.2 例子
6.4.3 重新实现FCCGreedy算法
6.4.4 是时候提供补偿了
6.5 最终结果
6.6 本章要点
6.7 章末习题
6.7.1 挑战题
6.7.2 编程题
后记算法设计实战指南
附录问题提示和答案

简介

版权

算法详解（卷4）——NP-Hard问题算法