數據結構 集合_集合實例（集合覆蓋）

集合覆蓋是一種優化求解問題，對很多組合數學和資源選擇問題給出了很好的抽象模型。 問題如下：給定一個集合S，集合P由集合S的子集A1到An組成，集合C由集合P中的一個或多個子集組成。如果S中的每個成員都包含在C的至少一個子集中則稱集合C覆蓋集合S。此外，C包含的P的子集越少越好。

設想從一大群選手中挑選人員組建一支隊伍，每名選手都擁有特定的技能組合。目標是組建出一隻最小的隊伍，使得隊伍整體擁有一組特定的技能組合。也就是說，對於隊伍整體所需要的技能，隊伍中至少有一名選手必須擁有這項技能。假定S為隊伍所必須擁有的技能集合，P為所有待選選手的技能集合。從P中挑選出一些技能組合以構成C，C必須覆蓋S中所要求的所有技能。重要一點，我們選擇的選手數量必須儘可能少。

針對集合覆蓋的演算法是一種近似演算法，它並不總是獲得最優解。該演算法的工作原理是：

不斷從P中選出一個集合，使其能夠覆蓋S中最多的成員數量。換句話說，該演算法每次都嘗試儘可能早覆蓋S中更多的成員，因此該演算法採用了貪心法的思路。由於每個集合都是從P中選出的，如果P被移除，則它的成員也將從S中移除。當P中剩餘的成員沒有任何集合能夠覆蓋S中的成員時，此時覆蓋集合C就完成了。

讓我們看看對於12種技能的集合S={a,b,c,d,e,f,g,h,i,j,k,l}的最佳覆蓋集。現在考慮有7名待選選手的集合P={A1,...A7}。P中選手擁有的技能集合為：A1={a,b,c,d}，A2={e,f,g,h}，A3={j,k,l}，A4={a,e}，A5={b,f,g}，A6={c,d,g,h,k,l}，A7={l}。最佳覆蓋集應該是C={A1,A2,A3}。這裡給出的演算法選擇的集合是C={A6,A2,A1,A3}（見圖1）。

集合覆蓋問題的函數實現

我們使用函數cover，該函數在集合P的子集A1~An中挑選出能夠覆蓋集合S的近似最優解。該函數有3個參數：

1、members是待覆蓋的集合S；

2、subsets是集合P中的子集；

3、covering作為返回的覆蓋集C。

該函數將修改所傳入的3個參數，因此在調用該函數時，如果有必要話應該保存一份參數的拷貝。

函數執行過程：開始時，covering通過調用set_init先得到初始化。

我們使用迴圈進行迭代，只要members中還有未覆蓋的成員，且subsets中的子集還沒有挑選完，最外層的迴圈就得繼續迭代。

在這個迴圈中，每次迭代時它都在subsets中找出能夠覆蓋到members的最大交集。

然後它將這個集合加到覆蓋集covering中並把它的成員從members中移除（因為這些成員已經被覆蓋，下一次迭代將判斷剩餘的成員能否被覆蓋）。在迴圈的最後，將所選擇的這個集合從subsets中移除（已經選中的要移除）。如果最外層的迴圈因為members不為空而終止迭代，則表示subsets中的集合不可能滿足完全覆蓋members的要求。同樣，如果在迭代期間subsets中的成員無法與members的成員形成交集，則同樣表示subsets中的成員無法滿足完全覆蓋members的要求。函數cover如果找到了一個完全覆蓋解，該函數返回0，參數covering指向這個完全覆蓋解；如果不可能實現完全覆蓋，則返回1；其他情況返回-1。

cover的複雜度為O(m³)，這裡的m代表members集合中的初始成員個數。在最壞的情況下，對於members中的每一員，subsets中都只有唯一一個子集與之對應，此時的複雜度是O(m_³)。在這種情況下，subsets有 m個子集，set_intesection以O(m)的複雜度執行，因為當計算和members求交集時，subsets的每個子集都只有唯一一個個成員需要遍歷。因此cover的內層迴圈是O(m²)的，而這個迴圈要執行m次。

示例1：集合覆蓋問題的頭文件

#ifndef COVER_H
#define COVER_H

#include "set.h"

typedef struct KSet_
{
    void *key;
    Set set;
}KSet;

int cover(Set *member, Set *subsets, Set *covering);

#endif 

 示例2：集合覆蓋問題的函數實現

#include <stdlib.h>
#include "cover.h"
#include "list.h"
#include "set.h"

int cover(Set *members, Set *subsets, Set *covering)
{
    Set intersection;
    KSet *subset;
    ListElmt *member,*max_member;
    void *data;
    int max_size;
    
    /*初始化覆蓋集covering*/
    set_init(covering,subsets->match,NULL);
    
    while(set_size(members)>0 && set_size(subsets)>0)
    {
        /*找到能夠覆蓋最多members成員的子集*/
        max_size = 0;
        for(member = list_head(subsets);member!=NULL;member=list_next(member))
        {
            if(set_intersection(&intersection, &((KSet *)list_data(member))->set, members) != 0)
                return -1;
            
            if(set_size(&intersection)>max_size)
            {
                max_member = member;
                max_size = set_size(&intersection);
            }
            
            set_destroy(&intersection);
        }
        /*如果不存在交集，那麼就不可能有覆蓋集*/
        if(max_size==0)
            return 1;
        
        /*將被選到的子集插入覆蓋集covering中*/
        subset = (KSet *)list_data(max_member);
        
        if(set_insert(covering,subset) != 0)
            return -1;
        
        /*從members中移除已經被覆蓋的元素*/
        for(member=list_head(&((Kset *)list_data(max_member))->set);member != NULL;
            list_next(member))
        {
            data = list_data(member);
            if(set_remove(members,(void **)data)== 0 && members->destroy != NULL)
                members->destroy(data);
        }
        
        /*從子集集合中刪除已經被選用的子集*/
        if(set_remove(subsets,(void **)&subset) != 0)
            return -1;
    }
    
    /*如果members中仍然存在未被覆蓋的元素，那麼也不可能實現完全覆蓋*/
    if(set_size(members)>0)
        return -1;
    
    return 0;
}