개요

Set Covering Problem은 주어진 요소의 집합과 이를 포함하는 여러 부분 집합이 있을 때, 모든 요소를 포함하는 최소한의 부분 집합을 찾는 문제이다. 주로 Greedy 알고리즘을 통해 해결한다.

전략

1. 현재 가장 많은 요소를 커버하는 부분 집합을 반복적으로 선택

2. 선택된 부분 집합에 포함된 요소들을 전체 요소 집합에서 제거한 후, 남은 요소들에 대해 다시 가장 많은 요소를 커버하는 부분 집합을 선택

3. 이 과정을 모든 요소가 커버될 때까지 반복

구현

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10}

S1 = {1, 2, 3, 8}
S2 = {1, 2, 3, 4, 8}
S3 = {1, 2, 3, 4}
S4 = {2, 3, 4, 5, 7, 8}
S5 = {4, 5, 6, 7}
S6 = {5, 6, 7, 9, 10}
S7 = {4, 5, 6, 7}
S8 = {1, 2, 4, 8}
S9 = {6, 9}
S10 = {6, 10}

위 예제를 입력으로 하는 Set Covering algorithm을 작성

#include <stdio.h>
#define MAX_ELEMENT 10
int main() {
	int u[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int f[10][MAX_ELEMENT] =
	{ 
		{1, 2, 3, 8}, {1, 2, 3, 4, 8}, {1, 2, 3, 4}, {2, 3, 4, 5, 7, 8}, {4, 5, 6, 7}, 
		{5, 6, 7, 9, 10}, {4, 5, 6, 7}, {1, 2, 4, 8}, {6, 9}, {6, 10} 
	};
	
	//집합당 원소 개수 
	int setSize[] = {4, 5, 4, 6, 4, 5, 4, 4, 2, 2}; 
	// 집합 사용여부
	int isUse[10] = {0,}; 
	// 남은 원소 체크 
	int check[10] = {0,}; 
	
	int i, j;
	int remove; 
	int element = 10;
	int mostSet = 0; 
	int mostCount = 0; 
	int size;
	int mostSetSize = 0; 
	printf("C = { ");
	
	//공집합이 될때까지 
	while (element != 0) {
		mostCount = 0; 
		mostSetSize = 0;
		mostSet = 0;
		for (i =0; i <10; i++) {
			size = setSize[i]; 
			remove = 0;
			if (isUse[i] == 0) { 
				for (j = 0; j < size; j++) {
					if (check[f[i][j] - 1] == 0) {
						remove++;
					}
				}
				//가장 많은 원소를 공유한 집합 저장 
				if (mostCount < remove) {
					mostCount = remove;
					mostSetSize = size;
					mostSet = i;
				}
			}
		}
		element -= mostCount; 
		isUse[mostSet] = 1;
		printf("S%d ", mostSet+1); //사용한 집합 
		for (j =0; j < mostSetSize; j++) {
			check[f[mostSet][j] - 1] =1; //전체 집합에서 제거 
		} 
	}
	printf("}\n");
	return 0;
}