알고리즘 - 25 근사 알고리즘

근사 알고리즘

1. 근사 알고리즘이란?

2. 근사 알고리즘과 근사 비율

 

 

 

NP-완비 문제

1. 다항식 시간에 해결할 수 있는 알고리즘이 아직 발견되지 않음

2. 아직까지 누구도 이 문제들을 다항식 시간에 해결할 수 없다는 것을 증명하지 못함

 

 

NP-완비 문제를 해결하기 위해 다음 세가지 중 한가지는 포기해야함

1. 다항식 시간에 해를 찾는 것

2. 모든 입력에 대해 해를 찾는것

 - 대부분 입력(즉, 최악의 경우가 아닌 입력)에 대해 최적해를 구하는 다항식 알고리즘 개발

3. 최적해를 찾는 것

 - 최적의 답은 아니더라도 최적에 가까운 준 최적해를 구하는 다항식 알고리즘 개발

 

 

 

근사 알고리즘

- 최적해를 찾는 것을 포기하여 최적해에 근사한 해를 찾음

 

 

 

P : 문제, I : 입력 크기가 n인 P의 한 사례

- V^* (I) : I에 대한 최적해의 값

- V(I) : 근사 알고리즘이 생성한 근사해의 값

 

 

근사 비율

- 근사 비율 r(I) : 근사해의 값과 최적해의 값의 비율

- 최대화 문제 : 0 < V(I) <= V^* (I)

- 최소화 문제 : 0 < V^* (I) <= V(I)

 

크기가 n인 모든 I에 대해 r(I) <= r(n)이면, 근사 알고리즘은 비율 한계가 r(n)임

- r(n) >= 1

- 근사 비율 r(n)이 1이면 최적 알고리즘, 큰 값일 수록 부정확한 해를 산출하는 경우

 

 

상대 오차

- 상대 오차의 한계 epsilon(n)

- 모든 I에 대해서 epsilon(I) <= epsilon(n)

- epsilon(n) = 0 -> 최적 알고리즘

 

 

근사 알고리즘의 예

1. 여행자 문제

2. 정점 커버 문제

3. 작업 스케줄링 문제

4. 클러스터링 문제

 

 

여행자 문제

- 여행자가 임의의 한 도시에서 출발하여 다른 모든 도시를 한 번씩만 방문하고 다시 출발했던 도시로 돌아오는 여행 경로의 거리를 최소화 하는 문제

 

TSP를 위한 근사 알고리즘 고안

- 다항식 시간 알고리즘을 가지며, 유사한 특성을 가진 문제를 찾아 활용

 -> 최소 싱장 트리 문제 : 모든 점을 사이클 없이 연결하는 트리 중에 트리 선분의 가중치의 합이 최소인 트리

 -> 최소 신장 트리의 모든 점을 연결하는 특성과 최소 가중치의 특성을 응용하여, 시작 도시를 제외한 다른 모든 도시를 트리 선분을 따라 한번 씩 방문하도록 경로를 찾음

 

 

여행자 문제의 근사 알고리즘의 예

1. (a) 그래프 G에서 크루스칼 알고리즘이나 프림 알고리즘으로 최소 신장트리 (b)를 구함

 

2. 도시 1에서 출발하여 트리 선분을따라서 모든 도시를 방문하고 돌아오는 도시의 방문 순서를 (c)와 같이 구함. 방문 순서는 [1 2 4 3 4 5 4 6 7 6 4 2 1]임

 

3. 순서를 따라서 도시를 방문하되 중복 방문하는 도시를 순서에서 제거하여 여행자 문제의 근사해를 구함. 단 도시 순서의 가장 마지막에 있는 출발 도시 1은 중복되어 나타나지만 제거하지 않음

 

 

 

 

유사 코드

- 입력 : n개의 도시, 각 도시간의 거리

- 출력 : 출발 도시에서 각 도시를 한 번씩만 방문하고 출발 도시로 돌아오는 도시 순서

1. 입력에 대해 MST를 찾음

2. MST에서 임의의 도시로부터 출발하여 트리의 선분을 따라 모든 도시를 방문하고 다시 출발했던 도시로 돌아오는 도시 방문 순서를 찾음

3. return 이전 단계에서 찾은 도시 순서에서 중복되어 나타나는 도시를 제거한 도시 순서(단, 도시 순서의 가장 마지막의 출발 도시는 제거하지 않음)

-> 시간 복잡도는(크루스칼이나 프림 알고리즘의 시간 복잡도) + O(n) + O(n)이므로 크루스칼이나 프림 알고리즘의 시간 복잡도와 같음

 

 

 

근사 비율

- 여행자 문제의 최적해를 알 수 없ㅇ므로, '간접적인' 최적해인 최소 신장 트리 선분의 가중치 합 M을 최적해의 값으로 활용

- 실제 최적해의 값이 M보다 항상 크기 때문

- Approx_MST_TSP 알고리즘이 계산한 근사해의 값은 2보다 크지 않음

 -> MST의 선분을 따라서 도시 방문 순서를 찾을 때 사용된 트리 선분을 살펴보면, 각 선분이 두 번 사용됨

 -> 따라서 이 도시 방문 순서에 따른 경로의 총 길이는 2M임

 -> 삼각 부등식의 원리를 이용하여 새로운 도시 방문 순서를 만들기 때문에, 이전 도시 방문순서에 따 경로 길이보다 새로운 도시 방문 순서에 따른 경로의 길이가 더 짧음

 

 

 

 

정점 커버 문제 vertex cover problem

- 주어진 그래프 G = (V, E)에서 각 선분의 양 끝점들 중에서 적어도 하나의 끝 점을 포함하는 점들의 집합 중에서 최소 크기의 집합을 찾는 문제

