计算机数学 计算复杂性理论与NPC、NP难问题的求解PDF电子书下载

第一章 线性规划 1

1.1 线性规划的基本概念 1

1.2 单纯形算法 4

1.3 字典序单纯形算法 7

1.4 对偶理论 10

1.5 内点算法 14

第二章 多面体理论 21

2.1 多面体的定义及其维数 21

2.2 用有效不等式与边界面来描述多面体 23

2.3 用极点和极射向表示多面体 26

第三章 图与网络规划 34

3.1 图的基本知识 34

3.1.1 图 34

3.1.2 有向图 36

3.1.3 图的表示 38

3.2 几类重要的图 41

3.3 最短路问题 42

3.4 最小权支撑树问题 44

3.5 最大流问题 45

第四章 动态规划方法 53

4.1 多阶段决策问题与动态规划的基本概念 53

4.2 动态规划方法的基本思想与最优性定理 55

4.3 最小权问题 59

4.4 背包问题 61

4.4.1 0-1背包问题 61

4.4.2 整数背包问题 63

4.5 旅行商问题 65

第五章 算法复杂性概论 68

5.1 引言 68

5.2 基本概念 69

5.3 多项式时间算法与指数时间算法 71

第六章 问题复杂性的分类 75

6.1 判定问题与语言 75

6.2 算法的严格定义与P类问题 78

6.3 NP类问题 80

6.4 多项式变换与NP完全问题 84

6.5 强NP完全问题 87

6.6 Co-NP类问题 90

6.7 NP困难问题 92

6.8 空间复杂性简介 95

第七章 证明问题为NP完全的或P的方法 97

7.1 证明问题为NPC的一般步骤 97

7.2 限制法(Restriction) 100

7.3 局部置换法(Local Replacement) 101

7.4 分量设计法(Component Design) 105

7.5 证明问题属于P类的方法 110

第八章 NP完全理论在分析、求解新问题中的应用 114

8.1 分析新问题复杂性的双向研究方法 114

8.2 子问题分析法 116

8.3 求解NPC问题的算法类型 119

第九章 近似算法的性能度量与NP完全理论的应用 125

9.1 近似算法的性能度量 125

9.2 NP完全理论在限定问题可近似程度中的应用 134

第十章 一般整数规划的基本性质 137

10.1 一般整数规划问题 137

10.2 整数规划与线性规划之间的关系 139

10.3 整数规划问题解的有界性 143

10.4 整数规划问题的计算复杂性 146

第十一章 割平面算法 150

11.1 分数割平面算法 150

11.2 整数割平面算法 154

11.3 导出有效不等式的方法 161

11.3.1 取整方法 161

11.3.2 同余方法 162

11.3.3 合并方法 162

11.3.4 超加函数法 163

11.4 混合整数规划问题的求解 167

11.5 覆盖问题的割平面算法 173

11.5.1 覆盖问题的描述 173

11.5.2 覆盖问题的割平面算法 175

第十二章 分解算法 179

12.1 拉格朗日松弛法 179

12.2 Benders分解 185

12.3 一般分解方法 188

12.4 选址问题的分解算法 192

13.1 一般分枝定界法 196

第十三章 分枝定界法 196

13.2 使用线性规划松弛的分枝定界算法 199

13.2.1 剪枝准则 199

13.2.2 分枝方法 200

13.2.3 结节选取方法 202

13.2.4 分枝变量选择力法 203

13.3 0-1背包问题的分枝定界算法 206

第十四章 匹配问题 210

14.1 匹配问题简介 210

14.2 最大匹配问题 212

14.2.1 二部图的匹配算法 214

14.2.2 非二部图的匹配算法 216

14.3 加权匹配问题 222

14.3.1 指派问题的求解 222

14.3.2 一般加权匹配问题 226

14.4.1 b匹配问题 232

14.4 b匹配问题与其他相关论题 232

14.4.2 匹配理论与算法的应用 236

第十五章 近似算法的设计与分类 240

15.1 近似算法概述 240

15.2 贪婪算法(Greedy Algorithms) 241

15.3 局部搜索法(Local Search Heuristics) 242

15.4 原始-对偶法 245

15.5 近似算法的其他设计方法 250

15.6 近似算法的分类 253

15.6.1 定常近似比算法 254

15.6.2 近似策略 255

15.6.3 最好可能近似比算法 258

15.6.4 比最好还要好的近似算法 260

15.6.5 与真正最优值仅一步之遥的近似算法 262

16.1 有效不等式的构造 264

第十六章 对称旅行商问题 264

16.2 松弛问题的构造 270

16.3 近似算法 273

16.3.1 最近邻法 274

16.3.2 最近插入法 274

16.3.3 贪婪可行法 275

16.3.4 k边交换法 275

16.3.5 三角不等式与贪婪型算法的性能 275

16.3.6 支撑树加倍法 279

16.3.7 支撑树加完美匹配法 280

16.4 精确算法 282

16.4.1 指派问题加分枝定界算法 283

16.4.2 拉格朗日松弛加分枝定界算法 284

16.4.3 分数割平面加分枝定界算法 285

参考文献 289