胡 沁， 宁爱兵， 苟海雯， 张惠珍

(上海理工大学 管理学院,上海 200093)

0 引言

精确覆盖(exact cover, EC)及其各种变形问题在运筹学、管理学、组合数学和计算机科学等领域被广泛研究，例如针对阵列雷达子阵划分问题[1]，该问题可做如下简单概述：阵列雷达可分为许多子阵，然而囿于器件水平、系统成本及工程实现难度等因素的限制，每一子阵对区域的覆盖范围不同，其范围类似于若干个多联六边形组成的非规则形状。为了保证预警探测、空间监视等军事任务的安全性，在阵列雷达设计时，不仅需要保证对阵面全覆盖而且需要降低工程实现的难度，如何做到只用特定非规则形状的子阵对整个阵面进行精确覆盖是达到这一目标的核心问题。除此之外精确覆盖在信息科学[2]、自动化系统设计[3]、通信工程[4]及密钥管理[5]等诸多领域亦具有非常广泛的应用，因此精确覆盖问题具有极其重要的研究价值和意义，也是组合优化中经典的NP-Hard问题，除非P=NP，否则不存在多项式时间算法。

目前求解精确覆盖问题的算法主要分为精确算法和启发式算法。Donald Knuth在2000年首次提出了解决精确覆盖问题的精确算法——X算法[6]，但随着问题的规模和元素总个数的增加，求解问题的时间越来越长，随后有许多学者开始尝试改良X算法以加快求解速度[7]。近年来，大量学者开始尝试运用启发式算法求解精确覆盖问题，并取得了令人满意的结果，如量子算法[8]、绝热量子算法[9]、DNA计算机算法[10]、基于光学原理的算法[11]等。……