计算机难解问题的骨架理论与应用

　　前言
　　第一章 计算机难解问题与计算复杂性理论
　　1．1 现实世界中的难解问题
　　1．2 P与NP
　　1．2．1 问题与实例
　　1．2．2 多项式时间算法与指数时间算法
　　1．3 P类与NP类问题
　　1．4 典型的NP-难解问题
　　1．4．1 TSP问题
　　1．4．2 QAP问题
　　1．4．3 p-中位问题
　　1．5 历史文献评注
　　参考文献
　　第二章 求解难解问题的非精确算法
　　2．1 启发式算法
　　2．1．1 局部搜索
　　2．1．2 贪心算法
　　2．1．3 禁忌搜索
　　2．1．4 模拟退火
　　2．1．5 遗传算法
　　2．1．6 蚁群算法
　　2．1．7 拟物拟人算法
　　2．2 超启发式算法
　　2．2．1 超启发式算法基本概念
　　2．2．2 超启发式算法的分类
　　2．2．3 超启发式算法框架--HyFlex
　　2．3 超启发式算法与启发式算法的对比
　　2．3．1 超启发式算法与启发式算法的多视角对比
　　2．3．2 超启发式算法研究展望
　　2．4 历史文献评注
　　参考文献
　　第三章 骨架的计算复杂性理论
　　3．1 骨架的概念
　　3．1．1 骨架的提出及研究意义
　　3．1．2 解的定义方式与骨架
　　3．2 骨架与相变的相关性
　　3．3 骨架与后门的相关性
　　3．4 骨架的计算复杂性
　　3．4．1 分析骨架计算复杂性的一般性方法
　　3．4．2 GBP问题的骨架计算复杂性分析
　　3．4．3 声冲位问题的骨架计算复杂性分析
　　3．4．4 加权Max-sAT问题的骨架计算复杂性分析
　　3．5 历史文献评注
　　参考文献
　　第四章 骨架的获取
　　4．1 限界交叉方法
　　4．1．1 直接判定骨架变量方法
　　4．1．2 限界交叉方法的基本思想
　　4．1．3 限界交叉方法实例
　　4．1．4 限界交叉方法的改进
　　4．2 局部最优解近似法
　　4．2．1 适应度地貌
　　4．2．2 大坑猜想
　　4．2．3 基于大坑猜想的解模型
　　4．3 其他方法
　　4．4 历史文献评注
　　参考文献
　　第五章 基于骨架的启发式算法
　　5．1 基于实例归约的骨架算法
　　5．1．1 算法流程
　　5．1．2 TSP问题上的应用
　　5．1．3 聚类问题上的应用
　　5．2 基于初始解构造的骨架算法
　　5．2．1 算法流程
　　5．2．2 聚类问题上的应用
　　5．2．3 不确定聚类问题上的应用
　　5．3 历史文献评注
　　参考文献
　　第六章 骨架研究的完整应用示例
　　6．1 QAP问题
　　6．1．1 问题定义
　　6．1．2 骨架的计算复杂性分析
　　6．1．3 基于偏移实例的近似骨架算法
　　6．1．4 实验结果及分析
　　6．2 GPP问题
　　6．2．1 问题定义
　　6．2．2 骨架的计算复杂性分析
　　6．2．3 基于偏移实例的ms算法
　　6．2．4 实验结果及分析
　　6．3 NRP问题
　　6．3．1 问题定义
　　6．3．2 骨架的计算复杂性分析
　　6．3．3 基于近似骨架的多级算法
　　6．3．4 实验结果及分析
　　6．4 历史文献评注
　　参考文献
　　第七章 骨架的相关概念研究
　　7．1 脂肪
　　7．1．1 脂肪研究的概述
　　7．1．2 脂肪的计算复杂性
　　7．1．3 基于脂肪的启发式算法设计
　　7．1．4 实验结果及分析
　　7．2 肌肉
　　7．2．1 肌肉研究的概述
　　7．2．2 肌肉的计算复杂性
　　7．2．3 基于肌肉的启发式算法设计
　　7．2．4 实验结果及分析
　　7．3 历史文献评注
　　参考文献
　　附录A N-皇后问题的快速局部搜索算法
　　附录B 加速的限界交叉算法

　　骨架理论是有效解决规模日益扩大的计算机难解问题的新途径，是当 前智能计算领域的研究热点之一。　　《计算机难解问题的骨架理论与应用》（作者贾焕金）主要介绍面向计 算机难解问题的骨架特征的挖掘及其算法设计。《计算机难解问题的骨架 理论与应用》首先介绍了计算复杂性理论，并简要归纳了经典启发式算法 及超启发式算法。在此基础上，本书重点阐述了骨架的概念，并归纳r骨架 与计算复杂性理论的关系，深入介绍丁如何分析骨架的计算复杂性。随后 ，本书介绍了获取骨架的有效方法，并系统地总结了现有的各种基于骨架 的算法。为了便于运用本书阐述的算法，书后附有部分算法的源程序。　　本书可供理工科大学计算机、软件工程和人工智能等专业的教师及研 究生阅读，也可供自然科学和工程领域中的研究人员参考。