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

本书主要介绍面向NP-难解问题的骨架特征的挖掘及其启发式算法设计。给定一个NP-难解问题的实例，骨架是指它的所有全局最优解的共同部分。本书首先介绍了与NP-难解问题相关的计算复杂性理论（包括P和NP的关系、Cook定理及NP-完全问题定义等），并简要介绍了有效求解NP-难解问题的近似算法与常见的启发式算法。在此基础上，引入了骨架的概念，并归纳了骨架与计算复杂性相关理论（如相变、后门等）的关系，深入介绍了如何分析获取完整或者部分骨架的计算复杂性。随后，本书介绍了获取部分或近似骨架的可行方法，包括限界交叉，加速的限界交叉，局部最优解近似法等。利用部分或者近似骨架，本书系统地总结了现有的各种基于骨架的算法，包括确定型骨架算法和概率型骨架算法两大类。为了全面阐述骨架的研究方法，本书以软件的下一版本问题为例，给出该问题的骨架计算复杂性分析、骨架的近似及基于近似骨架的多级算法。最后，本书介绍了与骨架相关概念的研究现状。