Release Time:2019-03-11  Hits:

Indexed by: Journal Article

Date of Publication: 2011-01-01

Journal: 自动化学报

Included Journals: CSCD、ISTIC、PKU、EI

Volume: 37

Issue: 3

Page Number: 257-269

ISSN: 0254-4156

Key Words: NP-难解; 骨架; 启发式算法; 计算复杂性

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