计算机难解问题的骨架理论与应用PDF电子书下载

第一章 计算机难解问题与计算复杂性理论 1

1. 1现实世界中的难解问题 1

1. 2 P与NP 2

1. 2. 1问题与实例 2

1.2.2多项式时间算法与指数时间算法 3

1. 3 P类与NP类问题 5

1.4典型的NP-难解问题 6

1. 4. 1 TSP问题 6

1. 4. 2 QAP问题 10

1. 4. 3 p-中位问题 13

1.5历史文献评注 15

参考文献 17

第二章 求解难解问题的非精确算法 22

2.1启发式算法 22

2. 1. 1局部搜索 23

2.1.2贪心算法 31

2.1.3禁忌搜索 32

2.1. 4模拟退火 34

2.1.5遗传算法 35

2. 1. 6蚁群算法 39

2.1. 7拟物拟人算法 43

2.2超启发式算法 43

2.2.1超启发式算法基本概念 43

2.2.2超启发式算法的分类 44

2.2.3超启发式算法框架——HyFlex 48

2.3超启发式算法与启发式算法的对比 52

2.3. 1超启发式算法与启发式算法的多视角对比 52

2.3.2超启发式算法研究展望 53

2.4历史文献评注 56

参考文献 58

第三章 骨架的计算复杂性理论 64

3. 1骨架的概念 64

3.1.1骨架的提出及研究意义 64

3.1.2解的定义方式与骨架 65

3.2骨架与相变的相关性 65

3. 3骨架与后门的相关性 67

3.4骨架的计算复杂性 67

3.4. 1分析骨架计算复杂性的一般性方法 67

3. 4. 2 GBP问题的骨架计算复杂性分析 68

3. 4. 3 p-中位问题的骨架计算复杂性分析 73

3.4.4加权Max-SAT问题的骨架计算复杂性分析 77

3. 5历史文献评注 80

参考文献 81

第四章 骨架的获取 83

4. 1限界交叉方法 83

4.1.1直接判定骨架变量方法 83

4.1.2限界交叉方法的基本思想 84

4.1.3限界交叉方法实例 85

4.1.4限界交叉方法的改进 92

4.2局部最优解近似法 96

4.2. 1适应度地貌 96

4. 2.2大坑猜想 98

4.2.3基于大坑猜想的解模型 99

4. 3其他方法 107

4.4历史文献评注 110

参考文献 110

第五章 基于骨架的启发式算法 113

5. 1基于实例归约的骨架算法 113

5.1.1算法流程 113

5. 1. 2 TSP问题上的应用 115

5.1.3聚类问题上的应用 116

5.2基于初始解构造的骨架算法 121

5.2.1算法流程 121

5.2. 2聚类问题上的应用 122

5.2.3不确定聚类问题上的应用 123

5.3历史文献评注 126

参考文献 128

第六章 骨架研究的完整应用示例 129

6. 1 QAP问题 129

6. 1. 1问题定义 129

6. 1.2骨架的计算复杂性分析 130

6. 1.3基于偏移实例的近似骨架算法 136

6.1.4实验结果及分析 139

6. 2 GPP问题 140

6.2. 1问题定义 141

6.2. 2骨架的计算复杂性分析 141

6.2.3基于偏移实例的IBS算法 144

6.2.4实验结果及分析 146

6. 3 NRP问题 147

6. 3. 1问题定义 147

6.3.2骨架的计算复杂性分析 150

6.3.3基于近似骨架的多级算法 152

6.3.4实验结果及分析 157

6.4历史文献评注 159

参考文献 161

第七章 骨架的相关概念研究 165

7. 1脂肪 165

7.1.1脂肪研究的概述 165

7.1.2脂肪的计算复杂性 166

7.1.3基于脂肪的启发式算法设计 168

7. 1.4实验结果及分析 172

7. 2肌肉 173

7.2. 1肌肉研究的概述 173

7.2.2肌肉的计算复杂性 174

7.2.3基于肌肉的启发式算法设计 177

7.2. 4实验结果及分析 182

7.3历史文献评注 183

参考文献 184

附录A N-皇后问题的快速局部搜索算法 186

附录B加速的限界交叉算法 193