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

被引：3

作者：

江贺 ^{[1
]}

张宪超 ^{[1
]}

陈国良 ^{[2
]}

李明楚 ^{[1
]}

机构：

[1] 大连理工大学软件学院

[2] 中国科技大学计算机科学与技术系

来源：

中国科学(E辑:信息科学) | 2008年 / 02期

关键词：

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

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：209 / 222

页数：14

共 10 条

[1]

蚁群算法原理及其应用.[M].段海滨; 著.科学出版社.2005,

[2]

近世计算理论导引.[M].黄文奇;许如初著;.科学出版社.2004,

[3]

神经网络及其应用.[M].周志华;曹存根主编;.清华大学出版社.2004,

[4]

遗传算法及其应用.[M].陈国良等编著;.人民邮电出版社.1996,