[Algorithm] 집합 커버 문제 (Set Covering Problem)

💡집합커버문제 (Set Covering Problem)

• n개의 원소를 가진 집합 U
• U의 부분집합들을 원소로하는 집합 F
• F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가?
• 여기서, F에서 선택하는 집합들의 수를 최소화하는 문제이다.

 

❓최적해를 어떻게 찾아야할까?

• 가장 단순한 방법 : F에 있는 집합들의 모든 조합을 1개씩 합집합하여 U가 되는지 확인하고, U가 되는 조합의 집합 수가 최소인 것을 찾는 것
  • Brute Force Algorithm : n개의 원소가 있으면 (2^n -1)개를 다 검사 필요
  • n이 커지면 최적해를 찾는 것은 실질적으로 불가능
  • 실제로 집합커버문제는 NP-hard 문제로 polynomial time optimal algorithm을 설계하기 매우 어렵다. (현실적인 시간 내에 해를 찾기 어렵)
• 이를 극복하기 위해, 최적해를 찾는 대신 최적해에 근접한 근사해(approximation solution)를 찾는 것.

 

💡의사코드

1. C = ∅
2. while(U!=∅)do{
3. 	U의 원소들을 가장 많이 포함하고 있는 집합 Si를 F에서 선택한다. // 그리디 알고리즘
4. 	U = U-(Si의 원소들)
5.  Si를 F에서 제거하고, Si를 C에 추가한다.
}
6. return C

-> 최종해가 optimal은 아니다.

 

 

💡시간복잡도

• while 루프의 수행횟수 : 최대 n번
  • 왜냐하면 루프가 1번 수행될 때마다 집합 U의 원소 1개씩만 커버될 때, 최악의 경우 루프가 n번 수행되어야하기 때문
• 루프가 1번 수행될 때의 시간복잡도
  • Line2 : O(1)
  • Line3 : U의 원소들을 가장 많이 포함하고 있는 집합 S를 찾으려면, 현재 남아있는 Si들 각각을 U와 비교해야한다. 따라서 Si의 수는 최대 n이고, 각 Si와 U의 비교는 O(n)시간이 걸리므로, line3은 O(n^2)의 시간이 걸린다.
  • Line4 : 집합 U에서 집합 Si의 원소들을 제거하는 것이므로 O(n)시간이 걸린다.
  • Line5 : Si를 F에서 제거하고, Si를 C에 추가 : O(1)의 시간
  • 루프 1회의 시간복잡도는 O(1) + O(n^2) + O(n) + O(1) = O(n^2)
• 총 시간 복잡도 O(n) x O(n^2) = O(n^3)

 

💡근사비율

• 근사 알고리즘은 근사해가 최적해에 얼마나 근사한지를 나타네는 근사비율을 알고리즘과 함께 제시해야한다.
• 집합 커버 알고리즘의 근사비율은 Klogn : 알고리즘이 최악 경우의 해일지라도 그 집합 수가 Klogn개를 넘지 않는다는 뜻. 
  • K = 최적해의 집합의 수
• 집합 문제의 최적해를 찾는데는 지수시간이 걸리나, SetCover 알고리즘은 O(n^3)시간에 근사해를 찾으며 그 해도 실질적으로 최적해와 비슷

---

➰응용

• 도시계획에서 공공기관 배치
• 경비 시스템
• 컴퓨터바이러스 찾기
• 대기업의 구매 업체 선정
• 기업의 경력 직원 고용
• 비행기 조종사 스케쥴링, 조립 라인 균형화, 정보검색 등

 

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업