黑白二次分配问题

• 作者: 张宪超 李明楚 江贺 陈国良
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 黑白二次分配问题 NP-难解 启发式算法 黑白图 支配集
• 年，卷（期）: 2007,（3）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 440-447
• 页数: 8页
• 分类号: TP3
• 字数: 6517字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.03.011

摘要

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>O).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李明楚	大连理工大学软件学院	63	300	11.0	14.0
2	陈国良	中国科技大学计算机科学与技术系	18	165	8.0	12.0
3	张宪超	大连理工大学软件学院	29	428	12.0	20.0
4	江贺	大连理工大学软件学院	47	513	12.0	21.0