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

后记 算法设计实战指南

6.7 章末习题

6.6 本章要点

6.5 最终结果

6.4 降序时钟拍卖的实现

6.3 可行性检查

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

6.1 无线频谱再利用

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

5.8 章末习题

5.7 本章要点

*5.6 NP完全问题

*5.5 指数级时间假设

*5.4 P≠NP猜想

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

*5.2 决策、搜索和优化

*5.1 难处理性的累积证据

第5章 P、NP及相关概念

4.10 章末习题

4.9 本章要点

4.8 子集求和问题是NP问题

4.7 TSP是NP问题

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

4.5 独立子集问题是NP问题

4.4 一个转化模板

4.3 整体思路

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

4.1 再论转化

第4章 证明NP问题

3.7 章末习题

3.6 本章要点

3.5 可满足性解决程序

3.4 混合整数规划解决程序

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

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

3.1 TSP的Bellman-Held-Karp算法

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

2.7 章末习题

2.6 本章要点

2.5 局部搜索的原则

2.4 TSP的2-OPT启发式算法

*2.3 影响最大化

2.2 最大覆盖

2.1 完成工时最小化

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

1.8 章末习题

1.7 本章要点

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

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

1.4 NP问题的算法策略

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

1.2 读者的不同专业层次

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

第1章 什么是NP问题

致谢

前言

内容提要

版权

版权信息

封面

封面

版权信息

版权

内容提要

前言

致谢

第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 章末习题

后记 算法设计实战指南