맨위로가기

크리스토피데스 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

크리스토피데스 알고리즘은 외판원 문제의 근사 해를 구하는 알고리즘으로, 삼각 부등식을 만족하는 완전 그래프에서 최소 비용의 해밀턴 회로를 찾는다. 이 알고리즘은 최소 신장 트리를 구성하고, 홀수 차수 정점을 찾아 최소 가중치 완전 매칭을 수행하며, 오일러 회로를 생성한 후 해밀턴 회로로 변환하는 단계를 거친다. 근사 비율은 3/2이며, 계산 복잡도는 O(n³)이다. 하지만 더 나은 근사 비율을 가진 알고리즘이 개발되었으며, 유클리드 공간에서의 TSP 문제에 대한 PTAS(다항 시간 근사 기법)가 존재한다. 크리스토피데스 알고리즘은 스태커 크레인 문제와 같은 TSP의 일반화 문제에도 활용될 수 있다.

더 읽어볼만한 페이지

  • 근사 알고리즘 - 최근접 이웃 탐색
    최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다.
  • 근사 알고리즘 - L-환산
    L-환산은 최적화 문제 간의 관계를 정의하는 개념으로, 한 문제의 입력과 해를 다른 문제의 입력과 해로 변환하는 함수와 특정 조건을 만족하며, 이를 통해 한 문제의 근사 알고리즘을 다른 문제에 적용할 수 있게 한다.
  • 그래프 알고리즘 - 페이지랭크
    페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다.
  • 그래프 알고리즘 - 너비 우선 탐색
    너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
크리스토피데스 알고리즘
알고리즘 개요
종류근사 알고리즘
문제travelling salesman problem (TSP)
시간 복잡도O(n^3)
근사 비율3/2
역사
명칭 유래니코스 크리스토피데스가 1976년에 발표
발견자니코스 크리스토피데스
발표 년도1976년
다른 이름크리스토피데스-세르듀코프 알고리즘
관련 인물아나톨리 이바노비치 세르듀코프
설명
개요크리스토피데스 알고리즘은 travelling salesman problem (TSP)에 대한 근사 알고리즘이다.
메트릭 TSP의 경우 최적 해의 3/2 이내의 해를 보장한다.
이 알고리즘은 니코스 크리스토피데스가 1976년에 발표했다.
단계1. 최소 스패닝 트리를 찾는다.
2. 최소 스패닝 트리에서 홀수 차수 정점을 모두 찾는다.
3. 홀수 차수 정점들의 완전 그래프에서 최소 가중치 완전 매칭을 찾는다.
4. 최소 스패닝 트리와 최소 가중치 완전 매칭을 결합하여 다중 그래프를 형성한다.
5. 다중 그래프에서 오일러 회로를 찾는다.
6. 오일러 회로를 순회하면서 이미 방문한 정점을 건너뛰어 TSP 순회를 만든다.
분석'삼각 부등식'을 만족하는 경우, 크리스토피데스 알고리즘은 비용이 최적 TSP 순회 비용의 최대 1.5배인 순회를 생성한다.
알고리즘은 최소 스패닝 트리를 계산하고, 최소 가중치 완전 매칭을 계산하며, 오일러 회로를 계산하는 데 다항 시간이 걸리므로 다항 시간 내에 실행된다.
시간 복잡도O(n^3)

2. 알고리즘

크리스토피데스 알고리즘은 완전 그래프에서 외판원 문제의 근사해를 찾는 알고리즘이다. 이 알고리즘은 최적해의 1.5배를 넘지 않는 해를 보장한다.[1][11][14]

알고리즘 적용을 위해 우선 외판원 문제 G=(V,w)를 정의한다. G는 V의 점들과 점들 사이 변으로 이루어진 완전 그래프이고, w는 G의 모든 변들에 0 이상의 가중치를 부여한다. 이때, G의 모든 점 u, v, x에 대해 삼각 부등식 w(uv) + w(vx) ≥ w(ux)이 성립한다.

알고리즘의 개략적인 순서는 다음과 같다.[1][11][14]

1. G의 최소 신장 트리 T를 만든다.

2. T에서 홀수 차수를 갖는 정점들의 집합 O를 정의한다. (악수 보조 정리에 의해 O는 짝수개의 원소를 갖는다.)

3. O에 의해 형성된 유도된 부분 그래프에서 최소 비용의 완전 매칭 M을 찾는다.

4. M과 T의 변들을 합쳐 모든 점들이 짝수 차수를 갖는 다중 그래프 H를 형성한다.

5. H에서 오일러 회로를 구성한다.

6. 5단계에서 찾은 회로에서 반복되는 점들을 제거하여 해밀턴 회로로 변경한다.

5단계와 6단계는 여러 다른 경로를 제공할 수 있다.

2. 1. 최소 신장 트리 (Minimum Spanning Tree, MST) 구성

