근사 알고리즘

근사해가 얼마나 최적해에 가까운지를 나타내는 것을 근사 비율이라고 한다. 근사해 값과 최적해 값의 비율로서, 1에 가까울수록 정확도가 높다. 이때, 근사 비율을 계산하려면 최적해를 알아야 하는 모순이 발생한다. 따라서, 최적해를 대신할 수 있는 간접적인 최적해를 찾고, 이를 이용해 근사 비율을 계산한다. 

1. TSP

TSP 를 위한 근사 알고리즘을 생각하려면, 다항식 시간을 가지는 유사한 알고리즘을 활용할 수 있다. TSP 와 비슷한 특성을 가지는 MST (최소 신장 트리) 가 있다. MST 는 모든 점을 사이클 없이 연결하는 트리 중에서 가중치 합이 최소인 트리이다.

 

[Step 1 : MST 찾기 ] 크루스컬 또는 프림 알고리즘을 사용한다.

 

[Step 2 : DFS 깊이 우선 탐색 진행] 

 

[Step 3 : 중복된 도시 제거 ] 도시 A에서 B 로 가는 거리는 중간에 C를 경유하여 가는 것보다는 짧다는 삼각 부등식 특성을 사용한다. 

 

[근사 비율] 

간접적인 최적해를 구해서 근사 비율을 계산해보자. 간선의 가중치의 합 M 을 간접적인 최적해로 사용하자. 다만, 실제 최적해는 M 보다 항상 크다. 모든 점을 돈 후에, 시작점으로 다시 돌아와야 하기 때문이다. (M+)

 

이제 근사해를 계산해보자. MST 를 만들 때, 모든 간선이 2번씩 사용되었으므로 경로의 총 길이는 2M 이다. 이후에 삼각 부등식을 사용하기 때문에 근사해는 2M 보다 크지 않다. (2M-)

 

두 값의 비율을 구해보면, 근사해의 값은 최적해의 2배를 넘지 않는다는 결론을 낼 수 있다. 

 

[시간 복잡도]

간선 수 m, 점의 수 n 일 때, TSP 의 시간 복잡도는 MST 생성 부분에 의해 결정된다.  

크루스컬 : O(mlogm) 

프림 : O(n²)

 

 

2. 정점 커버

그래프에서 각 간선의 양 끝점들 중에서 적어도 1개의 점을 포함하는 최소 크기의 집합 찾는 문제이다. 

정점 커버는 집합 커버 문제로 변환할 수 있다. 

(집합 커버: 주어진 집합 S에 대해서 S의 부분 집합들이 주어질 때, 이 부분집합들 중에서 합집합하여 S 와 같게 되는 최소의 부분 집합 찾는 문제)

[근사 비율]

Klnn

근사해를 찾기 위해 극대 매칭 방법을 사용할 수 있다. 간선의 양 끝 점들이 중복되지 않게 간선을 하나씩 추가하는 방법이다. 

정점 대신에 간선을 선택한다고 생각해보자. 빨간색으로 선택한 간선의 양 끝점이 간선에 의해 커버된다. 

근사해는 12개, 최적해는 7개이다. 

 

[시간 복잡도]

간선 수 m 일 때, O(m) 

3. 통채우기

[시간 복잡도] 

- 최초/최선/최악 : 새 물건을 넣을 때마다 기존의 통들을 살펴봐야 하기 때문에 O(n²)

- 다음 적합: 직전 통만 살펴보면 되기 때문에 O(n) 

 

[최초/최선/최악 적합의 근사 비율]

 

최적해에서 사용된 통의 수를 OPT 라고 하면 OPT >= 물건의 합 / 통의 크기 

근사해에서 사용된 통의 수 OPT'를 구해보자. 마지막 통을 제외하고는 통이 1/2 이하로 차 있을 수 없다. 

 

[다음 적합의 근사 비율]

이웃한 2개의 통의 합은 C 보다 클 것이다. 용량을 초과해서 새로운 통을 사용하는 것이기 때문이다. 

4. 작업 스케줄링 문제

[시간 복잡도] 

n개의 작업을 배정해야 하고, m개의 기계를 탐색해야 하기 때문에 O(nm)

 

[근사 비율]

가장 마지막으로 추가되는 작업 i 를 제외한 상태를 생각한다. 가장 빨리 끝난 시간을 T 라고 하면, 이는 평균시간인 T' 보다 작다. 가장 빨리 끝난 기계이니깐. 마지막 작업이 추가되었을 때, 최종적으로 끝나는 시간 OPT는 T+Ti 이다. 따라서 T<=T'

 

 

5. 클러스터링 문제

n 개의 점을 k 개의 그룹으로 나누고 각 그룹의 중심이 되는 k개의 점을 선택하는 문제이다. 이때, 가장 큰 반경을 가진 그룹의 직경이 최소가 되도록 k개의 점을 선택해야 한다. (원의 크기가 모두 비슷하도록)

 

 

Step 1 : 임의의 점 1개를 첫 번째 센터 C1 로 정한다. 

Step 2: C1 과 가장 멀리 떨어진 점을 두 번째 센터 C2 로 정한다. 

Step 3: 각 점 xi 에서 각각 C1 과 C2 까지의 거리를 계산하여 그 중에서 작은 값을 D[i] 로 정한다. D에서 가장 큰 값의 인덱스 가진 점이 C3 가 된다. 

Step 4: 같은 방식으로 C4 도 정한다. 

 

Step 5: 그룹으로 나누기: 센터가 아닌 각 점으로부터 4개의 센터까지의 거리를 각각 계산하고, 그 중에서 가장 짧은 거리의 센터를 찾는다. 

 

[시간 복잡도]

step3 와 4에서 각각의 센터를 매번 비교하지 않고, 직접 센터까지의 거리만 계산한다면 시간 복잡도는 O(kn) 이다. 

- 점에서 센터까지 거리 계산 : O(n)

- 센터 k 개 찾아야 하므로 k 번 반복

 

[근사 비율]

 

 

처음에 문제 정의할 때,가장 큰 반경을 가진 그룹의 직경이 최소가 되도록 k개의 점을 선택해야 한다고 했다.

먼저, 최적해가 만든 그룹 중에 가장 큰 직경을 OPT 라고 하자. OPT 의 하한을 찾아보자. k개의 센터를 모두 찾았지만 k+1 의 가상의 센터를 추가해본다. 어쨋든 k=4 인 문제니깐 5개의 센터 중 2개는 하나의 그룹에 속해야 한다. 그림에서는 C5이 가장 가까운 센터인 C3 과 같은 그룹에 속한다. 둘 사이의 거리가 d 라고 했을 때, OPT >= d 이다. 그룹에 속하니깐!

 

이번엔 근사해가 만든 그룹 중에 가장 큰 직경을 OPT' 라고 하자. 항상 가장 멀리 떨어진 점을 센터로 하기로 했으니, 어떤 점도 자신으로부터 가장 가까운 센터까지의 거리가 d 보다 크지 않다. 즉, 반경 d 이내에 그룹에 속하는 모든 점들이 포함된다. 따라서 OPT' <= 2d (지름)

 

즉 2OPT >= 2d >= OPT' 이므로 근사비율은 2.0 이다.