点击次数：

论文类型： 期刊论文

发表时间： 2007-03-30

发表刊物： 计算机学报

收录刊物： EI、PKU、ISTIC、CSCD

卷号： 30

期号： 3

页面范围： 440-447

ISSN号： 0254-4164

关键字： 黑白二次分配问题;NP-难解;启发式算法;黑白图;支配集

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