%0 Journal Article
%T Backbone Analysis and Applications in Heuristic Algorithm Design<br>启发式算法设计中的骨架分析与应用
%A JIANG He
%A QIU Tie
%A HU Yan
%A LI Ming-Chu
%A LUO Zhong-Xuan
%A <br>江贺
%A 邱铁
%A 胡燕
%A 李明楚
%A 罗钟铉
%J 自动化学报
%D 2011
%I 
%X 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.
%K NP-hard
%K backbone
%K heuristic algorithm
%K computational complexity<br>NP-难解
%K 骨架
%K 启发式算法
%K 计算复杂性
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=E76622685B64B2AA896A7F777B64EB3A&aid=E362A11B97F5F5631A6FC8FB10EB71E1&yid=9377ED8094509821&vid=42425781F0B1C26E&iid=38B194292C032A66&sid=4290346F7268639E&eid=1A363081E1FF7014&journal_id=0254-4156&journal_name=自动化学报&referenced_num=0&reference_num=0