- 경로
- 찾은 최단 길이
- 출발점
| 방법 | 길이 | 최단 대비 | 단계 수 |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
외판원 문제
외판원은 모든 도시를 한 번씩 방문하고 집으로 돌아와야 합니다. 어떤 순서로 돌아야 여행이 가장 짧을까요? 묻기는 쉽지만, 도시 수가 늘어나면 모든 순서를 시도해 답을 구하는 것은 가망이 없습니다. 도시가 30개만 되어도 순회 경로는 약 4.4 × 10³⁰개입니다. 지도에 도시를 흩뿌리거나 직접 클릭해 놓은 다음, 빠른 어림 규칙과 영리한 개선 방법, 그리고 하나의 정확한 방법이 한 단계씩 경로를 만들어 가는 모습을 지켜보고, 빠른 방법이 얼마나 가까이 가는지 확인하세요. 도시의 배치와 개수를 고르고 방법을 선택한 뒤 ‘풀기’를 누르면 순회 경로가 한 단계씩 만들어지는 모습을 볼 수 있고, ‘한 단계’를 누르면 한 번에 한 수씩 진행합니다. 지도를 클릭하면 도시가 추가되고, 도시를 클릭하면 삭제됩니다. ‘모두 비교’는 같은 도시들에서 모든 방법을 실행하고 각 방법이 찾은 최단 경로와 얼마나 차이 나는지 보여 줍니다. 빨간 도시가 여행의 출발점입니다.
작동 원리
- 배치와 도시 수를 고르거나, 지도를 클릭해 직접 도시를 놓고 도시를 클릭해 삭제하세요.
- 방법을 고르고 ‘풀기’를 눌러 한 단계씩 지켜보거나, ‘한 단계’를 눌러 한 번에 한 수씩 진행하세요.
- ‘모두 비교’를 누르면 같은 도시들에서 모든 방법을 실행하고, 각 경로가 찾은 최단 경로보다 얼마나 긴지 확인할 수 있습니다.
왜 어려운가
도시가 n개이면 서로 다른 순회 경로는 (n − 1)! / 2개입니다. 어디서 출발하든, 어느 방향으로 돌든 상관없기 때문입니다. 도시 5개면 12개, 10개면 181,440개, 20개면 약 6 × 10¹⁶개입니다. 모든 지도에서 n의 거듭제곱 정도로만 늘어나는 시간 안에 가장 짧은 경로를 찾는 방법은 알려져 있지 않습니다. 이 문제는 NP-난해입니다. 이 앱에서 가장 좋은 정확한 방법인 1962년의 Held–Karp 동적 계획법도 약 n² · 2ⁿ 단계가 필요하므로, 여기서는 도시 12개로 제한됩니다.
좋은 경로를 빠르게
실제로는 거의 가장 짧은 경로를 빠르게 찾을 수 있습니다. 최근접 이웃은 항상 방문하지 않은 가장 가까운 도시로 이동하며, 보통 최적 경로보다 약 25% 길게 끝납니다. 최소 비용 삽입은 고리를 키워 가며, 고리를 가장 적게 늘리는 도시를 추가합니다. 2-opt는 아무 경로에서나 시작해 두 변을 더 짧은 두 변으로 계속 바꾸는데, 이렇게 하면 모든 교차가 사라지고 보통 약 5% 이내로 접근합니다. 담금질 기법은 무작위 2-opt 이동을 하면서 아직 ‘뜨거운’ 동안에는 경로를 길게 만드는 이동도 일부 받아들이므로, 안정되기 전에 막다른 곳에서 빠져나올 수 있습니다.
자주 묻는 질문
최단 경로를 구하는 공식이 있나요?
없습니다. 가장 짧은 경로는 모든 도시의 정확한 위치에 따라 달라지며, 최악의 경우 지수적으로 늘어나는 작업량 없이 모든 지도에서 그것을 찾는 방법은 알려져 있지 않습니다. 수백 개나 수천 개의 도시라면 Concorde 같은 전문적인 정확한 풀이기가 선형 계획법과 영리한 가지치기를 결합해 최적 경로를 증명해 내며, 지금까지 정확히 풀린 가장 큰 사례는 85,900개의 점으로 이루어져 있습니다.
2-opt는 왜 모든 교차를 없애나요?
경로의 두 변이 교차하면, 그 두 변이 잇는 네 도시는 두 변을 대각선으로 하는 사각형을 이룹니다. 삼각 부등식에 따라 두 변을 사각형의 마주 보는 두 변으로 바꾸면 항상 더 짧아지고, 그 사이 구간의 방향이 뒤집힙니다. 2-opt는 더 이상 도움이 되지 않을 때까지 이런 교환을 계속하므로, 최종 경로는 절대 자기 자신과 교차하지 않습니다.
담금질 기법에서 온도란 무엇인가요?
경로를 길게 만드는 이동을 얼마나 기꺼이 받아들일지를 조절하는 값입니다. 길이를 d만큼 늘리는 이동은 확률 e^(−d/T)로 받아들여집니다. 온도 T가 높으면 거의 모든 이동이 허용되어 경로가 나쁜 배치에서 벗어날 수 있고, T가 내려가면 방법이 탐욕적으로 바뀌어 안정됩니다. 이름은 금속을 천천히 식혀 원자들이 에너지가 낮은 배열을 찾게 하는 어닐링(풀림)에서 왔습니다.
정확한 방법은 왜 도시 12개로 제한되나요?
Held–Karp는 도시의 모든 부분집합과 가능한 모든 마지막 도시에 대해 최단 경로를 저장하는데, 이는 약 n · 2ⁿ개의 수이며 각각을 n번의 비교로 채웁니다. 도시 12개면 수십만 단계이고, 25개면 수십억 단계가 됩니다. 그래도 (n − 1)! / 2개의 경로를 모두 시도하는 것보다는 훨씬 빠릅니다. 도시 12개라면 그 수는 거의 2,000만 개입니다.
서버로 전송되는 것이 있나요?
없습니다. 도시와 다섯 가지 방법은 모두 브라우저에서 실행됩니다. 클릭해 놓은 도시는 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동