Hits:

Indexed by:期刊论文

Date of Publication:2008-01-01

Journal:中国科学. E辑, 技术科学

Included Journals:PKU、ISTIC、CSCD

Volume:38

Issue:2

Page Number:209-222

ISSN No.:1006-9275

Key Words:二次匹配问题; NP-难解; 骨架分析; 偏移实例; 元启发算法

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