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

封面

版权信息

版权

内容提要

前言

致谢

第1章 什么是NP问题

1.1 MST和TSP：算法的难解之谜

1.2 读者的不同专业层次

1.3 容易的问题和困难的问题

1.4 NP问题的算法策略

1.5 证明NP问题：一个简单的方案

1.6 新手错误和可接受的不准确说法

1.7 本章要点

1.8 章末习题

第2章 正确性的妥协：高效的不准确算法

2.1 完成工时最小化

2.2 最大覆盖

*2.3 影响最大化

2.4 TSP的2-OPT启发式算法

2.5 局部搜索的原则

2.6 本章要点

2.7 章末习题

第3章 速度的妥协：准确的非高效算法

3.1 TSP的Bellman-Held-Karp算法

*3.2 通过颜色编码寻找最长路径

3.3 问题特定的算法与万能魔盒

3.4 混合整数规划解决程序

3.5 可满足性解决程序

3.6 本章要点

3.7 章末习题

第4章 证明NP问题

4.1 再论转化

4.2 3-SAT问题和Cook-Levin定理

4.3 整体思路

4.4 一个转化模板

4.5 独立子集问题是NP问题

*4.6 有向汉密尔顿路径问题是NP问题

4.7 TSP是NP问题

4.8 子集求和问题是NP问题

4.9 本章要点

4.10 章末习题

第5章 P、NP及相关概念

*5.1 难处理性的累积证据

*5.2 决策、搜索和优化

*5.3 NP：具有容易识别的解决方案的问题

*5.4 P≠NP猜想

*5.5 指数级时间假设

*5.6 NP完全问题

5.7 本章要点

5.8 章末习题

第6章 案例研究：FCC激励拍卖

6.1 无线频谱再利用

6.2 回购执照的启发式贪心算法

6.3 可行性检查

6.4 降序时钟拍卖的实现

6.5 最终结果

6.6 本章要点

6.7 章末习题

后记 算法设计实战指南