외판원 문제
가장 짧은 순회 길을 찾아서
지도 위에 점 5개를 찍고 모든 점을 한 번씩만 방문한 뒤 출발점으로 돌아오는 가장 짧은 경로를 찾아보세요.
점이 5개일 때는 금방 찾지만 점이 30개로 늘어나면 슈퍼컴퓨터로도 모든 길을 다 따져볼 수 없습니다. 경우의 수가 왜 우주 전체 원자 수보다 많아질까요?
이야기
도시 몇 곳을 모두 한 번씩 들르고 돌아오는 가장 짧은 길을 찾으려 합니다. 어려워 봐야 얼마나 어렵겠나 싶습니다.
도시가 넷이면 경우가 셋뿐입니다. 다섯이면 열둘. 열이면 18만. 스물이면 6경이 넘습니다. 서른이면 우주의 나이로도 다 못 셉니다.
도시 하나 늘 때마다 경우가 곱절로 곱절로 늘어납니다. 컴퓨터가 아무리 빨라도 소용없습니다.
그래서 사람들은 방법을 바꿨습니다. 가장 짧은 길 대신 충분히 짧은 길을 빠르게 찾는 것입니다. 가까운 도시부터 가 보고, 그다음 조금씩 고쳐 나갑니다.
이 문제가 유명한 까닭은 따로 있습니다. 답을 찾기는 어려운데 확인하기는 쉽습니다. 길을 하나 주면 길이를 재기만 하면 되니까요. “확인하기 쉬우면 찾기도 쉬운가?” — 이것이 수학의 일곱 난제 가운데 하나인 P 대 NP 문제입니다.
🚩 그런데 「어렵다」는 말이 「못 푼다」는 뜻은 아닙니다. 도시가 열 곳만 되어도 길이 18만 가지가 넘고, 스무 곳이면 우주의 나이로도 다 못 셉니다. 그런데도 2006년에 85,900개 도시 문제가 실제로 풀렸습니다. 그것도 「이보다 짧은 길은 없다」는 증명까지 붙여서 말입니다.
모든 길을 다 세지 않고도 가망 없는 갈래를 통째로 잘라 내는 방법을 찾아낸 덕분입니다.
택배 차량의 배달 순서가 이 문제입니다. 도시가 조금만 늘어도 경우의 수가 폭발합니다.
그래서 완벽한 답 대신 충분히 좋은 답을 빨리 찾는 방법을 씁니다. 반도체 회로 배선, 유전자 서열 맞추기에도 같은 문제가 나옵니다.
계단 넷 — 같은 사실을 네 깊이로
도시 대여섯 개로 길을 찾아본다
종이에 도시 4개를 찍고 길이를 적어 둡니다. 출발점을 정하고 모든 도시를 돌아오는 경로를 하나씩 선으로 이어 길이를 더해 봅니다.
도시가 4개일 때는 가능한 경로가 3개뿐이지만, 도시가 하나씩 늘어날 때마다 찾아보아야 할 경로의 수가 걷잡을 수 없이 불어나는 것을 직접 확인해 보세요.
도시를 돌아 보세요
도시 하나가 늘 때마다 몇 배씩 늘어납니다.
경우의 수가 폭발하는 것
방문할 도시가 개일 때 출발점을 제외하고 돌아보는 순서의 경우의 수는 가지입니다.
도시가 5개면 12가지, 10개면 181,440가지이지만, 도시가 30개가 되면 경우의 수는 약 가지가 됩니다. 1초에 1조 개씩 계산하는 슈퍼컴퓨터로도 1억 년 이상 걸리는 조합 폭발이 일어납니다.
얼마나 걸리나
25 곳이면 우주가 끝나도 못 끝냅니다.
근사 알고리즘
외판원 문제(TSP)는 최적해를 다항 시간 안에 찾는 알고리즘이 알려지지 않은 대표적인 NP-난해(NP-hard) 문제입니다.
모든 경우를 무식하게 다 뒤지는 대신, 삼각부등식을 만족하는 경우 최소 신장 트리(MST)를 기반으로 최적해의 1.5배 이내를 보장하는 크리스토피데스 근사 알고리즘(Christofides Algorithm)이나 동적 계획법(Held-Karp 알고리즘)으로 실용적인 최단 경로를 구합니다.
어림으로 풀어 보세요
「완벽하지 않아도 좋다」고 하면 순식간에 풀립니다.
P vs NP
외판원 문제는 밀레니엄 난제인 P 대 NP 문제(P vs NP Problem)의 중심에 서 있습니다. TSP를 다항 시간 에 해결하는 알고리즘이 발견된다면 모든 NP 문제가 P에 속하게 되어 인류의 암호학과 계산 이론이 근본적으로 뒤바뀝니다.
현재는 유전 알고리즘, 담금질 기법(Simulated Annealing), 반도체 회로 마이크로칩 배선 설계 및 택배 물류 최적화 엔진에 핵심 기술로 쓰입니다.
가장 큰 기록
「불가능」과 「오래 걸림」은 다릅니다.
풀어 보기
외판원 문제와 경우의 수. 개의 도시를 모두 한 번씩 방문하고 돌아오는 서로 다른 순회 경로의 수는 가지이다.
(1) 도시가 4개일 때 가능한 순회 경로의 수를 구하시오.
(2) 도시가 6개일 때 가능한 순회 경로의 수를 구하시오.
(3) 도시가 5개인 완전 그래프에서 가장 가까운 도시를 차례로 선택하는 탐욕(Greedy) 알고리즘이 항상 전체 최단 경로를 보장하지는 않는 까닭을 간략히 서술하시오.
(2) (6-1)! / 2 = 5! / 2 = 120 / 2 = 60가지가 됩니다.
답과 풀이 보기
(1) 가지
(2) 가지
(3) 탐욕 알고리즘은 지금 가장 가까운 곳만 봅니다. 그러다 보면 가까운 도시들을 먼저 다 먹어 치우고, 마지막에 멀리 떨어진 도시를 하나 남겨 아주 긴 길을 되돌아와야 합니다.
한 걸음씩 최선을 고른다고 전체가 최선이 되지는 않습니다.
도시가 늘면 경우의 수가 무섭게 커집니다. 이면 가지 — 1 초에 1 억 개를 따져도 19 년이 걸립니다. 경우의 수가 계승으로 자라기 때문이라, 도시를 하나 더할 때마다 곱하기로 늘어납니다.
더 멀리
이 문제는 매일 우리 곁에서 풀리고 있습니다.
- 택배 경로 — 기사 한 사람의 하루 동선이 이 문제입니다
- 회로 기판 — 드릴이 구멍을 뚫는 순서를 정할 때 씁니다
- 유전자 분석 — 조각을 이어 붙이는 순서를 찾는 데도 쓰입니다
이어지는 장
모든 도시를 한 번씩만 거쳐 출발점으로 돌아오는 외판원 문제는 극도로 풀기 어렵지만, 모든 도로를 빠짐없이 한 번씩만 지나 돌아오는 한붓그리기 문제는 꼭짓점의 홀수 차수 여부만 세면 단숨에 해결됩니다 — 제100장에서 점을 도는 길과 선을 도는 길의 결정적 난이도 차이를 비교해 보세요.
영감을 받은 곳
1930년 카를 멩거(Karl Menger)가 빈 대학 수학 세미나에서 「메신저 문제」로 정식 제기하고, 1954년 조지 댄치그 등이 49개 도시 최단 순회 경로를 계산한 RAND 연구소 보고서에서 발전했습니다.