크리스토피데스 알고리즘

Christofides algorithm

크리스토피데스 알고리즘이나 크리스토피데스-Serdyukov 알고리즘은 이동 중인 세일즈맨 문제에 대한 대략적인 해결책을 찾기 위한 알고리즘으로, 거리가 미터 공간을 형성하는 경우(이들은 대칭적이고 삼각형 불평등에 따른다.[1]솔루션이 최적 용액 길이의 3/2인자 이내임을 보장하는 근사 알고리즘으로 니코스 크리스토피데스, 아나톨리 1세의 이름을 따서 명명되었다. 1976년 독자적으로 발견한 세르듀코프.[2][3][4]

이 알고리즘은 일반 메트릭스 공간의 여행 판매원 문제에 대해 관련 과학 커뮤니티가 철저히 동료 검토를 거친 최고의 다항식 시간 근사 알고리즘으로 여전히 서 있다.그러나 2020년 7월 칼린, 클라인, 가란 등이 참신한 근사 알고리즘을 도입한 프리프린트를 발표하면서 근사비가 1.5~10이라고−36 주장했다.그들의 방법은 Christofides의 알고리즘과 유사한 원리를 따르지만, 최소 스패닝 트리 대신 신중하게 선택한 무작위 분포에서 무작위로 선택한 트리를 사용한다.[5][6]

알고리즘.

G = (V,w)를 여행 판매원 문제의 한 예가 되게 하라.즉, G는 정점의 V에 대한 완전한 그래프로서, 함수 w는 G의 모든 에지에 음이 아닌 실제 무게를 할당한다.삼각형 불평등에 따르면, 3개의 꼭지점 u, v, x마다 w(uv) + w(vx) w w(ux)의 경우가 되어야 한다.

그 후 알고리즘은 다음과 같이 가성으로 설명할 수 있다.[1]

  1. G의 최소 스패닝 트리 T를 생성한다.
  2. O를 T에서 홀수 정도의 정점 집합으로 한다.손으로 흔드는 보조정리법으로 O는 짝수의 정점을 가지고 있다.
  3. O의 정점에 의해 유도된 서브그래프에서 최소중량 완벽 매칭 M을 찾는다.
  4. M과 T의 가장자리를 결합하여 각 꼭지점의 높이가 일정한 연결된 다중글자 H를 형성한다.
  5. H에 오일러 회로를 형성하십시오.
  6. 반복 정점(바로 가기)을 건너뛰어 이전 단계에서 발견된 회로를 해밀턴 회로로 만드십시오.

근사비

알고리즘에 의해 생성된 솔루션 비용은 최적값의 3/2 이내다.이를 증명하기 위해 C를 최적의 여행 세일즈맨 투어가 되게 한다.C에서 가장자리를 제거하면 스패닝 트리가 생성되는데, 스패닝 트리는 최소 스패닝 트리의 무게를 가져야 하며 w(T) ≤ w(C)를 의미한다.다음으로, O의 정점을 C 주위의 주기적 순서로 번호를 매기고, C 파티션은 두 개의 경로 집합으로, 즉 주기적 순서의 첫 번째 경로 정점이 홀수인 경로와 첫 번째 경로 정점이 짝수인 경로로 번호를 매긴다.각 경로 집합은 각 경로의 두 끝점과 일치하는 O의 완벽한 일치를 나타내며, 이 일치의 가중치는 최대 경로의 중량과 동일하다.이 두 세트의 경로가 C의 가장자리를 분할하기 때문에, 두 세트 중 한 세트는 C의 무게의 절반 이상을 가지며, 삼각형 불평등 덕분에 해당 일치는 또한 C의 무게의 절반에 해당하는 무게를 가진다.최소-중량완벽 일치는 더 큰 중량을 가질 수 없으므로 w(M) w w(C)/2이다.T와 M의 가중치를 추가하면 오일러 투어의 가중치가 최대 3w(C)/2가 된다.삼각형 불평등 덕분에 지름길은 무게를 늘리지 않기 때문에 출력 무게도 최대 3w(C)/2이다.[1]

하한

여행 중인 세일즈맨 문제에 대한 입력 자료가 존재하여 크리스토피데스 알고리즘이 임의로 근사 비율이 3/2에 가까운 솔루션을 찾도록 한다.그러한 입력 등급 중 하나는 중량이 1인 n 정점 경로에 의해 형성되며, 0에 가깝지만 양에 가까운 숫자에 대해 중량이 1 + path인 경로에서 두 단계 떨어진 정점들을 연결하는 가장자리 집합도 함께 형성된다.전체 그래프의 나머지 모든 가장자리에는 이 하위 그래프의 최단 경로에 의해 주어진 거리가 있다.그런 다음 최소 스패닝 트리는 길이 n - 1의 경로에 의해 주어질 것이며, 두 개의 홀수 정점만이 경로 끝점일 것이며, 완벽한 일치는 약 n/2의 중량을 가진 단일 에지로 구성된다.트리와 일치를 조합하면 바로 가기가 없고 무게는 약 3n/2이다.단, 최적 솔루션은 경로의 끝점에 입사하는 두 개의 중량-1 가장자리와 함께 중량 1 + ε의 가장자리를 사용하며, ε의 작은 값에 대해서는 총 중량(1 + ε)(n - 2) + 2를 n에 가깝게 한다.따라서 우리는 3/2의 근사 비율을 얻는다.[7]

예

Metrischer Graph mit 5 Knoten.svg 주어진: 가장자리 무게가 삼각형 부등식을 따르는 전체 그래프
Christofides MST.svg 최소 스패닝 트리 T 계산
V'.svg 홀수 도(T)의 정점 O 집합을 계산한다.
G V'.svg O의 정점만을 사용하여 G의 서브그래프를 형성한다.
Christofides Matching.svg 이 하위 그래프에서 최소 가중치 완전 일치 M 구성
TuM.svg 일치 및 스패닝 트리 T unite M을 결합하여 오일러 멀티그래프 형성
Eulertour.svg 오일러 둘러보기 계산
Eulertour bereinigt.svg 알고리즘의 출력을 제공하는 반복 정점 제거

참조

  1. ^ a b c Goodrich, Michael T.; Tamassia, Roberto (2015), "18.1.2 The Christofides Approximation Algorithm", Algorithm Design and Applications, Wiley, pp. 513–514.
  2. ^ Christofides, Nicos (1976), Worst-case analysis of a new heuristic for the travelling salesman problem (PDF), Report 388, Graduate School of Industrial Administration, CMU
  3. ^ van Bevern, René; Slugina, Viktoriia A. (2020), "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem", Historia Mathematica, 53: 118–127, arXiv:2004.02437, doi:10.1016/j.hm.2020.04.003, S2CID 214803097
  4. ^ Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (in Russian), 17: 76–79
  5. ^ Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2020-08-30). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS].
  6. ^ Klarreich, Erica (8 October 2020). "Computer Scientists Break Traveling Salesperson Record". Quanta Magazine. Retrieved 2020-10-10.
  7. ^ Bläser, Markus (2008), "Metric TSP", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, ISBN 9780387307701.

외부 링크