[HUFS/알고리즘] #8 근사 알고리즘

근사 알고리즘 (Approximation Algorithms)

NP-완전 문제들은 활용성이 높지만 다항식 시간에 해결할 수 있는 알고리즘이 아직 발견되지 않았고, 존재하지 않을 것으로 추측된다. 일단 해결하기 위해 다음 3가지 중 1가지는 포기해야 한다

 

1. 다항식 시간에 해를 찾는 것
2. 모든 입력에 대해 해를 찾는 것
3. 최적해를 찾는 것

NP-완전 문제를 해결하기 위해 3번째 요소(최적해)를 포기, 최적해에 아주 근사한 해를 찾아주는 것이 근사 알고리즘이다

• 최적해가 아닌 근사해를 찾는 대신 다항식 시간의 복잡도를 가진다
• 근사해가 얼마나 최적해에 근사한지 나타내는 근사 비율(Approximation Ratio)을 알고리즘과 함께 제시해야 한다
• 근사 비율이 1.0에 가까울수록 정확도가 높은 알고리즘이다
• 근사 비율을 계산하려면 최적해를 알아야 하는 모순이 생긴다
• 최적해를 대신할 수 있는 간접적인 최적해를 찾고 이를 최적해로 삼아 근사 비율을 계산한다

 

1. 여행자 문제 (Traveling Salesman Problem, TSP)

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

• 도시 A에서 B로 가는 거리는 도시 B에서 A로 가는 거리와 같다 (대칭성)
• 도시 A에서 도시 B로 가는 거리는 도시 A에서 다른 도시 C를 경유해 도시 B로 가는 거리보다 짧다 (삼각 부등식 원리)

 

유사한 특성의 다항식 시간 알고리즘을 가지는 문제는 최소 신장 트리 (Minimum Spanning Tree, MST) 문제이다

• MST = 모든 점을 사이클 없이 연결하는 트리 중 선분의 가중치 합이 최소인 트리
• MST의 모든 점을 연결하는 특성과 최소 가중치의 특성을 TSP에 응용해 시작 도시를 제외한 다른 모든 도시를 트리 선분을 따라 1번씩 방문하도록 경로를 찾는 것

 

삼각 부등식 원리로 MST를 활용해 근사해를 찾는 과정

 

1. 먼저 그래프 G에 크러스컬 또는 프림 알고리즘으로 최소 신장 트리 MST를 찾는다
2. 임의의 도시에서 출발해 모든 도시를 방문하고 돌아오는 도시의 방문 순서를 구한다
3. 해당 순서를 따라 도시를 방문하되 중복 방문하는 도시를 순서에서 제거한다 (출발 도시 제외)

중복 방문 도시를 제거하는 과정에서 삼각 부등식 원리를 사용

여행자 문제 근사 알고리즘

여행자 문제 근사 알고리즘 해설

MST를 찾는 시간 복잡도 + O(n) + O(n)

~ 크러스컬(O(nlogn)) or 프림 알고리즘(O(n^2))과 동일한 다항식 시간 복잡도

 

간접적인 최적해인 MST 선분의 가중치의 합(M)을 최적해로 활용하면, 여행자 문제 근사 알고리즘이 계산한 근사해의 값은 중복 방문을 허용한 Line 2의 2M보다는 크지 않다

~ 근사 비율은 2M/M = 2보다 크지 않다 = 근사해의 값이 최적해 값의 2배를 넘지 않는다

 

2. 정점 커버 문제 (Vertex Cover)

그래프 G=(V,E)에서 각 선분의 양 끝점들 중에서 적어도 하나의 끝점을 포함하는 점들의 집합들 중에서 최소 크기의 집합을 찾는 문제로, 결과적으로 그래프의 모든 선분을 커버한다

 

정점 커버 예시

모든 선분을 커버하는 경우 예시

• 선택된 선분의 양 끝점에 인접한 선분이 모두 커버된다
• 정점 커버 = 선택된 각 선분의 양 끝점들의 집합
• 새 선분은 자신의 양 끝점들이 이미 선택된 선분의 양 끝점 집합에 포함되지 않을 때만 선택

 

이 경우, 선택된 선분의 주변 6개의 선분은 새로운 선분으로 선택되지 않는다

이 방식을 반복해 선분을 선택하다가 더 이상 선분을 추가할 수 없을 때 중단, 이 때 선택된 선분의 집합을 극대 매칭(maximal matching)이라고 한다 (매칭은 각 선분의 양쪽 끝점들이 중복되지 않는 선분의 집합, 여기서 새로운 선분을 더 추가할 수 없는 상태가 극대 매칭이다)

 

정점 커버 문제 근사 알고리즘

이처럼 근사해를 구해도 최적해와 괴리가 있을 수 있다

정점 커버 근사 알고리즘 시간 복잡도 = 극대 매칭을 찾는 시간 복잡도

하나의 선분을 선택해 기존 선분의 양 끝점이 동일한지 검사 O(n) * 선분 수 m

~ O(n) * m = O(nm)의 시간 복잡도

 

극대 매칭을 간접적인 최적해로 사용, 매칭에 있는 선분의 수가 최적해의 값이 되며 각 선분의 양쪽 끝점들의 집합을 정점 커버의 근사해로서 반환하므로 근사해 = 극대 매칭의 선분의 수 * 2

~ 근사 비율 = (극대 매칭의 각 선분의 양 끝점들의 수) / (극대 매칭의 선분의 수) = 2

 

3. 통 채우기 문제 (Bin Packing)

n개의 물건이 주어지고, 통(bin)의 용량이 C일 때, 모든 물건을 가장 적은 수의 통에 채우는 문제

 

