自动化学报2011，Vol.37Issue(3)：257-269,13.DOI:10.3724/SP.J.1004.2011.00257
启发式算法设计中的骨架分析与应用
Backbone Analysis and Applications in Heuristic Algorithm Design
摘要
Abstract
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.关键词
NP-难解/骨架/启发式算法/计算复杂性引用本文复制引用
江贺,邱铁,胡燕,李明楚,罗钟铉..启发式算法设计中的骨架分析与应用[J].自动化学报,2011,37(3):257-269,13.基金项目
国家自然科学基金(60805024,61033012),大连市自然科学基金201000117)资助 （60805024,61033012）
