그리디 알고리즘 - 집합 커버 문제

집합 커버 문제

집합 커버 문제는 집합 F에서 선택하는 집합들의 수를 최소화하는 문제이다.

예시로 신도시 학교 배치 문제가 있다 

10개의 마을이 신도시에 만들어질 계획이다. 아래의 2가지 조건이 만족되도록 학교 위치를 선정해야 한다.

•학교는 마을에 위치해야 한다.

•등교 거리는 걸어서 15분 이내이어야 한다.

어느 마을에 학교를 신설해야 학교의 수가 최소가 되는가?

10개 마을의 위치 와 등교거리가 15분 이내인 마을간의 관계

사진을 문제로 변환 시키면

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}           S5={4, 5, 6, 7}            S9 ={6, 9}

S2={1, 2, 3, 4, 8}        S6={5, 6, 7, 9, 10}       S10={6, 10}

S3={1, 2, 3, 4}           S7={4, 5, 6, 7}

S4={2, 3, 4, 5, 7, 8}     S8={1, 2, 4, 8}

선택된 집합의 수가 최소이면서 합집합이 U와 같은 집합은 

S2∪S6 = {1, 2, 3, 4, 8}∪{5, 6, 7, 9, 10}

이다.

집합 커버 문제의 최적해를 찾는 방법 중 가장 간단한 것은 F에 있는 집합들의 모든 조합을 하나씩 합집합 하여 U가 되는 조합의 집합수가 최소인 것을 찾는 것이다. 하지만  F에 n개의 원소가 있으면 (2n-1)개를 다 검사, n이 커지면 최적해를 찾는 것은 실질적으로 불가능하다. 이를 극복하기 위한 방법으로 최적해를 찾는 대신 최적해에 급전한 근사해(approximation solution)을 찾는다.

---

알고리즘 

SetCover
입력: U, F={Si}, i=1,2,...,n
출력: 집합 커버 C
C = ∅
while (U ≠ ∅) do {
  U의 원소들을 가장 많이 포함하고 있는 집합 Si를 F에서 선택한다.
  U = U - Si
  Si를 F에서 제거하고, Si를 C에 추가한다.
}
return C

 

• Line 4 : C = ∅로 초기화한다.
• Line 5 : while-조건 (U ≠ ∅)을 만족한다.
• Line 6 : U의 원소들을 가장 많이 커버하는 집합인 S4를 F에서 선택한다.
• Line 7 : 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를 F에서 선택.
• Line 7 : 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}를 리턴

---

시간 복잡도

while-루프가 수행되는 횟수는 최대 n번이다. 루프 1번 수행할 때, 집합 U의 원소 1개씩만 커버된다면 최악의 경우 n번 수행되어야 하기 때문이다. 

루프가 수행되는 횟수 : O(n)

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

루프 1회의 시간 복잡도 : O(1)+O(n2)+O(n)+O(1) = O(n2)

SetCover 알고리즘의 시간 복잡도 : O(n)*O(n2) = O(n3)

 

---

도시 계획(Ctiy Planning)에서 공공기관 배치하기, 경비시스템, 컴퓨터 바이러스 찾기, 대기업의 구매 업체 선정, 기업의 경력 직원 고용, 비행기 조종사 스케줄링, 조립 라인 균형화, 정보 검색 등에 활용할 수 있는 알고리즘이다.