그리디 알고리즘에 속하며, 다음 4가지로 분류할 수 있다

• 최초 적합(First Fit): 첫 번째 통부터 차례로 살펴보며, 가장 먼저 여유가 있는 통에 넣는다
• 다음 적합(Next Fit): 직전에 물건을 넣은 통에 여유가 있으면 새 물건을 넣는다
• 최선 적합(Best Fit): 여유가 있는 통 중에 남는 부분이 가장 작은 통에 새 물건을 넣는다
• 최악 적합(Worst Fit): 여유가 있는 통 중에 남는 부분이 가장 큰 통에 새 물건을 넣는다

* 각 방법으로 새 물건을 기존의 통에 넣지 못하면, 새로운 통을 추가해 새 물건을 넣는다

 

C=10, 물건은 [7, 5, 6, 4, 2, 3, 7, 5]일 때, 각 방법을 적용한 결과

최적해에 가까운 근사해를 구해보자

통 채우기 문제 근사 알고리즘

시간복잡도는 사용된 그리디 알고리즘 방법에 따라 다르다

• 다음 적합을 제외한 3가지 방법: 새 물건을 넣을 때마다 기존의 통을 살펴보는데, 통의 수가 n을 넘지 않으므로 O(n^2)
• 다음 적합: 새 물건에 대해 직전에 사용된 통만 살펴보면 되므로 O(n)

 

근사비율은 구하는 방식만 사용된 그리디 알고리즘 방법에 따라 다르다

1. 다음 적합을 제외한 3가지 방법의 경우, 전체 통의 수는 최적해에서 사용된 통의 수의 2배를 넘지 않는다 (2개 이상의 통이 1/2 이하로 차 있을 수 없기 때문)

 

전체 통을 검사하기 때문에 1/2 이하의 통이 2개라면 합쳐진다

따라서 각 방법이 사용한 통의 수가 OPT'라면, (OPT'-1)개의 통에 각각 1/2 넘게 물건을 채울 때, 물건의 크기의 합은 ((OPT' - 1) * C/2) 보다는 크다

 

결과적으로 근사 비율은 2가 된다

2. 다음 적합의 경우, 직전 통에 들은 물건의 크기와 새 물건의 크기의 합이 통의 크기보다 클 때만 새 통에 새 물건을 넣는다

 

다음 적합이 사용한 통의 수가 OPT'일 때, 이웃한 2개의 통의 물건의 합은 항상 통보다 크다

마찬가지로 근사 비율이 2가 된다

 

4. 작업 스케줄링 문제 (Job Scheduling)

n개의 작업과 각 작업의 수행 시간들, 그리고 m개의 동일한 기계가 주어질 때, 모든 작업이 가장 빨리 종료되도록 작업을 기계에 배정하는 문제

 

그리디 알고리즘이며, 현재 가장 빨리 끝나는 기계에 새 작업을 배정한다

작업 스케줄링 문제 근사 알고리즘

4 대의 기계 + 작업 시간이 [5, 2, 4, 3, 4, 7, 9, 2, 4, 1]인 경우, 가장 늦은 종료 시간(=13)을 반환

가장 빨리 끝나는 기계를 찾는 for 루프 (m-1)만큼 / n개의 작업 배정 / 가장 늦은 종료 시간 찾기 O(m)

~ n * O(m) + O(m) = O(nm)의 시간 복잡도

 

최적해가 OPT, 근사해가 OPT'일 때, 근사해는 최적해의 두배를 넘지 않는다

 

OPT'는 T 시점부터 수행된 가장 마지막 작업이 종료된 시간이다

마지막 작업을 제외한 평균 종료 시간인 T’은 항상 T보다 크거나 같다

이를 통해 근사해가 최적해의 2배보다 크지 않음 (= 근사 비율은 2보다 크지 않음)을 증명

 

5. 클러스터링 문제 (Clustering)

n개의 점이 2차원 평면에 주어질 때, k개의 그룹으로 나누고 각 그룹의 중심이 되는 k개의 점을 선택하는 문제

 

그룹의 직경이 최소가 되도록 k개의 점 선택

클러스터링 문제 근사 알고리즘

4개의 그룹으로, 4개의 센터를 선택하는 상황

임의로 하나의 센터를 정하고 가장 먼 점을 2번째 센터로 선택

각 센터에서 가장 먼 점을 계산해 3번째 센터로 선택

같은 방식으로 4번째 센터를 정하고 센터에 가장 가까운 순으로 그룹에 점을 추가

임의의 점 선택 O(1) / 각 점에서 각 센터까지의 거리 계산 O(kn) / 그 중 최대값 찾기 O(n) / for 루프 (k-1)회 반복 / 센터가 아닌 각 점으로부터 k개의 센터까지 거리 각각 계산하며 최솟값 찾기 O(kn)

~ O(1) + (k-1) * (O(kn) + O(n)) + O(kn) = O(k^2*n)의 시간 복잡도

 

최적해의 가장 큰 그룹의 직경인 OPT의 하한은 근사해에 임의로 (k+1)번째 센터를 찾았을 때 가장 가까운 센터까지의 거리 d보다 작을 수 없다

 

OPT >= d

따라서 근사해의 가장 큰 그룹의 직경 OPT'는 2d보다 크지 않다

 

OPT' <= 2d

2OPT >= 2d >= OPT'이므로 근사 비율은 2를 넘지 않는다

 

클러스터링 알고리즘은 유사도를 부분 데이터로 분할해 분석하는 경우에 활용된다

 

클러스터링 알고리즘 응용