외판원 문제 해설

외판원에게 도시 목록을 주고, 각 도시를 한 번씩 방문하고 집으로 돌아오는 가장 짧은 여행을 찾으라고 해 봅시다. 제안된 경로는 누구나 확인할 수 있고, 나쁜 경로는 누구나 눈으로 보고 개선할 수 있지만, 언제나 최선의 경로를 찾는 빠른 방법은 아무도 모릅니다. 외판원 문제는 어려운 문제의 대표적인 예가 되었고, 이 문제를 공략하려고 고안된 방법들은 이제 배송을 계획하고, 회로 기판에 구멍을 뚫고, 유전체를 조립하는 데 쓰입니다.

닫힌 순회 경로로 이어진 도시들의 지도. 출발 도시가 표시되어 있고 그 아래에 더 짧은 경로가 희미하게 보인다
닫힌 순회 경로로 이어진 도시들의 지도. 출발 도시가 표시되어 있고 그 아래에 더 짧은 경로가 희미하게 보인다

문제

순회 경로는 모든 도시를 정확히 한 번씩 방문하고 출발한 곳에서 끝나며, 그 길이는 도중의 거리를 모두 더한 값입니다. 과제는 가장 짧은 순회 경로를 찾는 것입니다. 여기서 다루는 형태에서는 거리가 지도 위의 직선 거리이므로, A에서 C로 가는 길이 B를 거쳐 가는 길보다 길어지는 일은 없습니다. 이것이 메트릭 외판원 문제입니다. 이 퍼즐은 1930년 무렵 수학자 카를 멩거(Karl Menger)가 논의했고, 이름은 그 뒤 수십 년 동안 랜드 연구소(RAND Corporation)의 수학자들이 이 문제를 다루면서 널리 쓰이게 되었습니다.

1970년의 카를 멩거. 그는 1930년경 외판원 문제를 논했다.
1970년의 카를 멩거. 그는 1930년경 외판원 문제를 논했다.

경로의 폭발

출발 도시를 고정합니다. 다음 도시는 n − 1가지, 그다음은 n − 2가지를 고를 수 있고, 이런 식으로 이어지며, 모든 경로는 두 방향으로 돌 수 있으므로 순회 경로는 (n − 1)! / 2개입니다. 도시 10개면 181,440개로, 컴퓨터에게는 쉽습니다. 20개면 약 6 × 10¹⁶개이고, 70개면 관측 가능한 우주의 원자 수를 넘습니다. 컴퓨터가 빨라져도 별 도움이 되지 않습니다. 도시가 하나 늘 때마다 작업량이 약 n배가 되기 때문입니다.

NP-난해

1972년 리처드 카프(Richard Karp)는 그래프에 모든 꼭짓점을 지나는 순회, 즉 해밀턴 순환이 있는지 묻는 문제가 모두 똑같이 어려운 NP-완전 문제들의 한 집합에 속한다는 것을 보였습니다. 외판원 문제는 이 문제를 포함하므로 NP-난해입니다. 외판원 문제를 빠르게 푸는 방법이 있다면 일정 계획, 물류, 암호학의 수천 가지 다른 문제도 빠르게 풀 수 있게 됩니다. 그런 방법이 존재하는지가 바로 P 대 NP 문제이며, 이는 밀레니엄 상 문제 가운데 하나입니다.

정확한 방법: Held–Karp

1962년 마이클 헬드(Michael Held)와 리처드 카프, 그리고 이와 독립적으로 리처드 벨먼(Richard Bellman)이 동적 계획법을 사용했습니다. 도시의 모든 집합 S와 S에 속한 모든 도시 j에 대해, 출발 도시에서 시작해 S의 도시들을 정확히 방문하고 j에서 끝나는 최단 경로를 계산합니다. 각 값은 S에서 j를 뺀 집합의 값들로부터 구해지므로, 표는 작은 집합부터 큰 집합 순으로 채워지고 마지막에 가장 짧은 순회 경로가 나옵니다. 필요한 단계는 n!이 아니라 약 n² · 2ⁿ인데, 도시 30개라면 이는 몇 분과 우주의 나이만큼의 차이입니다. 그래도 여전히 지수적으로 늘어납니다.

1962년의 리처드 벨먼, 알프레드 아이젠스타트 촬영. 그는 1950년대 초 랜드 연구소에서 일하면서 동적 계획법이라는 이름을 붙였다.
1962년의 리처드 벨먼, 알프레드 아이젠스타트 촬영. 그는 1950년대 초 랜드 연구소에서 일하면서 동적 계획법이라는 이름을 붙였다.

빠른 구성 규칙

