二次分配问题的骨架分析与算法设计  

作　　者：江贺[1] 张宪超[1] 陈国良[2] 李明楚[1] 

机构地区：[1]大连理工大学软件学院,大连116621 [2]中国科技大学计算机科学与技术系,合肥230027

出　　处：《中国科学（E辑）》2008年第2期209-222,共14页Science in China(Series E)

基　　金：国家自然科学基金(批准号:60673046,60673066);辽宁省自然科学基金(批准号:20051082);大连理工大学青年教师培养基金资助项目

摘　　要：骨架分析是近年来NP-难解问题研究的热点,对于衡量问题的相变、难度及算法设计具有重要意义.骨架的理论分析及在算法设计方面的应用还处于起步阶段.从QAP问题入手,对QAP骨架进行了理论分析,证明寻找QAP问题的骨架属于NP-难解问题,不存在多项式时间的算法可以保证得到QAP问题的骨架,为局部最优解交叉来获得近似骨架提供了合理性解释.在此基础上,利用偏移实例构造方法,提出了基于偏移实例的近似骨架算法.其基本思想是:首先为QAP实例构造偏移实例,其最优解恰是原QAP实例的一个全局最优解;然后利用现有算法求得新实例的多个局部最优解,通过对局部最优解求交得到近似骨架;将近似骨架固定以得到规模更小的搜索空间,最后在新空间上求解.拓广了骨架理论研究的范围,所提出的算法为NP-难解问题的通用算法设计提供了一种新思路.

关 键 词：二次匹配问题 NP-难解 骨架分析 偏移实例 元启发算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]