[알고리즘] 집합 커버 문제 (Set Cover)

그리디 알고리즘을 이용해 푸는 문제 중 하나인 집합 커버 문제를 보자

- n개의 원소를 가진 전체 집합 U
- U의 부분집합 Si 를 원소로 갖는 집합 F
- F의 원소들인 Si 를 합집합하여 U가 되는 Si 의 최소 개수를 찾아야함

 

예를 들어 생각해보자

 

[신도시 학교 배치] 

- 10개의 마을이 신도시에 만들어질 계획
- 다음 조건을 만족하는 학교의 위치 선정을 해야함

  º 학교는 마을에 위치해야함
  º 등교 거리는 걸어서 15분 이내

- 어느 마을에 학교를 신설해야할까?

- 2번 마을에 만들면 마을 1, 3, 4, 8 커버
- 6번 마을에 만들면 마을 5, 7, 9, 10 커버

> 전체 마을이 커버됨 > 최소 마을 개수 : 2개

이걸 어떻게 집합 커버 문제로 풀 수 있을까?

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} // 신도시의 마을 10개
F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10}

Si = 마을 i에 학교를 배치했을 때 커버되는 마을의 집합

S1 = {1, 2, 3, 8}  > 마을 1을 기준으로 15분 이내에 갈 수 있는 마을
S2 = {1, 2, 3, 4, 8} > 마을 2을 기준으로 15분 이내에 갈 수 있는 마을
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}

Si 집합들 중에서 어떤 집합들을 선택하여야 그들의 합집합이 U와 같을까?
(단, 선택된 집합의 수는 최소이어야 한다.)
답은 S2 ∪ S6 = {1, 2, 3, 4, 8} ∪ {5, 6, 7, 9, 10} = {1, 2, 3, 4, 5, 6, 7, 8, 9 10} = U

 

집합 커버 문제의 최적해는 조합을 모두 비교해야하기 때문에 실질적으로 정확한 최적해를 찾는것은 불가능하다
따라서 최적해가 아닌 최적해에 근접한 근사해를 찾는다

근사해를 찾는 알고리즘 (pseudo code)

SetCover // line 1

입력: U, F={Si}, i=1,2,...,n // line 2
출력: 집합 커버 C // line 3

C = ∅ // line 4
 
while (U ≠ ∅) do { // line 5
  U의 원소들을 가장 많이 포함하고 있는 집합 Si를 F에서 선택한다. // line 6
  U = U - Si  // line 7
  Si를 F에서 제거하고, Si를 C에 추가한다.  // line 8
}   // line 9

return C   // line 10

Line 4 : C = ∅로 초기화한다.

Line 5 : while-조건 (U ≠ ∅)을 만족한다.

Line 6 : U의 원소들을 가장 많이 커버하는 집합인 S4 = {2, 3, 4, 5, 7, 8} 를 F에서 선택한다.

Line 7 : U= U - S4 = {1, 6, 9, 10}

Line 8 : S4를 F에서 제거, 즉, F = {S1, S2, S3, S5, S6, S7, S8, S9, S10}  / S4를 C에 추가, 즉, C = {S4}

Line 5 : while-조건 만족

Line 6 : U의 원소들을 가장 많이 커버하는 집합인 S6 = {5, 6, 7, 9, 10} 를 F에서 선택.

Line 7 : U= U - S6 = {1]

Line 8 : S6를 F에서 제거, F = {S1, S2, S3, S5, S7, S8, S9, S10} / S6를 C에 추가, C = {S4, S6}

Line 5 : while-조건 만족

Line 6 : U의 원소들을 가장 많이 커버하는 집합인 S1을 F에서 선택.
(S2, S3, S8을 선택해도 무방)

Line 7 : U = ∅

Line 8 : S1을 F에서 제거,
S1을 C에 추가, C = {S1, S4, S6}

Line 5 : while-조건 불만족

Line 9 : C={S1, S4, S6}를 리턴

 

시간복잡도

Line 5 : while-루프 조건 검사 시간 O(1)
Line 6 : Si 각각을 U와 비교하여야 한다. Si들의 수가 최대 n이라면, O(n^2) 시간
Line 7 : 집합 U에서 집합 Si의 원소를 제거, O(n) 시간이 걸린다.
Line 8 : Si를 F에서 제거, Si를 C에 추가, O(1) 시간이 걸린다.
따라서 루프 1회의 시간 복잡도는 O(1)+O(n^2)+O(n)+O(1) = O(n^2)이다.

그러므로 SetCover 알고리즘의 시간복잡도 :  O(n)*O(n^2) = O(n^3)