외판원 문제, 즉 TSP는 여러 도시를 각각 한 번씩 방문하고 출발 도시로 돌아오는 순회 가운데 총비용이 가장 작은 것을 찾는 문제입니다. 도시 사이의 비용은 거리, 시간, 요금처럼 정할 수 있습니다. 설명은 간단하지만 도시 수가 늘면 가능한 방문 순서가 팩토리얼로 폭증합니다.
N개 도시가 모두 서로 연결되고 두 방향의 비용이 같은 대칭 TSP에서 출발 도시를 하나 고정하고, 순회를 거꾸로 도는 경우를 같은 경로로 보면 후보 수는 (N−1)!/2입니다. 이 식은 모든 TSP에 조건 없이 적용되는 공식이 아닙니다. 방향별 비용이 다른 비대칭 문제에서는 일반적으로 고정 출발점 기준 (N−1)!개이며, 일부 간선이 없는 그래프에서는 가능한 순회 수가 더 적거나 하나도 없을 수 있습니다.
대칭 완전 TSP의 서로 다른 순회 수: 출발점 고정 (N−1)!, 역방향 중복 제거 (N−1)!/2
외판원 문제를 그래프로 표현하기
도시를 꼭짓점, 도시 사이 이동을 변, 이동 비용을 변의 가중치로 나타냅니다. 모든 꼭짓점을 정확히 한 번 방문하고 출발점으로 돌아오는 경로는 해밀턴 순환입니다. TSP는 가능한 해밀턴 순환 가운데 가중치 합이 최소인 것을 찾습니다.
| 요소 | 그래프 표현 | TSP에서의 의미 |
|---|---|---|
| 도시 | 꼭짓점 | 한 번씩 방문할 지점 |
| 이동 가능 관계 | 변 | 두 도시 사이 이동 |
| 거리·시간·비용 | 가중치 | 최소화할 값 |
| 왕복 순회 | 해밀턴 순환 | 모든 도시 방문 후 출발지 복귀 |
모든 변을 정확히 한 번씩 지나는 오일러 순환과 혼동하면 안 됩니다. TSP는 모든 꼭짓점을 한 번씩 방문하는 해밀턴 순환을 찾되, 변은 일부만 사용합니다. 쾨니히스베르크 다리 문제의 오일러 경로는 변을 한 번씩 써야 하는 다른 문제입니다.
왜 (N−1)!/2가 되는가
N개 도시 가운데 출발 도시 A를 고정합니다. 순환은 어디서 적기 시작하느냐만 바꾼 표현이 여러 개 생기므로 시작점을 고정해 회전 중복을 없앱니다. 남은 N−1개 도시의 방문 순서는 (N−1)!개입니다.
대칭 거리에서는 A→B→C→A와 A→C→B→A의 총비용이 같습니다. 하나는 다른 하나를 반대로 돈 순서입니다. 각 순회가 정확히 한 개의 역방향 짝을 가지므로 2로 나눕니다. N≥3인 대칭 완전 그래프에서 서로 다른 무방향 순회의 수는 (N−1)!/2입니다.
| 도시 수 N | (N−1)!/2 | 후보 순회 수 |
|---|---|---|
| 4 | 3!/2 | 3 |
| 5 | 4!/2 | 12 |
| 10 | 9!/2 | 181,440 |
| 15 | 14!/2 | 43,589,145,600 |
| 20 | 19!/2 | 60,822,550,204,416,000 |
도시 20개만 되어도 단순 열거 후보가 약 6.08경 개입니다. 후보 하나의 길이를 계산하려면 N개의 변 비용을 더해야 하므로 무차별 탐색의 실제 연산은 후보 수보다 더 많습니다. 팩토리얼 증가는 지수함수보다도 빠르게 커집니다.
비대칭 TSP에서는 왜 2로 나누지 않나
일방통행이나 방향별 통행시간이 있으면 A에서 B로 가는 비용과 B에서 A로 가는 비용이 다를 수 있습니다. 이때 A→B→C→A와 A→C→B→A는 역방향 관계이지만 비용이 같다고 보장되지 않습니다. 서로 다른 후보로 남겨야 하므로 출발점만 고정한 (N−1)!개를 셉니다.
그래프가 완전하지 않으면 어떤 순열은 존재하지 않는 변을 요구해 합법적인 순회가 아닙니다. 반대로 실제 도로망을 최단거리로 완성해 도시 쌍마다 비용을 넣으면 완전 그래프로 바꿀 수 있지만, 그 비용이 삼각부등식을 만족하는지와 경로 중간의 의미를 따져야 합니다.
최적화 문제와 결정 문제
최적화 형태는 가장 짧은 순회의 비용과 경로를 찾으라고 묻습니다. 결정 형태는 주어진 한계 B 이하의 비용으로 모든 도시를 도는 순회가 존재하는지 묻습니다. 후보 경로가 주어지면 각 도시를 한 번 방문하는지와 비용이 B 이하인지 다항 시간에 확인할 수 있습니다.
TSP의 결정 버전은 NP-완전이고, 최적화 버전은 NP-난해입니다. ‘NP’는 비다항 시간을 뜻하는 약자가 아니라 nondeterministic polynomial time의 약자입니다. NP-난해하다는 말은 현재 알려진 정확 알고리즘이 느리다는 경험만 뜻하지 않고, NP의 모든 문제만큼 어려운 구조를 갖는다는 환원 기반 분류입니다.
TSP 최적화 문제는 NP-난해, 비용 한계 이하 순회의 존재를 묻는 결정 버전은 NP-완전입니다.
NP-난해가 모든 입력에서 완전탐색만 가능하다는 뜻은 아니다
NP-난해성은 일반 입력을 대상으로 최적해를 항상 구하는 다항 시간 알고리즘이 알려져 있지 않다는 뜻입니다. 특정 구조의 입력, 작은 도시 수, 한 줄에 놓인 도시처럼 제한된 경우에는 빠른 알고리즘이 있을 수 있습니다. 실제 최적화 프로그램은 단순히 모든 순열을 검사하지 않습니다.
가지한정법은 현재 최선해보다 나빠질 수밖에 없는 부분 경로를 버립니다. 절단평면법은 선형계획 완화에 제약을 추가하고, 정수계획과 결합해 큰 사례의 최적성을 증명하기도 합니다. 어려운 최악의 경우가 존재한다는 이론과 실제 데이터에서 상당한 크기를 푸는 공학은 함께 성립합니다.
동적 계획법은 팩토리얼을 2ᴺ 규모로 줄인다
헬드–카프 동적 계획법은 방문한 도시 집합 S와 마지막 도시 j를 상태로 둡니다. D(S,j)를 출발점에서 시작해 S의 도시들을 방문하고 j에서 끝나는 최소비용이라고 하면, 마지막 직전 도시 i를 고르는 점화식을 세울 수 있습니다.
D(S,j)=minᵢ∈S−{j}[D(S−{j},i)+cᵢⱼ]
상태 집합은 약 2ᴺ개이고 각 상태에서 여러 이전 도시를 비교하므로 전형적인 시간복잡도는 O(N²2ᴺ), 공간복잡도는 O(N2ᴺ)입니다. (N−1)! 전수조사보다 크게 개선되지만 여전히 지수 시간과 지수 공간입니다. 도시가 커지면 정확 계산이 빠르게 어려워집니다.
삼각부등식이 있으면 근사 보장이 가능하다
거리형 TSP에서는 c(i,k)≤c(i,j)+c(j,k)라는 삼각부등식을 가정할 수 있습니다. 유클리드 거리나 최단거리 비용은 보통 이 성질을 만족합니다. 대칭이고 삼각부등식을 만족하는 메트릭 TSP에는 최적해와의 비율을 보장하는 다항 시간 근사 알고리즘이 있습니다.
최소 신장 트리를 두 번 따라가고 이미 방문한 도시를 건너뛰는 방법은 최적값의 2배 이하 순회를 만들 수 있습니다. 크리스토피데스 알고리즘은 최소 신장 트리, 홀수 차수 꼭짓점의 최소 가중 완전 매칭, 오일러 순환과 지름길을 결합해 메트릭 대칭 TSP에서 최적값의 3/2배 이하를 보장합니다.
삼각부등식이 없는 일반 TSP에는 같은 보장을 그대로 적용할 수 없습니다. NIST 알고리즘 사전도 비삼각 TSP에서 일정한 근사비를 보장하는 다항 시간 알고리즘은 P=NP가 아니라면 존재하지 않는다는 점을 설명합니다. 문제의 조건이 근사 가능성까지 바꿉니다.
휴리스틱은 빠른 좋은 답을 찾지만 증명은 별개다
가장 가까운 도시를 차례로 선택하는 최근접 이웃법은 구현이 쉽지만 언제나 최적해를 주지는 않습니다. 2-opt는 경로의 두 변을 끊고 연결 방향을 바꿨을 때 짧아지면 교환하는 지역 탐색입니다. 3-opt, Lin–Kernighan 계열은 더 넓은 교환을 탐색합니다.
휴리스틱이 짧은 경로를 찾았다는 사실과 그것이 최적이라는 증명은 다릅니다. 하한을 함께 계산해 현재 해와의 간격을 제시하거나, 정확 알고리즘으로 탐색을 마쳐야 최적성을 증명할 수 있습니다. 현실의 배송 계획에서는 계산시간, 차량 용량, 시간창, 여러 출발지 같은 추가 제약도 있어 차량경로문제 등 다른 모형으로 확장됩니다.
작은 예제로 경로 수를 직접 세기
도시 A, B, C, D가 있고 모든 거리가 대칭이라고 하겠습니다. A를 출발점으로 고정하면 나머지 B, C, D의 순열은 3!=6개입니다. ABCDA와 ADCBA는 역방향 짝이고, ABDCA와 ACDBA, ACBDA와 ADBCA도 각각 짝입니다. 따라서 서로 다른 순회는 3개입니다.
방향별 비용이 다르면 여섯 순서를 모두 계산해야 합니다. 출발점을 고정하지 않고 단순히 N!로 세면 같은 순환을 시작 위치만 바꾼 N가지 표현이 중복됩니다. 경우의 수 공식이 달라지는 이유는 무엇을 같은 경로로 볼지에 달려 있습니다.
TSP와 최단경로 문제는 다르다
최단경로 문제는 출발점에서 도착점까지 가장 싼 길을 찾습니다. 모든 도시를 방문해야 한다는 조건이 없으며 다익스트라 알고리즘 같은 다항 시간 방법을 사용할 수 있습니다. TSP는 전체 방문 순서 자체를 선택해야 하므로 조합 구조가 훨씬 큽니다.
| 문제 | 목표 | 대표 난이도 |
|---|---|---|
| 최단경로 | 두 지점 사이 최소비용 경로 | 비음수 가중치에서 다항 시간 |
| 최소 신장 트리 | 모든 꼭짓점을 최소비용으로 연결 | 다항 시간 |
| 외판원 문제 | 모든 꼭짓점을 한 번 방문하는 최소 순회 | 최적화 버전 NP-난해 |
도로를 추가하면 TSP 해도 나아질까
고정된 비용 행렬에서 선택 가능한 간선을 추가하면 최적 TSP 비용은 나빠지지 않습니다. 기존 최적 순회가 여전히 후보로 남기 때문입니다. 하지만 실제 교통에서는 운전자들이 각자 경로를 선택하고 혼잡에 따라 비용이 변합니다. 브라에스의 역설에서 새 도로가 전체 통행시간을 늘리는 이유는 고정 비용 최적화와 게임적 교통 균형이 다른 문제임을 보여 줍니다.
실제 응용에서는 무엇을 추가로 고려하나
- 물류 배송에서는 차량 수, 적재량, 고객 시간창, 운전자의 근무시간이 추가됩니다.
- 회로 기판 가공에서는 드릴이나 장비의 이동시간을 줄입니다.
- 유전체 분석에서는 조각의 순서나 유사도 비용과 연결된 변형이 등장합니다.
- 로봇 경로에서는 장애물, 방향 전환 비용, 동적 환경을 반영해야 합니다.
- 천문 관측 순서에서는 망원경 회전시간과 관측 가능 시간이 제약이 됩니다.
이런 문제를 모두 순수 TSP라고 부를 수는 없습니다. 용량 제약이 붙으면 차량경로문제, 여러 외판원이 있으면 다중 TSP, 방문 시간이 정해지면 시간창 TSP처럼 모형이 달라집니다. 올바른 알고리즘을 고르려면 비용과 제약을 먼저 명확히 해야 합니다.
외판원 문제에서 자주 하는 오해
- 모든 TSP의 후보 수가 언제나 (N−1)!/2라고 말합니다. 대칭 완전 순회와 역방향 동일시가 필요합니다.
- NP-난해를 ‘절대로 풀 수 없음’으로 해석합니다. 작은 사례와 구조화된 사례는 정확히 풀 수 있습니다.
- 좋은 휴리스틱 해를 찾은 것과 최적성을 증명한 것을 같은 결과로 봅니다.
- 모든 변을 한 번씩 쓰는 오일러 경로와 모든 도시를 한 번씩 방문하는 해밀턴 순환을 혼동합니다.
- 삼각부등식이 없는 문제에 메트릭 TSP의 근사 보장을 그대로 적용합니다.
- 팩토리얼 전수조사만이 정확 알고리즘이라고 생각합니다. 동적 계획법, 가지한정, 절단평면 등 더 나은 방법이 있습니다.
외판원 문제 FAQ
왜 N!이 아니라 (N−1)!인가요?
순환 경로는 시작 위치만 바꿔도 같은 순회입니다. 출발 도시 하나를 고정하면 회전으로 생기는 N중 중복이 사라져 (N−1)!이 됩니다.
왜 다시 2로 나누나요?
대칭 비용에서는 한 순회를 정방향과 역방향으로 도는 비용이 같고 같은 무방향 순회로 볼 수 있기 때문입니다. 비대칭 TSP에서는 2로 나누지 않습니다.
TSP가 NP-난해하면 최적해를 구할 수 없나요?
구할 수 있습니다. 다만 일반 입력에서 항상 빠르게 해결하는 다항 시간 정확 알고리즘이 알려져 있지 않습니다. 도시 수와 구조에 따라 동적 계획, 정수계획, 가지한정 등으로 최적해와 증명을 얻을 수 있습니다.
핵심 정리
외판원 문제는 모든 도시를 한 번씩 방문하고 출발점으로 돌아오는 최소비용 해밀턴 순환을 찾습니다. N개 도시의 대칭 완전 그래프에서 출발점을 고정하면 (N−1)!개의 순서가 있고, 역방향을 같은 순회로 보면 (N−1)!/2개가 됩니다. 비대칭 비용이나 불완전 그래프에는 이 공식을 조건 없이 적용할 수 없습니다.
TSP 최적화는 NP-난해하지만 단순 팩토리얼 열거만 있는 것은 아닙니다. 헬드–카프 동적 계획법은 O(N²2ᴺ), 정확 솔버는 가지한정과 절단평면을 사용하며, 메트릭 TSP에는 근사 보장도 있습니다. 문제를 설명할 때 경우의 수 공식의 전제, 정확해와 근사해의 차이, 최적화와 결정 문제의 난이도를 함께 밝혀야 합니다.