크리스토피데스 알고리즘

크리스토피데스 알고리즘(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를 구한다.
2. T의 홀수 차수 점들의 집합을 O라고 정의하면, O는 악수 보조 정리에 의해 짝수개의 원소를 가지게 된다.
3. O에 의해 형성된 유도 부분 그래프에서 최소 비용의 완벽 부합 M을 찾는다.
4. M과 T의 변들을 합쳐 모든 점들이 짝수 차수를 갖는 다중 그래프 H를 형성한다.
5. H에서 오일러 회로를 구성한다.
6. 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이다.

예시

	삼각 부등식을 만족하는 가중치가 부여된 완전 그래프
	최소 비용 신장 트리 T를 계산한다.
	T의 홀수 차수 꼭짓점들을 모아 O로 정의한다.
	O의 꼭짓점들로 G의 부분 그래프를 구한다.
	부분 그래프의 최소 비용 완벽 부합 M을 찾는다.
	신장 트리 T와 완벽 부합 M을 합쳐 오일러 다중 그래프를 형성한다.
	오일러 경로를 계산한다.
	반복되는 꼭짓점들을 지워 알고리즘의 결과물을 얻는다.