计算机数学 计算复杂性理论与NPC、NP难问题的求解2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

计算机数学 计算复杂性理论与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