집합 커버 문제 (Set Cover Problem)

집합 커버 문제 (Set Cover Problem)

• 전체 집합 U와, 그 부분 집합 S_i들을 원소로 갖는 집합 F가 있다고 하자.

• F의 원소인 S_i들을 합집합하여 전체 집합 U와 같아지는 집합 S_i들의 최소 개수를 찾는 문제이다.

• F에 있는 집합들의 모든 조합을 하나씩 찾을 경우

  • 만약 F의 원소의 개수가 n개이면 나올 수 있는 경우의 수는 (2ⁿ - 1)개이고, n이 증가함에 따라 이 방식으로 최적해를 찾는 것은 실질적으로 불가능하다.

• 따라서 최적해 대신 최적해에 근접한 근사해(Approximation Solution)을 찾아야 한다.

  • U에 있는 원소를 가장 많이 커버하는 S_i를 반복적으로 찾아서 포함시키는 방식을 사용한다.

---

알고리즘

• 입력에 전체 집합 U와 그 부분 집합 S_i들을 포함한 집합 F가 주어진다.

  Pseudo Code

  SetCover(Set u, Set f)
  {
    Set cover;
    while (u.size() != 0)
    {
      u의 원소들을 가장 많이 포함하는 집합 s_i를 f에서 선택한다.
      u에서 s_i를 뺀다. (차집합)
      s_i를 cover에 추가한다.
      s_i를 f에서 제거한다.
    }
    return cover;
  }

  ---

예제

신도시를 계획하는데 10개의 마을에 학교를 배치해야 한다.

• 각 점은 마을을 의미하고, 선분은 15분 이내의 거리를 뜻한다.

• 학교는 마을에 위치해야 하고, 등교 거리는 15분 이내여야 한다.

  

• 집합 커버 문제로 변환시키면 다음과 같다.

  U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

  F = {S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈, S₉, S₁₀}

  S₁ = {1, 2, 3, 8}

  S₂ = {1, 2, 3, 4, 8}

  S₃ = {1, 2, 3, 4}

  S₄ = {2, 3, 4, 5, 7, 8}

  S₅ = {4, 5, 6, 7}

  S₆ = {5, 6, 7, 9, 10}

  S₇ = {4, 5, 6, 7}

  S₈ = {1, 2, 4, 8}

  S₉ = {6, 9}

  S₁₀ = {6, 10}

• 위의 알고리즘을 적용하는 순서는 다음과 같다.

  • 첫 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₄를 F에서 선택한다.

    • U에서 S₄를 빼면 U = {1, 6, 9, 10}이 된다.

    • S₄를 cover에 추가하고 F에서 제거한다.

  • 두 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₆를 F에서 선택한다.

    • U에서 S₆를 빼면 U = {1}이 된다.

    • S₆를 cover에 추가하고 F에서 제거한다.

  • 세 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₁를 F에서 선택한다.

    • U에서 S₁를 빼면 U는 공집합이 된다.

    • S₁를 cover에 추가하고 F에서 제거한다.

  • S₁, S₄, S₆이 담긴 cover를 리턴한다.

---

시간 복잡도

• 루프를 반복하는 횟수는 최대 n번이다.

• 전체 집합 U의 원소를 가장 많이 포함하는 집합 S_i를 찾을 때 걸리는 시간 복잡도는 O(n²)이다.

• 집합 U에서 집합 S_i를 뺄 때 O(n)이 걸린다.

• S_i를 cover에 추가하고 F에서 뺄 때 O(1)이 걸린다.

• 따라서 전체 시간 복잡도는 O(n³)이다.

  • 이는 지수 시간(2ⁿ)에 비해 굉장히 짧은 시간이다.

---

근사 비율 (Approximation Ratio)

• 근사 알고리즘에서 근사해가 최적해에 얼마나 가까운지를 나타내는 척도이다.

• SetCover 알고리즘의 근사 비율은 Klogn이라고 한다.

  • K는 최적해의 집합의 수이다.

  • 위의 예제에서는 최적해의 개수 K = 2이므로 Klogn = 2log10 < 8이다.

  • 즉 SetCover 알고리즘의 근사해의 집합 수가 8개를 초과하지 않는다는 것이다.