《计算机学报》文章摘要   全文下载
文章题目	黑白二次分配问题
作者	江贺1),2) 张宪超1) 陈国良2) 李明楚1)
作者单位	1)(大连理工大学软件学院 大连 116621) 2)(中国科技大学计算机科学与技术系 合肥 230027)
发表年份	2007
发表月份	3期(440—447)
文章摘要	摘要 二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题，该类问题在QAP问题的基础上增加了额外的约束条件：将设备分为黑白两色，其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性，指出该问题是NP-难解问题，不存在ε-近似度的多项式时间近似算法(ε>0).同时证明了其可行解的存在性与黑白图上的支配集问题等价，也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解，提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解，然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例. 关键词 黑白二次分配问题;NP-难解;启发式算法;黑白图;支配集 中图法分类号 TP301