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

摘要：

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

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

所属期刊栏目：38

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60673046;60673066;辽宁省自然科学基金20051082;大连理工大学青年教师培养基金

在线出版日期：2009-04-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：209-222