Hits:

Indexed by:期刊论文

Date of Publication:2011-01-01

Journal:自动化学报

Included Journals:EI、PKU、ISTIC、CSCD

Volume:37

Issue:3

Page Number:257-269

ISSN No.:0254-4156

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

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