计算机难解问题的骨架理论与应用PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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

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

1. 2 P与NP2

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超启发式算法框架——HyFlex48

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