그리디 알고리즘(5)[집합 커버 문제 SetCover]

U는 노드들의 집합.

F는 U집합의 부분 집합인 S들을 요소로 하는 집합. 

 

최적해는 2**n - 1 의 연산을 통해 구할 수 있다.(n은 U 원소의 갯수)

ㅡ> a, b ,c 가 있으면 a, b, c, a+b, a+c, b+c, a+b+c 이렇게 모두 다 찾아본다는 의미.

 

하지만 O(2**n)은 너무나 값이 커진다.

 

그래서 SetCover은 근사해를 찾는다. (근사해란 최적해에 가까운 값을 가진 해를 말한다.)

 

 

이 근사해를 구하는 시간 복잡도는  O(n**3) 이다.

 

---

< SetCover 의사코드(슈도코드, pseudocode) >

 

입력: U, F={Si}, i=1,2 ~ ,n

출력: 집합 커버 C

1  C =  ∅

2  while (U !=  ∅ ) {

3        U의 원소들을 가장 많이 포함하고 있는 집합 Si를 F에서 선택한다. // 그리디

4        U = U - Si

5        Si를 F에서 제거하고, Si를 C에 추가한다. 

   }

6  return C

 

line2 : U가 공집합이 되면 멈춘다. ㅡ> line4의 반복작업으로 U의 요소가  ∅ 이 될때 까지반복.

 

line3 : Si를 뽑는 기준은 가장 큰 Si가 아니라, U의 요소를 가장 많이 갖고있는 Si 이다. 

(U = {1} 이면, S1 = {1}, S2 = {2,3,4,5,6,7,8,9} 라면 무조건 S1이 line3에서 채택되는 것)

 

line4 : Si와  U에 둘다 포함된 것들을 제거한다. 

 

line5 : F에서 lin4때 쓴 Si를 제거. (그 Si가 다시 선택되지 않도록 한다.) 그 Si는 C로 옮긴다.

---

<시간 복잡도 구하기>

 

루프는 총 n번 돈다.O(n)

 

루프가 1번 돌때 기준으로.

line3에서

Si와 U를 비교하여 가장 많은 U를 포함한 Si를 구하는 것은 Si들의 수가 최대 n이라면..

둘의 비교는 O(n**2)이 걸린다.

 

시간 복잡도는 O(n) * O(n**2) = O(n**3)