그리디 알고리즘 - 집합 커버 문제
집합 커버 문제
집합 커버 문제는 집합 F에서 선택하는 집합들의 수를 최소화하는 문제이다.
예시로 신도시 학교 배치 문제가 있다
사진을 문제로 변환 시키면
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와 같은 집합은
이다.
집합 커버 문제의 최적해를 찾는 방법 중 가장 간단한 것은 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)에서 공공기관 배치하기, 경비시스템, 컴퓨터 바이러스 찾기, 대기업의 구매 업체 선정, 기업의 경력 직원 고용, 비행기 조종사 스케줄링, 조립 라인 균형화, 정보 검색 등에 활용할 수 있는 알고리즘이다.