启发式算法设计中的骨架分析与应用

骨架是指一个NP-难解问题实例的所有全局最优解的相同部分, 因其在启发式算法设计中的重要作用而成为该领域的研究热点. 本文对目前骨架及相关概念的研究成果进行了全面综述, 将骨架本身的研究工作归纳为三个层面: 理论基础层面主要考虑骨架与计算复杂性的关系问题; 应用基础层面主要考虑如何高效地获取骨架; 应用层面主要考虑如何利用骨架进行高效启发式算法设计. 在此基础上, 本文详细讨论了骨架研究亟待解决的难题, 并指出了解决这些问题的努力方向.

Backbone Analysis and Applications in Heuristic Algorithm Design

As the shared common parts of all global optimal solutions to an NP-hard problem instance, the backbone has become a hot research line due to its essential impacts on the heuristic algorithm design. In this paper, research results on the backbone and related conceptions were thoroughly surveyed. The existing research of backbone consists of three areas, including the basic theoretical research focusing on investigation of the relationship between the backbone and computational complexity, the application research on how to efficiently approximate the backbone, and the applications on how to employ the backbone within the heuristic algorithm design. Furthermore, we discussed in detail the existing problems to be solved in this topic, and provided some guidelines on how to tackle them.