点击次数：

论文类型：期刊论文

发表时间：2011-01-01

发表刊物：自动化学报

收录刊物：EI、PKU、ISTIC、CSCD

卷号：37

期号：3

页面范围：257-269

ISSN号：0254-4156

关键字：NP-难解; 骨架; 启发式算法; 计算复杂性

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