最小集合覆盖的启发式算法 摘 要 本文给出了一种求解集合覆盖问题的新的启发式算法，对该算法的合理性、 时间复杂性以及解的精度进行了分析。主要创新点是用完备策略建立启发式算 法。该方法具有一定的普遍性、可行性，可以应用到其他的 NP 困难问题。 关键词：最小集合覆盖；启发式算法；完备策略；NP 困难问题 集合覆盖问题是 NP 困难问题中具有代表性的问题之一，它在模式识别、机 器学习等领域中具有重要的应用。目前已有许多比较有效的启发式算法，但由于 问题本身固有的难度，这些启发式算法具有各种的缺陷，本文提出的启发式算法 由多个启发式策略组成，同时考虑到计算复杂度，具有一定的效果。 1 相关概念和完备策略 最小集合覆盖问题：S 是一个集合，S1，S2，…，Sm 是 S 的子集，且构成 S 的覆盖，即∪Si=S，求最小覆盖。 例 1 设 S={0，1，2，3，4，5，6，7，8，9}；S1={0，1，2，3，4}； S2={0，1， 5，6，7}；S3={3，4，5，6，7}；S4={5，6，7，9}； S5={2，8，9}；S6={1，3，5，7}；S7={0，4，6，8}； S8={0，3，6}；S9={1，4，7} 定义 1 设 NPH(NP-hard)是一个给定的 NP 困难问题（例如，集合覆盖问 题，TSP 等），ST 是一个求解 NPH 的策略，如果 ST 的前提条件的验证以及策略 的操作者都可以在多项式时间内完成，则称 ST 为多项式时间策略。 一般的启发式策略都是多项式时间策略，例如，集合覆盖问题，选取最大 基数的集合作为覆盖中的一员；对 TSP 来说，选择最邻近的点构成回路等都是 多项式策略。 定义 2 NPH 是一个 NP 困难问题，ST 是求解 NPH 的一个多项式时间策略， NPHO 是 NPH 经过 ST 操作后得到的一个新的问题，如果问题 NPHO 的规模比 问题 NPH 小，并且 NPHO 的最优解都是 NPH 的最优化解，则称 ST 为完备策略。 通俗地讲，一个完备策略是，当问题满足策略条件时，把原闸题化简成更 

易解的问题，并且新问题的最优化解都是原问题的最优化解，即保留一些最优化 解的策略。 在求解 NP 困难问题时，用完备策略既能降低问题的求解难度，又能保留 最优解，所以它是求解 NP 困难问题的最重要的策略(如果有的话)。因此用启发 式算法求解 NP 困难问题时，我们首先应该考虐寻找完备策略。 集合覆盖问题的完备策略： 完备策略 1 如果 S1，S2，…，Sm 中一个集合 Si=S，则选择 Si 作为最优 覆盖中的唯一一个集合 Si。 完备策略 2 如果存在 x∈S,x 只属于 S1，S2，…，Sm 中的一个集合 Si, 则选择 Si 作为最优化中的一个集合 Si。 完备策略 3 如果 Si⊆Sj，则排出 Si。 完备策略 4 Sn(x)表示包含 x∈S 集合的序号组成的集合，即 Sn(x)=|x∈S|， 如果 Sn(x) ⊆Sn(y)，则删除 S 中的元素 y. 下表给出了例 1 的特征矩阵 A，元素 aij=1 表示第 i 个集合 S 的元素在子 集 Sj 中出现，aij=0 表示没有出现： 表 1 例 1 的特征矩阵 S1 1 1 1 1 1 0 0 0 0 0 5 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) |Si| S2 1 1 0 0 0 1 1 1 0 0 5 S3 0 0 0 1 1 1 1 1 0 0 5 S4 0 0 0 0 0 1 1 1 0 1 4 S5 0 0 1 0 0 0 0 0 1 1 3 S6 0 1 0 1 0 1 0 1 0 0 4 S7 1 0 0 0 1 0 1 0 1 0 4 S8 1 0 0 1 0 0 1 0 0 0 3 S9 0 1 0 0 1 0 0 1 0 0 3 不难看出以上四个策略都是多项式时间策略，下面依次来证明四个策略满 足定义 2。 策略 1 显然满足定义 2. 考虑策略 2，当问题的实例满足策略 2 的条件时，即存在 x∈S 只属于覆盖 中的一个集合，不妨设 x∈S1，则 S1 一定在任何覆盖中（否则不能形成一个覆 

