| 二次分配问题的骨架分析与算法设计 |
| |
| 引用本文： | 江贺,;张宪超,;陈国良,;李明楚.二次分配问题的骨架分析与算法设计[J].中国科学(E辑),2008(2):209-222. |
| |
| 作者姓名： | 江贺 ;张宪超 ;陈国良 ;李明楚 |
| |
| 作者单位： | [1]大连理工大学软件学院,大连116621; [2]中国科技大学计算机科学与技术系,合肥230027 |
| |
| 基金项目： | 国家自然科学基金（批准号：60673046,60673066）、辽宁省自然科学基金（批准号：20051082）和大连理工大学青年教师培养基金资助项目感谢University of Applied Sciences of Western Switzerland的Eric Taillard教授提供的FANT源代码,Intel（上海）研发中心邹鹏博士提供ABFANT的相关文献及中国科技大学周智老师的有益帮助. |
| |
| 摘 要： | 骨架分析是近年来NP-难解问题研究的热点，对于衡量问题的相变、难度及算法设计具有重要意义．骨架的理论分析及在算法设计方面的应用还处于起步阶段，从QAP问题入手，对QAP骨架进行了理论分析，证明寻找QAP问题的骨架属于NP．难解问题，不存在多项式时间的算法可以保证得到QAP问题的骨架，为局部最优解交叉来获得近似骨架提供了合理性解释，在此基础上，利用偏移实例构造方法，提出了基于偏移实例的近似骨架算法．其基本思想是：首先为QAP实例构造偏移实例，其最优解恰是原QAP实例的一个全局最优解；然后利用现有算法求得新实例的多个局部最优解，通过对局部最优解求交得到近似骨架；将近似骨架固定以得到规模更小的搜索空间，最后在新空间上求解，拓广了骨架理论研究的范围，所提出的算法为NP-难解问题的通用算法设计提供了一种新思路。
|
| 关 键 词： | 二次匹配问题 NP-难解 骨架分析 偏移实例 元启发算法 |
| 本文献已被 维普 等数据库收录！ |
|