- 정점 커버를 살펴보면, 그래프의 모든 선분이 정점 커버에 속한 점에 인접해 있음. 즉, 정점 커버에 속한 점으로서 그래프의 모든 선분을 커버하는 것

 

정점 커버 문제의 예 1

- 그래프 G에서 {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}이 각각 정점 커버

- {2}또는 {3}은 정점 커버가 아님. {2}는 선분 (1, 3)을 거버하지 못하고, {3}은 선분 (1, 2)를 커버하지 못함

- 그래프에 대한 정점 커버 문제의 해는 {1}이 됨

 

 

정점 커버 문제의 예 2

1. 아래의 그래프 G는 어느 건물의 내부 도면을 나타냄

- 건물의 모든 복도를 감시하기 위해 가장 적은수의 CCTV 카메라를 설치하고자 함

- 이를 위해서 3대의 카메라를 각각 점 1, 5, 6에 설치하면 모든 복도(선분)를 '커버'할 수 있음

 

 

 

정점 커버 문제의 두가지 접근 방법

1. 먼저 차수가 가장 높은 점을 우선 선택하면 많은 수의 선분이 커버 됨

2. 점을 선택하는 대신에 선분을 선택하는 것

- 선분을 선택하면 선택된 선분의 양 끝점에 인접한 선분이 모두 커버됨

- 따라서 정컴 커버는 선택된 각 선분의 양 끝점들의 집합임

- 정점 커버를 만들어 가는 과정에서, 새 선분은 자신의 양 끝점들이 이미 선택된 선분의 양 끝점들의 집합에 포함되지 않을 때에만 선택됨

 

 

 

 

 

작업 스캐줄링 문제

- n개의 작업, 각 작업 수행시간 t_i, i = 1, 2, 3, ..., n 그리고 m개의 동일한 기계가 주어질 때, 모든 작업이 가장 빨리 종료되도록 작업글 기계에 배정하는 문제

 

작업 스케줄링 문제의 조건

- 한 작업은 배정된 기계에서 연속적으로 수행되어야 함

- 기계는 한 번에 하나의 작업만을 수행함

 

가장 간단한 해법은 그리디 방법으로 작업 배정

- 현재까지 배정된 작업에 대해 가장 빨리 끝나는 기계에 새 작업을 배정하는 것

 

 

작업 스케줄링 문제를 그리디 알고리즘을 이용하여 근사해를 구하는 유사 코드

Approx_JobScheduling
입력 : n개의 작업, 각 작업 수행 시간 t_i, i = 1, 2, ..., n 기계 M_j, j = 1, 2, ..., m
출력 : 모든 작업이 종료된 시간
for j = 1 to m
   L[j] = 0             L[j] = 기계 M_j에 배정된 마지막 작업의 종료 시간
for i = 1 to n {
   min = 1
   for j = 2 to m {                      가장 일찍 끝나는 기계를 찾음
       if (L[j] < L[min])
           min = j
   }
   작업 i를 기계 M_min에 배정함
   L[min] = L[min] + t_i
}

return 가장 늦은 작업 종료 시간

 

 

 

작업 스케줄링 문제 해법의 작동 예

- 작업 수행 시간 : 5, 2, 4, 3, 4, 7, 9, 2, 4, 1

- 기계 : 4개

 

 

 

시간 복잡도

1. approx_jobscheduling 알고리즘은 n개의 작업을 하나씩 가장 빨리 끝나는 기계에 배정함

- 이러한 기계를 찾기 위해 알고리즘의 for루프가 m-1번 수행됨

- 모든 기계의 마지막 작업 종료 시간인 L[j]를 살펴봐야하므로 O(m) 시간이 소요됨

2. 시간 복잡도 n개의 작업을 배정해야하고, 배열 L을 탐색해야 하므로 n x O(m) + O(m) = O(nm)임

 

 

근사 비율

1. approx_jobscheduling 알고리즘의 근사해를 opt'라 하고, 최적해를 Opt라고 할 때 ,opt' <= 2 x opt임

2. 근사해는 최적해의 두 배를 넘지 않음. t_i는 작업 i의 수행 시간임.

3. 가장 마지막으로 배정된 작업 i가 T부터 수행되며, 모든 작업이 T + T_i에 종료된 것을 보이고 있음. 그러므로 OTP' = T + t_i임.

4. T'는 작업 i를 제외한 모든 작업의 수행 시간의 합을 기계의 수 m으로 나눈 값임. T'는 작업 i를 제외한 i를 평균 종료 시간임

5. T <= T'이 됨

 - 작업 i가 배정된(가장 늦게 끝나는) 기계를 제외한 모든 기계에 배정된 작업은 적어도 T 이후에 종료되기 때문임.

 

 

클러스터링 문제

- n개의 점이 2차원 평면에 주어질 때, 이 점들 간의 거리를 고려하여 k개의 그룹으로 나누고자 하는 문제

 

클러스터링 문제 조건

- 입력으로 주어진 n개의 점을 k개의 그룹으로 나누고 각 그룹의 중심이 되는 k개의 점을 선택하는 문제임

- 단, 가장 큰 반경을 가진 그룹의 직경이 최소가 되도록 k개의 점이 선택되어야 함

 

 

 

 

 

클러스터링 문제 해결 전략

1. n개의 점 중에서 k개의 센터를 선택해야 하는데, 이를 한 꺼번에 선택하는 것 보다 한 개씩 선택하는 것이 쉬움

2. 오른쪽 그립 같이 첫 번째 센터가 랜덤하게 정해졌다고 가정함

3. 두 번째 센터는 두 개의 센터가 서로 가까이 있는 것보다 멀리 떨어져 있는 것이 좋음

4. 다음 세 번째 센터는 첫 번째와 두 번째 센터에서 가장 멀리 떨어진 점을 선택