盖），于是 S1 属于任何一个最优化覆盖中，这就是说，选择 S1 之后求解难度降 低了，但还保留着所有最优化覆盖，故策略 2 是完备策略。 考虑策略 3，问题的实例满足策略 3 的条件时，即存在两个集合 Si，Sj 满 足 Si⊆Sj，如果一个最优覆盖含有 Si 之后，则在覆盖中用 Sj 来代替 Si 后仍然是 一个最优化覆盖，故排出 Si 之后问题的难度降低了，但不增加最优化覆盖，因 此策略 3 是完备策略。 考虑策略 4，问题的实例满足策略 4 的条件时，即存在两个集合 Sn(x)，Sn(y) 满足 Sn(x) ⊆Sn(y)，则包含 x 的集合都包含了 y，所以覆盖 x 的任何一个覆盖总 能覆盖 y，于是删除 S 中的元素 y 之后问题的难度降低了，但并增加最优化覆盖， 因此策略 4 是完备策略。 2 启发式算法 在上节中给出了四个完备策略，在这一节中我们给出基于完备策略的启发函 数算法。 初值，COVER={Φ}，COVER0={S1，S2，…，Sm}； 第一步：如果 S1，S2，…，Sm 中的一个集合 Si=S，则 COVER=COVER+{Si}， 停止。 第二步：如果存在 x∈S,x 只属于 S1，S2，…，Sm 中的一个集合 Si，则 COVER=COVER+{Si}，COVER0=COVER0-{Si}，S=S-{Si}。 第三步：如果存在两个集合 Si⊆Sj，则 COVER0=COVER0-{Si}。 第四步：如果存在两个元素 x，y∈S，满足 Sn(x) ⊆Sn(y)，则 S=S-{y}。 第五步：如果上述四个条件都不满足，则选择一个基数最大的集合 Si， COVER=COVER+{Si}，COVER0=COVER0-{Si}，S=S-{Si}，返回第一步。 下面以例 1 的数据为例来详细说明本算法的求解过程。 第一步：不满足完备策略 1、2、3，现在看是否满足策略 4，现列出包含每 个元素的集合序列： Sn(2)=S1 S5 Sn(5)=S2 S3 S4 S6 Sn(1)=S1 S2 S6 Sn(4)=S1 S3 S7 S9 Sn(0)=S1 S2 S7 S8 Sn(3)=S1 S3 S6 S8 Sn(6)= S2 S3 S4 S6 S7 S8 Sn(7)=S2 S3 S4 S6 S9 Sn(8)=S5 S7 由上可知存在两个元素 5、7∈S，满足 Sn(5) ⊆Sn(7)，故 S=S-{7}= Sn(9)=S4 S5 {0、1、2、3、4、5、6、8、9}。 删除元素 7 后的集合序列变为： S1={0，1，2，3，4}； S2={0，1， 5，6}；S3={3，4，5，6}； S4={5，6，9}；S5={2，8，9}；S6={1，3，5}；S7={0，4，6，8}； S8={0，3，6}；S9={1，4} 

第二步：不满足完备策略 1、2，但满足完备策略 3，即存在两个集合 S9⊆S1，故 COVER0=COVER0-{S9}，即 COVER0={S1 S2 S3 S4 S5 S6S 7S8}。 第三步：四个完备策略都不满足，所以选择基数最大的集合，在第二步 删除元素 7 和 S9 后每个集合的基数变为： ∣S1∣=5 ∣S2∣=4 ∣S3∣=4 ∣S4∣=3 ∣S5∣=3 ∣S6∣=3 ∣S7∣=4 ∣S8∣=3 由 上 可 知 基 数 最 大 的 集 合 为 S1 ， COVER=COVER+{S1} ， COVER0=COVER0-{S1}，S=S-S1，即 COVER={S1}，COVER0={S2 S3 S4 S5 S6 S7 S8}，S={5、6、8、9}。 将 S2，S3，…，Sm 中与 S1 中重复的元素删除掉后的结果为： S2={5，6}，S3={5，6}，S4={5，6，9}， S5={8，9}，S6={5}，S7={6，8}，S8={6}。 第四步：不满足完备策略 1、2，但满足完备策略 3，即由第三步结果可 知，S2、S3、S6、S8⊆S4，故 COVER0=COVER0-{S2，S3，S6，S8}，即 COVER0= {S4，S5，S7}。 第五步：满足策略 2，即元素 5 只属于集合 S4，故 COVER=COVER+{S4}， COVER0=COVER0-{S4}，S=S-{S4}，即 COVER={S1 S4}，COVER0= {S5，S7}， S={8}，将 S5，S7 中与 S4 中重复的元素删除掉后的结果为：S5={8}，S7={8}。 第六步：由上一步结果可知只有元素 8 和包含该元素的两个集合 S5，S7， 故 COVER=COVER+{S5}，停止，最后得到的最小覆盖是 S1，S4，S5，不难看 出 S1，S4，S5 是例 1 的一个最优解。 3 算法的计算复杂性与解的精度估计 下面分析本文算法的计算复杂性： N 和 M 分别表示集合 S 的基数与集合的个数 1)完备策略 1 的计算复杂性为 O(NM)． 2)完备策略 2 的计算复杂性为 O(NM)． 3)完备策略 3 的计算复杂性为 O(NM2)． 4)完备策略 4 的计算复杂-睦为 O(N2M)． 5)“贪心”策略的计算复杂性为 O(NM)． 因此本算法的计算复杂性上界为 T(N，M)≤(O(NM)+O(NM)+O(NM2)+ O(N2M)(N+M) ≤O(NM(N+M)2) 

4 总结 本文以一个特定的例子详细讲解了求一个集合最小覆盖的启发式算法， 算法的核心思想就是循环不断的对集合进行扫描，判断是否符合完备策略， 然后根据完备策略的要求选出最小覆盖的集合，从而最终得到一个最优解。 参考文献 [1] 李国杰．人工智能的计算复杂性研究[J]．模式识别与人工智能，1992 [2] 姜成志，金光浩．集合覆盖问题的一种启发式算法[J]．黑龙江矿业学院学 报，1997 [3] 洪炳熔，叶风．集合覆盖问题的启发函数算法[J]．软件学报，1998 [4] 陈端兵，黄文奇．一种求解集合覆盖问题的启发式算法[J]．计算机科学， 2007 [5] 周海岩．最优集合覆盖的一种启发式算法[J]．忻州师范专科学校学报，2000 [6] 宋晓晨．集合覆盖问题的遗传算法求解方法[J]．黑龙江工程学院学报，2007