计算机难解问题的骨架理论与应用
2013-1
江贺、胡燕、 李明楚 科学出版社 (2013-01出版)
《计算机难解问题的骨架理论与应用》内容简介：骨架理论是有效解决规模日益扩大的计算机难解问题的新途径，是当前智能计算领域的研究热点之一。 书中主要介绍面向计算机难解问题的骨架特征的挖掘及其算法设计。书中首先介绍了计算复杂性理论，并简要归纳了经典启发式算法及超启发式算法。在此基础上，《计算机难解问题的骨架理论与应用》重点阐述了骨架的概念，并归纳了骨架与计算复杂性理论的关系，深入介绍了如何分析骨架的计算复杂性。随后，介绍了获取骨架的有效方法，并系统地总结了现有的各种基于骨架的算法。为了便于运用《计算机难解问题的骨架理论与应用》阐述的算法，书后附有部分算法的源程序。
《计算机难解问题的骨架理论与应用》可供理工科大学计算机、软件工程和人工智能等专业的教师及研究生阅读，也可供自然科学和工程领域中的研究人员参考。
前言第一章 计算机难解问题与计算复杂性理论1.1 现实世界中的难解问题1.2 P与NP1.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 超启发式算法框架——HyFlex2.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 p-中位问题的骨架计算复杂性分析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 基于偏移实例的IBS算法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 加速的限界交叉算法
第一章 计算机难解问题与计算复杂性理论本章简要介绍计算机难解问题的基本概念及一些经典的难解问题。首先，以一个简单的周游全国大城市的例子，给出计算机难解问题的一个具体应用。其次，介绍计算复杂性理论（computational complexity theory）的一些基本概念，包括问题与实例的概念、多项式时间与指数时间算法、P类与NP类问题等。最后，较为详细地介绍本书中频繁使用到的几个经典的难解问题。1.1 现实世界中的难解问题在算法设计或者数据结构的很多知识体系中，存在很多有趣的问题，比如串的匹配问题、二叉树的查找问题等。这些问题均可以在较短的时间（多项式时间）内快速求解。然而，在现实世界中，还存在一大类问题，它们的结构或简单或复杂，但要获得这些问题的精确解却是极其困难的。一个简单的例子是：一位大学生规划在毕业后周游全国主要的大城市，比如北京、上海、天津、重庆、南京、长沙、合肥、大连。他计划从大连出发，经过上述每个城市一次，最后返回大连。现在的问题是：如何找到一条最合理的旅游路线，使得这位大学生的旅费最少？在这里，假设该大学生经过前期的调研，已经把各个城市之间直达的旅费调研清楚了。这个问题是一个非常有趣的问题，也非常简单易懂，在5min内就可以向任何一位小学生讲清楚。但是，如何获得该问题的精确解，却不像该问题的定义那么简单。可以用一个排列来表示解，比如大连→北京→天津→重庆→长沙→合肥→上海→南京→大连。一种直观的精确求解方法是穷举法，把所有的可能性都试一次，然后挑出最好的解。如果用这种求解方法，则共有7！种可能性（注意到是固定地从大连出发，又回到大连）。对于少量的城市数而言，这种穷举法是可行的，但是当城市数增加为100甚至更多时，需要尝试的解的个数则迅速增加而难以逐一枚举。另一种直观方法是采用贪心法，即从大连出发，每次挑选距离当前城市最近且没有访问过的城市作为下一个访问的城市，直到回到大连为止。这种方法显然速度比穷举法快得多，然而该方法是一种“鼠目寸光”的方法，并不能确保获得的是精确解，通过反例法很容易证实。实际上，上述例子就是经典的组合优化问题―――旅行商问题（traveling sales-man problem，TSP）的具体应用。在上述例子中，两个城市之间的旅费，也可以换成是城市间的距离、旅行时间等。而TSP问题的应用背景实际是十分广泛的，在交通调度、线路板设计、工业控制等诸多领域都能找到它的应用例子。以线路板设计为例，如何在线路板上放置若干个元器件，使得它们之间存在一条最短环路，以节省印制电路的成本？将元器件映射为城市，则该线路板设计问题就转化为TSP问题。需要注意的是，这个应用中城市的数量（通常也称为问题的规模）是成千上万的，采用穷举法，即便在目前的天河、蓝光等超级计算机上的运行时间也是难以接受的。有趣的是，TSP问题经过一些变换后，依然是很难求解的。比如，假设有些城市之间距离为无穷大（即两个城市间没有通车），那能否找到一条通过每个城市一次且回到出发地的环路？该问题实际上是另外一个难解问题，即哈密尔顿环路问题（Hamiltonian cycle problem）。另外一种针对TSP问题的变换是引入额外的目标函数，比如除了要求最少的旅费之外，还希望旅游线路的旅行时间最少。这实际上又将TSP问题转化为双目标优化问题。此时，精确解不再是单个解，而是一个解集。同时，由于两个目标之间可能相互冲突，因此这个解集通常被称为Pareto解集，即该解集中的任何一个解都不会比集合中其他解在两个目标上均更优。这种双目标优化问题通常比单个目标函数的问题更加困难。以上讨论的种种问题，都具有一些共同的特征，比如在多项式时间内难以精确求解，而若设计一些多项式时间复杂度的算法，通常只能给出一些近似的解。由于这类问题在实际应用中数量极其庞大，有必要在计算机科学及人工智能领域展开专门研究。1.2 P与NP本节将讨论P和NP的概念，它们是计算复杂性理论的基础定义，而计算复杂性理论则是整个计算机科学的基础。为了介绍P和NP的含义，本节将首先给出问题和实例的定义，然后再定义多项式时间和指数时间算法的概念。
《计算机难解问题的骨架理论与应用》(作者贾焕金)围绕着骨架在启发式算法设计中的功能，介绍了骨架所处理的NP-难解问题的计算复杂性理论、常见的求解NP-难解问题的启发式算法及超启发式算法、骨架与计算复杂性相关理论(如相变、后门等)的关系、完整或者部分骨架的计算复杂性分析方法、用于获取部分或近似骨架的有效方法、各种基于骨架的算法等。在本书的各个章节，注重实际NP-难解问题的求解。本书的主要章节均以实际问题为例，给出相关理论或算法的具体应用技巧。
