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