집합 덮개 문제(Set Cover Problem)

[출처 : 위키백과] 집합 덮개 문제(set cover problem)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다

 

N개의 원소를 가진 집합 U가 주어진다면 U의 부분집합(subsets)들은 S = {S1, S2…,Sm} 말하고 모든 부분 집합 Si는 관련된 비용(cost)을 갖는다. S의 부분집합들을 합집합하여 U의 모든 요소를 ​​커버할수있도록 해야 한다면 이때 선택되는 부분집합의 최소 비용 집합을 찾아야 한다. 

집합 덮개 문제(Set Cover Problem)를 좀더 쉽게 설명하기위해 심시티(simcity)게임을 예로 들겠다.

심시티는 가상 도시 내의 시민들의 행복도를 제고하고, 안정적인 예산을 유지하면서 도시를 개발시키는 과업을 수행한다.

그림1. 심시티 게임 화면

도시를 개발하기 위한 요소로 작은 주택부터 높은 빌딩도 있지만 사람이 거주하기 위해서는 기본적으로 인프라가 잘 갖춰있어야 한다.

예를들어 수도시설이라던지 소방시설, 공원, 학교등이다. 

주택이나 빌딩을 계속지으면 인구수가 늘어나고 인구수만큼 인프라도 계속 지어주어야만 한다. 

심시티 게임에서는 이런 인프라 건물들을 지을때 커버(cover)할수 있는 영역을 보여주는데 이게 이리저리 이동해보면서 가장 많이 커버할수 있는곳에 건물을 배치시켜야 한다.

  

그림2. 소방서 커버리지

그림2는 심시티에서 소방서를 지어야 하는 상황으로 빨간색은 근처에 소방서가 없어서 빨리 소방서를 지어 커버를 하라는 신호이다.

연두색은 이미 커버가 되어있는 지역이기도 하다.

이렇게 도시 중간중간에 소방서를 배치해서 빨간색이 없도록 도시를 건설해야 인구도 늘고 주민들이 행복해 하는데 우리가 고민해야할 문제는 어느곳에 소방서를 배치해야 소방서 지을 예산을 아낄수 있냐? 이다.

 

이 문제는 그리디알고리즘으로 해결할 수있는데 전체 도시에서 소방서가 있어야할 후보가 여러군데 있다면 그 후보들중  커버리지가 가장 높은 곳 부터 차례차례 지으면 되는것이다.

 

이걸 문제로 낸다면 U의 집합은 소방서가 커버할 건물들의 집합이고 , F는 소방서를 지을 후보 지점들이고 Si는  각 지점마다 어떤 건물들을 커버할수 있는지 부분집합을 나타낸다고 가정하자

 

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} 
S1 = {1, 2, 3, 8}
S2 = {1, 2, 3, 4, 8}
S3 = {1, 2, 3, 4}
S4 = {2, 3, 4, 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 가 된다.

 

그리디 알고리즘을 적용하여 부분집합 중 가장 많은 건물들을 커버 할 수 집합을 선택해 나가는 것이다.

여기서 가장 많은 건물을 커버할 수 있는  집합 1위는 S6이고 그 다음에는 S2 였던 것이다.

 

 

좀 응용을 해보자. 이번에는 소방서를 짖는데 비용(cost)가 든다고 하자

U = { 1, 2, 3, 4, 5 } 
S = { S1, S2, S3 } 
S1 = { 4, 1, 3}, Cost(S1) = 5 
S2 = { 2, 5}, Cost(S2) = 10 
S3 = { 1, 4, 3, 2}, Cost(S3) = 3

커버해야 할 건물 집합 U가 있고  각 건물을 커버할수 있는 소방서 집합 S 가 있다고 하면 S1은 4, 1, 3번 건물을 커버할수 있고 대신 소방서를 짓는데 드는 비용이 5이다. S2는 2, 5번 건물을 커버할수 있고 짓는 비용은 10, 그리고 S3는 1, 4, 3, 2 이고 비용은 3이다.
우리는 U의 모든 요소를 ​​커버할수 있는 S의 최소 비용 집합을 찾아야 한다.

비용을 무시했을 때 그리디 알고리즘을 적용하면 가장 많은 건물을 커버할수있는 소방서 부터 선택해야 하니 S3를 선택한다.
그리고 S1 을 선택한다. S3 ∪ S1 = { 1, 2, 3, 4 } 이고  아직 5를 커버하지 못했으므로 S2까지 모두 선택해야하는 상황이 발생된다.
그런데 모든 것을 커버할수 있는 경우는 S3 ∪ S2 ∪ S1 도 있지만  S2 ∪ S1 2개만 선택해도 되고  S2 ∪ S3 를 선택해도 된다.
따라서 cost 을 무시하고 그리디 알고리즘 적용시 최적의 해를 찾을수없다.

cost 을 고려한다면 건물을 S2 ∪ S1 은 cost = 15 가 들고  S2 ∪ S3 는 cost = 13이기 때문에 S2 ∪ S3 를 선택하는것이 답이 된다.
그럼 cost 를 고려하여 최소비용이 들면서 가장 적은 집합을 선택할 방법은 무엇일까 ?
답은 커버할수 있는 건물의 개수 대비 cost 가 얼마가 드는지 비율을 계산하여 비용이 적으면서 많은 건물을 커버할수 있는 것부터 선택하면된다.

비용이 있는 set cover problem algorithm

1. 지금까지 커버된 집합을 I라고 하고 처음에는 아무것도 없는 공집합으로 초기화 한다.
I = {}

2. 각 서브 집합에 대해 건물대비 비용이 얼마나 드는지 cost 비율을 계산한다. 
계산은 부분집합 Si의 cost 를 Si - I (차집합)  개수로 나누면 된다,

S1 = Cost(S1)/|S1 – I| = 5/3
S2 = Cost(S2)/|S2 – I| = 10/2
S3 = Cost(S3)/|S3 – I| = 3/4

3. 2번에서 구한 cost 비율중 가장 적은 S3를 I 에 추가한다. 
이제 I = { 1, 4, 3, 2 } 가 된다.

4. 아직 추가되지 않은 집합에 대해서 cost 비율을 다시 계산한다.
S1 = Cost(S1)/|S1 – I| = 5/0
S2 = Cost(S2)/|S2 – I| = 10/1

5. 4번에서 구한 cost 비율중 가장 작은 0이 아닌 가장 작은 것은 S2 이고 S2를 I에 추가하면
I = { 1, 2, 3, 4, 5 } 로  U와 같아졌다. 따라서 S2 ∪ S3  = U 가 된다.

코드 구현은 별로 어렵지 않으나 셋(Set) 자료구조를 선행학습해야 한다.  

 

그리디 알고리즘은 위의 예제에 대한 최적의 솔루션을 제공하지만 항상 최적의 솔루션을 제공하지 못할 수 있음을 명심해야 한다. 

다음 예제를 보자. 

U = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
S1 = {1, 2}

S2 = {2, 3, 4, 5}
S3 = {6, 7, 8, 9, 10, 11, 12, 13}
S4 = {1, 3, 5, 7, 9, 11, 13}
S5 = {2, 4, 6, 8, 10, 12, 13}

모든 cost 는 동일하다고 가정하고 그리디 알고리즘을 적용하면 {S3, S2, S1} 이 나오지ㅏㄴ 최적의 솔류션은 {S4, S5} 임을 알수 있다.

 

레퍼런스

• Set Cover Problem | Set 1 (Greedy Approximate Algorithm)