외판원 문제(TSP) 경로 계산기
도시 좌표를 넣으면 모든 도시를 한 번씩 들르고 돌아오는 가장 짧은 순회를 완전탐색으로 찾고, 최근접 이웃·2-opt 같은 근사와 나란히 놓아 몇 % 나쁜지 세어 보입니다. 도시가 늘 때 가짓수가 (n−1)!/2로 폭발하는 것도 표로 확인할 수 있습니다.
한 줄에 하나씩 「x y」 또는 「이름 x y」로 적습니다. 12개까지, 완전탐색은 10개까지 합니다.
가장 짧은 순회
41.53
도시 6개의 순회는 (n−1)!/2 = 60가지입니다. 가지치기로 그중 21가지만 끝까지 세어 답을 얻었습니다.
굵은 선이 최적 순회이고, 점선이 첫 도시에서 떠난 최근접 이웃입니다. 점선이 판을 가로지르는 자리가 「가까운 것만 집어 먹다가 마지막에 다 토해 내는」 대목입니다.
찾은 순회
최적 · A → D → B → E → C → F → A
최근접 이웃 · C → E → B → D → A → F → C
2-opt · C → E → B → D → A → F → C
도시가 늘면 가짓수가 어떻게 되나
| 도시 수 | (n−1)!/2 | 10억/초로 훑으면 |
|---|---|---|
| 5개 | 12 | 눈 깜짝할 새 |
| 8개 | 2,520 | 눈 깜짝할 새 |
| 10개 | 181,440 | 눈 깜짝할 새 |
| 12개 | 19,958,400 | 0.02초 |
| 15개 | 4.36 × 10^10 | 43.589초 |
| 20개 | 6.08 × 10^16 | 1.9년 |
| 25개 | 3.1 × 10^23 | 9,837,144.9년 |
순회는 고리라서 어디서 출발하든 같으므로 출발 도시를 하나로 못 박아도 잃는 것이 없고, 거꾸로 돈 것도 같으므로 또 반이 됩니다. 그래서 (n−1)!/2가지입니다. 도시가 하나 늘 때마다 가짓수가 거의 n배가 되므로, 컴퓨터가 아무리 빨라져도 완전탐색은 20개 언저리에서 벽에 부딪힙니다.
계산 방법
- 1도시 좌표를 한 줄에 하나씩 「x y」 또는 「이름 x y」로 적습니다.
- 2직선거리로 잴지 격자거리(맨해튼)로 잴지 고릅니다.
- 3그림에서 굵은 선(최적)과 점선(최근접 이웃)이 어디서 갈리는지 봅니다.
- 4표에서 최근접 이웃과 2-opt가 최적보다 몇 % 긴지 확인합니다.
- 5도시를 하나씩 늘려 보며 가짓수와 걸리는 시간이 어떻게 자라는지 봅니다.
자주 묻는 질문
(n−1)!/2가지입니다. 순회는 고리라서 어디서 출발하든 같은 길이므로 출발 도시를 하나로 못 박아도 잃는 것이 없고, 거꾸로 돈 고리도 같은 길이라 또 반으로 줄기 때문입니다. 도시 10개면 181,440가지, 15개면 435억 가지, 20개면 6경 가지가 넘습니다. 도시가 하나 늘 때마다 가짓수가 거의 n배가 되는 것이 이 문제의 성질입니다.
한 곳에서만 떠나면 도시 8~10개에서 평균 8~10% 나쁘고, 나쁠 때는 40%를 넘습니다. 「지금 자리에서 가장 가까운 곳으로」만 고르다 보니 마지막에 남은 도시로 가려고 판을 가로지르는 긴 변이 생겨서, 앞에서 아낀 것을 마지막 한 번에 다 토해 내기 때문입니다. 다만 출발점을 모두 해 보고 그중 제일 짧은 것을 고르면 평균 2% 안쪽으로 떨어집니다.
순회에서 변 두 개를 끊고 사이를 뒤집어 이어 붙였을 때 짧아지면 바꾸는 것을, 더 짧아질 데가 없을 때까지 되풀이하는 방법입니다. 직선거리로 재면 2-opt를 끝까지 돌린 순회에는 스스로 교차하는 변이 없습니다. 교차하는 두 변은 뒤집어 풀면 삼각부등식 때문에 반드시 짧아지기 때문입니다. 최적을 보장하지는 않지만 무작위 좌표에서 평균 0.2~0.5% 안쪽까지 붙습니다.
이 계산기는 완전탐색을 10개까지 합니다. 가지치기를 넣어 실제로 끝까지 세는 순회는 (n−1)!/2보다 훨씬 적지만, 11개를 넘으면 브라우저가 버티기 어려워집니다. 12개까지는 좌표를 넣을 수 있고 그때는 최근접 이웃과 2-opt만 냅니다. 참고로 헬드–카프 같은 동적계획법을 쓰면 20개 언저리까지, 전용 풀이기(Concorde)를 쓰면 수만 개까지 정확히 풀립니다.
다익스트라 같은 최단경로는 두 점 사이의 길을 찾는 문제라 빠르게 정확히 풀리지만, 외판원 문제는 모든 도시를 한 번씩 들르는 순서를 정하는 문제라 NP-난해입니다. 도시가 20개만 되어도 모든 순서를 훑는 것이 불가능해집니다. 다익스트라가 도시 수에 대해 다항식 시간으로 끝나는 것과 근본이 다릅니다.
모든 도시가 볼록 위치에 있으면 최적 순회는 볼록 껍질을 도는 순서 그대로입니다. 순서를 어기면 반드시 교차가 생기고, 교차하는 두 변은 풀면 더 짧아지기 때문입니다. 원 위에 점을 늘어놓고 확인해 보면 바로 보입니다. 다만 안쪽에 점이 하나라도 들어가면 이 성질은 깨집니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 완전탐색의 답을 헬드–카프 동적계획법과 대조해 검증했습니다. 무작위 좌표 300벌(도시 3~8개 × 직선거리·격자거리)에서 두 방법의 최적 길이가 일치하고, 돌려준 순서의 길이도 그 값과 맞는 것을 확인했습니다. 아예 다른 알고리즘 둘이 같은 답을 낸다는 것이 이 도구의 근거입니다.
- 볼록 위치의 점들(원 위에 놓인 점)에서는 최적 순회가 반드시 껍질을 도는 순서라는 정리를 정답지로 삼아, 무작위 각도 30벌에서 완전탐색이 그 순서를 찾아내는지 확인했습니다.
- 최근접 이웃과 2-opt가 최적보다 짧아지는 일이 없다는 것, 2-opt가 출발한 순회보다 길어지지 않는다는 것, 두 방법 모두 모든 도시를 정확히 한 번씩 담는다는 것을 무작위 입력 수백 벌로 고정했습니다.
- 「최적보다 몇 % 나쁜가」로 적은 값은 무작위 좌표 200벌(도시 8개)에서 실제로 세어 본 것입니다. 한 곳 출발 최근접 이웃이 평균 8~9%(최악 30% 넘음), 출발점을 다 해 본 것이 평균 2% 안쪽, 2-opt가 0.2~0.5%였습니다.
- 완전탐색은 이미 찾은 최선보다 길어지면 그 가지를 접습니다. 그래서 화면의 「끝까지 센 순회」는 (n−1)!/2보다 훨씬 적게 나오는데, 답은 같습니다.
- 여기서 말하는 최적은 주어진 좌표와 거리 기준 안에서의 최적입니다. 실제 배송 경로는 일방통행·좌회전 금지·시간대별 정체·차량 적재 한계가 얽혀 있어 답이 달라지므로(그때는 문제 이름부터 VRP로 바뀝니다) 그대로 현장에 쓰지 마세요.
- 도시는 12개까지, 완전탐색은 10개까지 다룹니다. 그림과 순서를 함께 보이는 것이 목적이라 그보다 크면 화면이 읽히지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.