최근접 이웃은 항상 아직 방문하지 않은 가장 가까운 도시로 이동합니다. 간단하고 빠르지만 몇몇 도시를 남겨 두기 쉬워서 마지막에 먼 길을 돌아 그 도시들을 들러야 하므로, 경로는 보통 최적보다 약 25% 깁니다. 반면 삽입 방법은 닫힌 고리를 유지하면서 남은 도시를 하나씩 비용이 가장 적게 드는 곳에 추가합니다. 1976년 니코스 크리스토피데스(Nicos Christofides)는 어떤 메트릭 지도에서도 최적값의 1.5배를 넘지 않음이 보장되는 구성법을 찾아냈는데, 이 한계는 40년 넘게 거의 깨지지 않았습니다.

경로 개선: 2-opt

국소 탐색은 아무 경로에서나 시작해 경로를 짧게 만드는 작은 변경을 계속합니다. 고전적인 이동인 2-opt는 두 변을 없애고 두 조각을 반대 방식으로 다시 이어, 그 사이 구간의 방향을 뒤집습니다. 두 변이 교차할 때마다 이 이동은 교차를 풀고 길이를 줄이므로, 2-opt로 더 이상 개선할 수 없는 경로는 결코 자기 자신과 교차하지 않습니다. 무작위 지도에서 2-opt 경로는 보통 최적보다 약 5% 깁니다. 세 변을 바꾸는 더 강한 이동이나 1973년 린과 커니핸이 만든 가변 깊이 방법을 쓰면 더 가까이 갈 수 있습니다.

담금질 기법

국소 탐색은 훨씬 더 좋은 경로가 있는데도 어떤 이동을 하나 해도 나빠지기만 하는 경로에 갇힐 수 있습니다. 1983년 스콧 커크패트릭(Scott Kirkpatrick), 대니얼 젤라트(Daniel Gelatt), 마리오 베키(Mario Vecchi)가 이 문제에 적용한 담금질 기법은 야금학에서 아이디어를 빌려 왔습니다. 더 나쁜 이동을 온도에 따라 달라지는 확률로 받아들이는데, 온도는 처음에 높고 천천히 낮아집니다. 초반에는 경로가 자유롭게 돌아다니고, 마지막에는 개선만 받아들여집니다. 충분히 천천히 식히면 매우 좋은 경로를 안정적으로 찾아냅니다.

직접 탐색하기

외판원 문제 데모를 열어 도시를 최대 200개까지 무작위로, 원 위에, 군집으로, 격자 위에, 또는 원하는 곳을 클릭해 놓아 보세요. 최근접 이웃이 마지막 도시들을 남겨 두는 모습과 2-opt가 모든 교차를 푸는 모습을 지켜보고, 담금질 기법의 온도가 식어 가는 과정을 따라가고, Held–Karp가 도시 12개까지 최단 경로를 증명하게 해 보세요. ‘모두 비교’는 같은 지도에서 모든 방법을 실행하고 각 경로가 찾은 최단 경로보다 얼마나 긴지 보여 줍니다.

자주 묻는 질문

외판원 문제는 어디에 쓰이나요?

무언가가 여러 장소를 효율적인 순서로 방문해야 하는 곳이라면 어디든 쓰입니다. 배송과 수거 경로, 회로 기판 위를 지나는 드릴이나 레이저의 경로, 망원경이 별을 관측하는 순서, 창고의 피킹 순서, 그리고 거리를 다르게 정의하면 DNA 서열을 조립할 때 조각들의 순서도 해당합니다.

지금까지 정확히 풀린 가장 큰 문제는 무엇인가요?

1954년 조지 댄치그(George Dantzig), 레이 풀커슨(Ray Fulkerson), 셀머 존슨(Selmer Johnson)은 미국의 49개 도시를 지나는 최단 경로를 증명했습니다. 2006년에는 데이비드 애플게이트(David Applegate), 로버트 빅스비(Robert Bixby), 바셰크 흐바탈(Vašek Chvátal), 윌리엄 쿡(William Cook)의 Concorde 풀이기가 수년에 걸친 컴퓨터 시간을 들여 칩 설계에서 나온 85,900개 점을 지나는 최적 경로를 증명했습니다.

가장 짧은 경로에는 항상 교차가 없나요?

그렇습니다. 직선 거리를 쓰는 평평한 지도에서는 그렇습니다. 두 변이 교차한다면, 그 두 변을 그것들이 이루는 사각형의 두 변으로 바꾸면 경로가 짧아지므로, 교차하는 경로는 가장 짧은 경로일 수 없습니다.

휴리스틱은 매번 같은 경로를 내놓나요?

여기서 쓰는 최근접 이웃, 최소 비용 삽입, 2-opt는 결정론적이어서 같은 도시들에서는 같은 경로를 내놓습니다. 담금질 기법은 무작위 경로에서 시작해 무작위 이동을 하므로 두 번 실행하면 다른 경로로 끝날 수 있지만, 길이는 보통 거의 같습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

외판원 문제 데모 열기