G영어의 최소 비용 신장 트리 T영어를 구한다.[14]

2. 2. 홀수 차수 정점 집합 구성

핸드셰이킹 보조정리에 의해, 최소 신장 트리에서 차수가 홀수인 정점들의 집합은 항상 짝수 개의 원소를 갖는다.[1][11][14]

2. 3. 최소 가중치 완전 매칭 (Minimum Weight Perfect Matching) 생성

에 의해 유도된 부분 그래프에서 최소 가중치 완전 매칭 을 찾는다.[1] 이 과정은 홀수 차수 정점들로 이루어진 부분 그래프에서, 모든 정점이 서로 연결되면서 가중치의 합이 최소가 되는 완전 매칭을 찾는 것을 목표로 한다.

2. 4. 오일러 회로 (Eulerian Circuit) 구성

최소 신장 트리와 최소 가중치 완전 매칭의 간선들을 합쳐 모든 정점의 차수가 짝수인 다중 그래프(Multigraph)를 만든다. 이 다중 그래프에서 모든 간선을 한 번씩만 지나는 오일러 회로를 찾는다.[14][1][11]

2. 5. 해밀턴 회로 (Hamiltonian Circuit) 생성

크리스토피데스 알고리즘은 오일러 회로에서 중복 방문하는 정점을 건너뛰는 방식(단축, Shortcutting)으로 모든 정점을 한 번씩만 방문하는 해밀턴 회로를 만든다.[1][11][14] 즉, 이전 단계에서 찾은 오일러 회로에서 이미 방문했던 정점을 건너뛰는 방식으로 해밀턴 회로를 생성한다.

3. 근사 비율

크리스토피데스 알고리즘으로 구한 해의 비용은 최적해의 3/2배를 넘지 않는다. 즉, 근사 비율은 3/2이다. 실제로 크리스토피데스 알고리즘의 근사율을 3/2에 한없이 가깝게 만들 수 있는 정점 집합이 존재한다.[13]

3. 1. 증명

외판원 문제의 최적해를 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이다.[15][1][11]

4. 계산 복잡도

알고리즘의 최악의 경우 복잡도는 완전 매칭 단계에 의해 지배되며, 이 단계는 O(n3)의 복잡도를 갖는다.[2] 세르듀코프의 논문에서는 O(n3 log n)의 복잡도를 주장했는데,[4] 이는 저자가 덜 효율적인 완전 매칭 알고리즘만 알고 있었기 때문이다.[3]

5. 예시

주어진 그래프
삼각 부등식을 만족하는 가중치가 부여된 완전 그래프가 주어짐.
최소 신장 트리
최소 비용 신장 트리를 계산함.
홀수 차수 꼭짓점
주어진 트리에서 홀수 차수를 갖는 꼭짓점 집합을 정의함.
부분 그래프
앞서 정의된 홀수 차수 꼭짓점 집합을 이용하여 부분 그래프를 구함.
최소 비용 완벽 부합
부분 그래프에서 최소 비용 완벽 부합을 찾음.
오일러 다중 그래프
최소 비용 신장 트리와 완벽 부합을 합쳐 오일러 다중 그래프를 형성함.
오일러 경로
오일러 경로를 계산함.
결과
반복되는 꼭짓점들을 지워 알고리즘의 결과물을 얻음.


6. 한계 및 개선

크리스토피데스 알고리즘은 3/2보다 더 나은 근사 비율을 보장할 수 없다는 한계가 있다. 예를 들어, ''n''개의 정점으로 구성된 경로에서 간선 가중치가 1이고, 두 단계 떨어진 정점은 1 + ''ε'' (''ε''는 매우 작은 양수)로 연결된 경우, 최소 신장 트리는 길이 ''n'' - 1의 경로가 되고, 홀수 정점은 경로 끝점 두 개뿐이다. 이들을 잇는 완벽 매칭은 가중치가 약 ''n''/2인 간선 하나로 구성된다.[5]

트리와 매칭을 합치면 사이클이 만들어지는데, 이 사이클의 가중치는 약 3''n''/2이다. 하지만 최적해는 가중치 1 + ''ε''의 간선과 경로 끝점에 인접한 가중치 1의 간선 두 개를 사용하여 총 가중치가 (1 + ''ε'')(''n'' - 2) + 2가 된다. ''ε''가 매우 작으면 이 값은 ''n''에 가까워지므로, 근사 비율은 3/2에 수렴한다.[5]

이러한 한계에도 불구하고, 칼린(Karlin), 클라인(Klein), 가란(Gharan)은 크리스토피데스 알고리즘보다 더 나은 1.5 − 10−36의 근사 비율을 가지는 확률적 근사 알고리즘을 제시했다.[6][7] 이 알고리즘은 최소 신장 트리 대신 확률 분포를 따르는 무작위 트리를 사용하며, 2021년 컴퓨팅 이론 심포지엄에서 최우수 논문상을 받았다.[8]

