크리스토피데스 알고리즘
크리스토피데스 알고리즘(Christofides algorithm)은 거리 공간 외판원 문제에서 근사해를 구하는 알고리즘이다. 위 근사 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장하며, Nicos Christofides에 의해 1976년 개발되었다.
2017년까지도 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다.
알고리즘
[편집]외판원 문제 G=(V,w)를 정의해보자. G는 V의 점들과 점들 사이 변으로 이루어진 완전 그래프이고, w는 G의 모든 변들에 0 이상의 가중치를 부여한다. 이 때 G의 모든 점들 u, v, x에 대해 다음의 삼각 부등식이 성립한다. w(uv) + w(vx) >= w(ux)
크리스토피데스 알고리즘은 다음과 같은 수도 코드로 표현할 수 있다.[1]
- G의 최소 비용 신장 트리 T를 구한다.
- T의 홀수 차수 점들의 집합을 O라고 정의하면, O는 악수 보조 정리에 의해 짝수개의 원소를 가지게 된다.
- O에 의해 형성된 유도 부분 그래프에서 최소 비용의 완벽 부합 M을 찾는다.
- M과 T의 변들을 합쳐 모든 점들이 짝수 차수를 갖는 다중 그래프 H를 형성한다.
- H에서 오일러 회로를 구성한다.
- 5단계에서 찾은 회로에서 반복되는 점들을 제거하여 해밀턴 회로로 변경한다.
근사 비율
[편집]위 알고리즘으로 근사 비율은 3/2이다. 이를 증명하기 위해 C를 외판원 문제의 최적해라고 하자.
C에서 임의의 변을 제거하면 신장 트리를 얻을 수 있는데, 이 신장 트리의 비용은 C의 비용보다 작다. (w(T) < w(C))
C의 주위에 순환 순서로 O의 꼭짓점에 숫자를 매기고 C를 다음 두 개의 경로 집합으로 나눈다 : 첫 번째 경로 꼭짓점이 홀수인 경로 집합과 첫 번째 경로 꼭짓점이 짝수인 경로 집합.
각 경로 집합은 O의 완벽 부합에 상응하는데, 각 경로와 경로의 두 끝점을 일치시켜 완벽 부합을 얻을 수 있다. 이 부합의 가중치는 경로의 가중치와 같아야한다.
이 두 경로 집합이 C의 변 집합을 분할하기 때문에 두 집합 중 하나는 최대 C의 가중치의 절반을 가지며 해당 완벽 부합 또한 최대 C의 가중치의 절반에 해당하는 가중치를 가진다. w(M) ≤ w(C)/ 2.
T와 M의 가중치를 더해 오일러 경로를 구하면 최대 3w(C)/2의 가중치 변 집합을 얻을 수 있다. Shortcutting은 가중치를 증가시키지 않으므로 출력의 가중치도 최대 3w(C)/2이다.[2]
예시
[편집] | 삼각 부등식을 만족하는 가중치가 부여된 완전 그래프 |
 | 최소 비용 신장 트리 T를 계산한다. |
 | T의 홀수 차수 꼭짓점들을 모아 O로 정의한다. |
 | O의 꼭짓점들로 G의 부분 그래프를 구한다. |
 | 부분 그래프의 최소 비용 완벽 부합 M을 찾는다. |
 | 신장 트리 T와 완벽 부합 M을 합쳐 오일러 다중 그래프를 형성한다. |
 | 오일러 경로를 계산한다. |
 | 반복되는 꼭짓점들을 지워 알고리즘의 결과물을 얻는다. |
각주
[편집]- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), 〈18.1.2 The Christofides Approximation Algorithm〉, 《Algorithm Design and Applications》, Wiley, 513–514쪽.
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), 〈18.1.2 The Christofides Approximation Algorithm〉, 《Algorithm Design and Applications》, Wiley, 513–514쪽.