유클리드 공간에서는 TSP의 기하학적 인스턴스에 대해 최적값의 1+\tfrac1c 배 이하의 길이의 경로를 찾는 다항 시간 근사 기법(PTAS) 알고리즘이 존재한다.[9] 산지브 아로라와 조셉 S. B. 미첼은 유클리드 TSP에 대한 PTAS를 발견하여 2010년 괴델상을 수상했다.

크리스토피데스-세르듀코프 알고리즘은 스태커 크레인 문제에도 사용될 수 있으며, 9/5의 근사 비율을 달성한다.[10]

6. 1. 근사 비율의 한계

크리스토피데스 알고리즘은 근사 비율이 임의로 3/2에 가까운 해를 찾는 외판원 문제 입력이 존재한다. 이러한 입력은 ''n''개의 정점으로 구성된 경로로 형성되며, 경로의 간선은 가중치 1을 가진다. 경로에서 두 단계 떨어진 정점은 매우 작지만 양수인 ''ε''를 사용하여 가중치 1 + ''ε''로 연결된다.[5]

완전 그래프의 나머지 모든 간선은 이 하위 그래프의 최단 경로로 주어진 거리를 갖는다. 그러면 최소 신장 트리는 길이 ''n'' - 1의 경로로 주어지며, 유일한 두 개의 홀수 정점은 경로 끝점이다. 이들의 완벽 매칭은 가중치가 약 ''n''/2인 단일 간선으로 구성된다.[5]

트리와 매칭의 합집합은 사이클이며, 단축 경로는 없다. 가중치는 약 3''n''/2이다. 그러나 최적의 해는 가중치 1 + ''ε''의 간선을 경로 끝점에 인접한 가중치 1의 두 간선과 함께 사용하며, 총 가중치는 (1 + ''ε'')(''n'' - 2) + 2이고, ''ε''의 작은 값에 대해 ''n''에 가깝다. 따라서 3/2의 근사 비율을 얻는다.[5]

6. 2. 추가 연구

칼린(Karlin), 클라인(Klein), 가란(Gharan)은 크리스토피데스 알고리즘의 근사 비율 1.5보다 작은 1.5 − 10−36의 근사 비율을 가지는 확률적 근사 알고리즘을 제시하였다.[6][7] 이 알고리즘은 크리스토피데스 알고리즘과 유사하게 작동하지만, 최소 신장 트리 대신 신중하게 선택된 확률 분포를 따르는 무작위 트리를 사용한다. 이 연구는 2021년 컴퓨팅 이론 심포지엄에서 최우수 논문상을 수상했다.[8]

d 차원의 유클리드 공간에서는 모든 c>0에 대해 다음 시간 안에 TSP의 기하학적 인스턴스에 대한 최적값의 1+\tfrac1c 배 이하의 길이의 경로를 찾는 다항 시간 알고리즘이 존재한다.

:O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right) 시간.

각 상수 c에 대해 이 시간 제한은 다항 시간이므로, 이를 다항 시간 근사 기법(PTAS)이라고 한다.[9] 산지브 아로라와 조셉 S. B. 미첼은 유클리드 TSP에 대한 PTAS를 동시에 발견한 공로로 2010년 괴델상을 수상했다.

크리스토피데스-세르듀코프 알고리즘은 스태커 크레인 문제를 근사하는 데에도 사용될 수 있다. 스태커 크레인 문제는 거리 공간에서 점들의 순서쌍이 주어지고, 이 순서쌍들을 순서대로 방문하는 최단 경로를 찾는 문제이다. 이 알고리즘은 스태커 크레인 문제에 대해 9/5의 근사 비율을 달성한다.[10]

참조

[1] 서적 Algorithm Design and Applications Wiley
[2] 간행물 Worst-case analysis of a new heuristic for the travelling salesman problem https://apps.dtic.mi[...]
[3] 논문 A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
[4] 논문 О некоторых экстремальных обходах в графах http://nas1.math.nsc[...] 1978
[5] 서적 Encyclopedia of Algorithms Springer-Verlag
[6] 간행물 STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 Association for Computing Machinery
[7] 뉴스 Computer Scientists Break Traveling Salesperson Record https://www.quantama[...] 2020-10-10
[8] 웹사이트 ACM SIGACT - STOC Best Paper Award https://www.sigact.o[...] 2022-04-20
[9] 논문 Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems
[10] 논문 Approximation algorithms for some routing problems
[11] 서적 Algorithm Design and Applications Wiley
[12] 간행물 Worst-case analysis of a new heuristic for the travelling salesman problem
[13] 서적 Encyclopedia of Algorithms https://books.google[...] Springer-Verlag
[14] 서적 Algorithm Design and Applications Wiley
[15] 서적 Algorithm Design and Applications Wiley


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com