외판원 순회

외판원 순회는 여러 도시를 한 번씩 모두 들르고 출발한 도시로 돌아오는 가장 짧은 길을 묻습니다. 넣는 것은 도시와 도시 사이의 거리입니다. 나오는 것은 도시를 들르는 순서입니다. 도시가 조금만 늘어도 순서의 가짓수가 폭발합니다. 정답을 빨리 구하는 방법은 아직 아무도 모릅니다. 그래서 실무에서는 정답 대신 충분히 짧은 길을 빨리 찾는 방법을 함께 씁니다.

쉽고 빠른 이해

영업 사원이 출장 한 번에 도시 여러 곳을 돌고 회사로 돌아올 때, 어느 순서로 돌아야 가장 덜 움직이는지 묻는 문제입니다. 도시들과 도시끼리의 거리를 주면 가장 짧은 순서와 그 길이가 답으로 나옵니다.

순서만 바꿔도 전체 거리가 달라집니다. 그런데 모든 순서를 다 재 보려 하면 도시가 스무 곳만 돼도 순서가 6경 가지를 넘습니다. 1초에 10억 개씩 재도 2년 가까이 걸리는 양입니다.

도시가 적으면 모든 순서를 재거나, 작은 답을 표에 적어 두고 이어 붙여 정답을 구합니다.
도시가 많으면 가까운 곳부터 들르는 식으로 빠르게 순서를 하나 만듭니다.
그 순서에서 길 두 개를 끊고 다른 짝으로 다시 이어 봅니다. 전체 길이가 줄면 그 순서로 바꿉니다.

대가는 둘 중 하나입니다. 정답을 고집하면 도시가 늘 때 시간이 감당 못 할 만큼 늘어납니다. 빨리 끝내면 나온 길이 가장 짧다는 보장이 없습니다.

상세

이 절은 외판원 순회가 무엇을 받아 무엇을 묻는지부터 봅니다. 그다음 도시 네 곳짜리 작은 예 하나를 끝까지 들고 갑니다. 그 예 위에서 정답을 구하는 방법 둘과 정답을 포기하고 빨리 가는 방법 셋을 차례로 돌려 봅니다.

이름은 여러 도시를 돌며 물건을 파는 외판원의 출장 일정에서 왔습니다. 영어로는 Traveling Salesman Problem 입니다. 줄여서 TSP 라고 부릅니다.

넣는 것과 나오는 것

외판원 순회는 그래프 위에서 묻는 문제입니다. 그래프는 점과 그 점들을 잇는 선으로 관계를 나타낸 구조입니다. 도시와 도로처럼 무엇과 무엇이 이어져 있는지를 담습니다.

점을 노드, 선을 간선이라고 합니다. 이 문제에서는 도시가 노드입니다. 두 도시를 잇는 길이 간선입니다.

간선마다 붙은 숫자는 가중치입니다. 그 간선을 지나는 비용을 뜻합니다. 이 문제에서는 두 도시 사이의 거리가 가중치입니다. 거리 대신 이동 시간이나 연료비를 넣어도 문제의 모양은 같습니다.

보통은 모든 도시 쌍 사이에 거리가 주어진다고 봅니다. 어느 두 노드도 간선 하나로 바로 이어진 그래프를 완전 그래프라고 합니다. 두 도시 사이에 길이 없으면 아주 큰 거리를 적어 두면 됩니다.

모든 노드를 한 번씩만 지나고 출발 노드로 돌아오는 고리를 해밀턴 순환이라고 합니다. 외판원이 도는 길 하나가 해밀턴 순환 하나입니다. 이 글에서는 이 고리를 줄여서 순회라고 부릅니다.

정리하면 넣는 것은 도시들과 도시 쌍마다의 거리입니다. 나오는 것은 길이 합이 가장 짧은 순회, 곧 도시를 들르는 순서입니다.

A 에서 B 로 가는 거리와 B 에서 A 로 가는 거리가 같으면 대칭 외판원 순회라고 합니다. 일방통행 길처럼 두 방향의 거리가 다르면 비대칭 외판원 순회입니다. 이 글은 대칭인 경우만 봅니다.

예시로 쓸 도시 네 곳

아래 그래프를 끝까지 씁니다. 도시는 A · B · C · D 네 곳입니다. 선 위의 숫자가 두 도시 사이의 거리입니다.

flowchart TD
    A((A)) ---|1| B((B))
    A ---|2| C((C))
    A ---|5| D((D))
    B ---|3| C
    B ---|4| D
    C ---|6| D

A 에서 출발한다고 정해 두면 순회는 셋뿐입니다. 남은 세 도시를 늘어놓는 순서는 여섯 가지입니다. 그런데 A-B-C-D-A 와 A-D-C-B-A 는 같은 고리를 거꾸로 돈 것이라 길이가 같습니다. 그래서 여섯이 셋으로 줄어듭니다.

순회	지나는 간선의 거리	길이 합
A-B-C-D-A	1 + 3 + 6 + 5	15
A-B-D-C-A	1 + 4 + 6 + 2	13
A-C-B-D-A	2 + 3 + 4 + 5	14

세 순회를 모두 재 보면 A-B-D-C-A 가 13 으로 가장 짧습니다. 이 그래프의 답이 이 순회입니다.

모든 순서를 재면 생기는 일

도시가 n 곳이면 출발 도시를 뺀 n − 1 곳을 늘어놓는 순서가 (n − 1)! 가지입니다. 느낌표는 계승입니다. 1 부터 그 수까지 모두 곱한 값이라 3! 은 3 × 2 × 1 = 6 입니다.

거꾸로 돈 고리를 한 번만 세면 순회는 (n − 1)! ÷ 2 개입니다. 도시가 하나 늘면 이 수에 늘기 전 도시 수가 곱해집니다. 도시 네 곳의 3 개가 다섯 곳에서는 3 × 4 = 12 개가 됩니다.

도시 수	순회 수
4	3
5	12
10	181,440
15	약 436억
20	약 6경

1초에 순회 10억 개를 잰다고 쳐도 도시 스무 곳이면 2년 가까이 걸립니다. 모든 순서를 재는 방법을 완전 탐색이라고 합니다. 이 문제에서는 도시가 열몇 곳만 넘어도 완전 탐색을 쓸 수 없습니다.

작은 답을 표에 적어 이어 붙이기

재는 양을 크게 줄이는 정답 구하기가 있습니다. 동적 계획법입니다. 큰 문제를 겹치는 작은 문제로 나눠 풉니다. 작은 문제의 답은 표에 적어 둔 뒤 다시 씁니다.

이 문제에서 작은 문제는 「A 에서 출발해 어떤 도시들을 모두 들르고 지금 도시 j 에 서 있을 때 걸어온 가장 짧은 거리」입니다. 표의 칸 하나는 들른 도시의 집합과 지금 서 있는 도시 j 의 짝입니다. 칸은 들른 도시 수가 적은 층부터 채웁니다.

예시 그래프로 칸을 채워 봅니다. 첫 층은 도시 하나만 들른 칸입니다. A 에서 바로 간 거리를 적으므로 B 만 들르고 B 에 선 칸은 1, D 만 들르고 D 에 선 칸은 5 입니다.

다음 층은 도시 둘을 들른 칸입니다. B 와 D 를 들르고 D 에 선 칸에 올 수 있는 길은 A-B-D 하나입니다. 그래서 1 + 4 = 5 를 적습니다. B 와 D 를 들르고 B 에 선 칸도 길이 A-D-B 하나입니다. 5 + 4 = 9 를 적습니다.

B · C · D 를 모두 들르고 C 에 선 칸은 C 직전에 어디 있었는지로 갈립니다. D 에 있다 왔으면 D 에 선 칸 5 에 D-C 거리 6 을 더해 11 입니다. B 에 있다 왔으면 B 에 선 칸 9 에 B-C 거리 3 을 더해 12 입니다. 둘 가운데 작은 11 을 적습니다.

아래 그림이 방금 채운 칸들입니다. 층이 하나 내려갈 때마다 들른 도시가 하나 늡니다. 두 길이 한 칸에서 만나면 작은 값만 남깁니다.

flowchart TD
    subgraph 층1["도시 하나를 들른 칸"]
        B1["B 만 들르고 B 에 선 칸 · 1"]
        D1["D 만 들르고 D 에 선 칸 · 5"]
    end
    subgraph 층2["B 와 D 를 들른 칸"]
        D2["D 에 선 칸 · 1 + 4 = 5"]
        B2["B 에 선 칸 · 5 + 4 = 9"]
    end
    subgraph 층3["B · C · D 를 모두 들른 칸"]
        C3["C 에 선 칸 · 11 과 12 가운데 11"]
    end
    B1 -->|B-D 4| D2
    D1 -->|D-B 4| B2
    D2 -->|D-C 6 · 11| C3
    B2 -->|B-C 3 · 12| C3
    C3 -->|C-A 2| E["A 로 돌아와 13"]

C 에 선 칸 11 에 C 에서 A 로 돌아가는 거리 2 를 더하면 13 입니다. 마지막 층의 B 에 선 칸과 D 에 선 칸도 같은 식으로 채워 돌아오는 거리를 더합니다. 셋 가운데 가장 작은 값이 13 입니다. 앞에서 세 순회를 모두 재서 얻은 답과 같습니다.

재는 양이 줄어드는 까닭은 칸을 다시 쓰는 데 있습니다. 칸을 한 번 채워 두면 그 칸을 지나는 모든 길이 다시 재지 않고 그 값을 가져다 씁니다.

들른 도시의 집합은 흔히 숫자 하나로 적습니다. 도시마다 비트 하나를 맡겨 들른 도시의 비트만 켜는 것입니다. 이런 쓰임을 비트 마스크라고 합니다.

Python

A, B, C, D = 1, 2, 4, 8  # 비트 하나씩
seen = A | B | D         # 11 = 0b1011
seen & C                 # 0: C 는 안 들름

집합이 정수 하나라서 표를 배열로 만들고 그 정수를 칸 번호로 씁니다. 도시가 n 곳이면 집합은 2ⁿ 가지입니다.

표 방식이 드는 시간과 메모리

칸은 집합 2ⁿ 가지에 서 있는 도시 n 가지를 곱한 n · 2ⁿ 개입니다. 칸 하나를 채울 때 직전 도시를 n 곳까지 봅니다. 그래서 모두 n² · 2ⁿ 번쯤 계산합니다.

이 방식은 흔히 헬드-카프 알고리즘이라는 이름으로 부릅니다. 모든 순서를 재는 방법과 견주면 아래와 같습니다.

도시 수	모든 순서 재기	표로 이어 붙이기
10	181,440	102,400
15	약 436억	약 737만
20	약 6경	약 4억
30	약 4.4 × 10³⁰	약 9,660억

도시 스무 곳에서 6경이 4억으로 줄었습니다. 1초에 10억 번 계산한다면 1초 안에 끝나는 양입니다. 그래도 2ⁿ 이 곱해져 있어서 도시가 하나 늘 때마다 두 배 넘게 불어납니다. 서른 곳이면 다시 감당하기 어려워집니다.

메모리도 칸 수만큼 듭니다. 도시 스무 곳이면 칸이 약 2천만 개입니다. 걸리는 시간보다 메모리가 먼저 모자라는 일이 흔합니다.

이 문제가 어려운 정도

앞의 두 정답 구하기는 도시가 늘면 결국 감당 못 할 만큼 느려졌습니다. 이 절은 그것이 방법이 서툴러서인지, 문제 자체가 어려워서인지를 봅니다. 계산 시간이 느는 모양을 가르는 말부터 풉니다.

n², n³ 처럼 입력 크기의 거듭제곱으로 느는 시간을 다항 시간이라고 합니다. 입력이 두 배가 되어도 시간은 네 배 · 여덟 배처럼 정해진 배수만큼만 늡니다. 2ⁿ 이나 n! 처럼 입력이 하나 늘 때마다 몇 배씩 뛰는 시간은 지수 시간이라고 합니다. 앞의 두 정답 구하기는 모두 지수 시간입니다.

외판원 순회를 다항 시간에 푸는 방법은 아직 아무도 찾지 못했습니다. 없다고 증명된 것도 아닙니다.

다항 시간에 풀리는 문제를 모은 묶음을 P(Polynomial time, 다항 시간)라고 합니다. 정렬이나 최단 경로 찾기가 P 에 듭니다.

이 문제가 어려운 정도는 NP(Nondeterministic Polynomial time, 비결정적 다항 시간)라는 묶음을 기준으로 잽니다. NP 는 답을 누가 내밀면 그 답이 맞는지 다항 시간에 확인할 수 있는 문제들입니다. 푸는 것은 어려워도 확인은 쉬운 문제들입니다.

이름의 「비결정적」은 갈림길마다 맞는 쪽을 알아서 골라 가는 가상의 기계를 가리킵니다. 그런 기계는 답을 고른 뒤 확인만 하면 됩니다. 그래서 확인이 다항 시간에 끝나는 문제는 그 기계에게 다항 시간에 풀리는 문제입니다.

NP 에 드는 것은 예 · 아니요로 답하는 문제뿐입니다. 이런 꼴을 결정 문제라고 합니다. 외판원 순회를 「길이가 K 이하인 순회가 있나」로 바꿔 물으면 결정 문제가 됩니다. 순회 하나를 받으면 거리를 더해 K 와 견주기만 하면 되므로 이 결정 문제는 NP 에 듭니다.

문제 X 를 문제 Y 로 바꿔 푼다는 것은 X 의 입력을 Y 의 입력으로 고쳐 써서 Y 의 답을 X 의 답으로 쓴다는 뜻입니다. 고쳐 쓰는 데 다항 시간이면 충분하다면, Y 를 빨리 푸는 방법이 곧 X 를 빨리 푸는 방법이 됩니다.

예를 들어 「이 그래프에 해밀턴 순환이 있나」는 외판원 순회로 바꿔 풀 수 있습니다. 이어진 노드 쌍의 거리는 1, 안 이어진 쌍은 2 로 적습니다. 그리고 「길이가 노드 수 이하인 순회가 있나」를 묻습니다. 그런 순회는 거리 1 인 간선만 지나야 하므로 두 질문의 답이 같습니다.

외판원 순회의 결정 문제는 NP-완전입니다. NP 에 들면서, NP 의 다른 모든 문제를 이 문제로 다항 시간에 바꿔 풀 수 있다는 뜻입니다. 그래서 이것 하나를 다항 시간에 풀면 NP 전체를 다항 시간에 풀게 됩니다.

가장 짧은 순회를 직접 묻는 원래 문제는 답이 순회 하나입니다. 예 · 아니요로 답하지 않으므로 NP 에 들지 않습니다. 그래도 원래 문제를 풀면 결정 문제도 바로 풀립니다. 가장 짧은 길이를 K 와 견주면 되기 때문입니다.

NP 의 모든 문제를 바꿔 풀 수 있을 만큼 어려운 문제를 NP-난해라고 부릅니다. NP-완전과 달리 NP 에 들 것까지는 요구하지 않습니다. 가장 짧은 순회를 묻는 원래 문제가 NP-난해입니다.

P 에 드는 문제는 답을 확인하는 것도 다항 시간에 되므로 모두 NP 에 듭니다. 거꾸로 NP 의 모든 문제가 P 에 드는지는 아직 아무도 모릅니다. 이 물음을 P 대 NP 문제라고 부릅니다.

정리하면 외판원 순회를 다항 시간에 푸는 정답 구하기는 아직 없습니다. 그래서 도시가 많을 때는 정답 대신 짧은 길을 빨리 얻는 쪽으로 갑니다. 다음 두 절이 그 방법입니다.

정답의 두 배를 넘지 않게 보장하기

정답을 포기하는 대신 「정답보다 얼마 이상 길지는 않다」를 보장하는 방법이 있습니다. 이런 방법을 근사 알고리즘이라고 합니다. 외판원 순회에서 가장 잘 알려진 것은 최소 신장 트리를 쓰는 방법입니다.

최소 신장 트리는 모든 노드를 잇되 고리가 없고 가중치 합이 가장 작은 간선 묶음입니다. 모든 도시를 가장 싸게 이어 두는 뼈대라서 순회를 만들 밑그림이 됩니다. 프림 알고리즘으로 구할 수 있습니다.

예시 그래프에서는 A-B(1) · A-C(2) · B-D(4) 세 간선입니다. 합은 7 입니다. A 를 맨 위에 두고 그리면 아래와 같습니다. A 아래에 B 와 C 가 붙습니다. B 아래에 D 가 붙습니다.

flowchart TD
    A((A)) ---|1| B((B))
    A ---|2| C((C))
    B ---|4| D((D))

이 방법은 삼각 부등식을 전제합니다. 두 도시를 바로 가는 거리가 다른 도시를 거쳐 가는 거리보다 길지 않다는 성질입니다. 도로 위 최단 거리나 지도 위 직선 거리는 이 성질을 지킵니다. 예시 그래프도 지킵니다.

순회를 만드는 절차는 셋입니다.

최소 신장 트리를 구합니다.
출발 도시에서 트리를 따라 모든 간선을 한 번은 가고 한 번은 되돌아오며 돕니다. 이렇게 돈 길은 트리 합의 두 배입니다.
도는 동안 이미 들른 도시가 다시 나오면 건너뛰고 다음 새 도시로 바로 갑니다.

예시 그래프에서 A 부터 돌면 A → B → D → B → A → C → A 입니다. 이미 들른 B 와 A 를 건너뛰면 A-B-D-C-A 가 남습니다. D 에서 B 와 A 를 거쳐 C 로 가던 4 + 1 + 2 = 7 이 D-C 6 으로 줄었습니다.

나온 순회의 길이는 13 으로 정답과 같습니다. 늘 정답이 나오는 것은 아닙니다. 그래도 트리 합의 두 배인 14 를 넘지 않는 것은 보장됩니다.

이 보장은 세 사실에서 옵니다. 첫째, 가장 짧은 순회에서 간선 하나를 빼면 모든 도시를 잇는 트리가 됩니다. 그러니 정답은 최소 신장 트리보다 짧을 수 없습니다. 예시에서도 정답 13 에서 C-D(6)를 빼면 최소 신장 트리 7 이 남습니다.

둘째, 트리를 두 번 도는 길은 트리 합의 두 배입니다. 셋째, 건너뛰기는 삼각 부등식 덕분에 길을 늘리지 않습니다. 셋을 이으면 나온 순회는 트리 합의 두 배를 넘지 않습니다. 트리 합은 정답보다 길지 않으므로 정답의 두 배도 넘지 않습니다.

같은 전제에서 보장을 정답의 1.5 배까지 좁히는 크리스토피데스 알고리즘도 있습니다. 트리를 두 번 도는 낭비를 줄이는 방법입니다.

크리스토피데스 알고리즘은 트리에서 간선이 홀수 개 붙은 도시끼리 짝을 지어 간선을 하나씩 더합니다. 더하는 간선의 합이 가장 작게 짝을 고릅니다. 그러면 모든 도시에 간선이 짝수 개 붙습니다. 도시에 들어갔다 나올 때마다 간선을 두 개씩 쓰므로, 이런 그래프는 간선마다 한 번씩만 지나며 한 바퀴를 돌 수 있습니다.

빨리 만들고 고쳐 나가기

보장 없이 빨리 짧은 길을 얻으려는 방법도 있습니다. 경험상 잘 통하는 요령이라는 뜻으로 휴리스틱이라고 부릅니다. 흔히 순회를 먼저 하나 빠르게 만듭니다. 그다음 조금씩 고쳐 줄입니다.

순회를 빠르게 만드는 대표 방법은 최근접 이웃입니다. 지금 도시에서 아직 안 들른 가장 가까운 도시로 가는 일을 끝까지 되풀이합니다. 매 순간 가장 좋아 보이는 것을 고르는 그리디 알고리즘의 한 가지입니다.

예시 그래프에서 A 부터 해 봅니다. A 에서 가장 가까운 B(1)로 가고, B 에서 남은 C(3)와 D(4) 가운데 C 로 갑니다. C 에서는 D(6)밖에 안 남았고 D 에서 A(5)로 돌아옵니다. 길이 15 인 A-B-C-D-A 가 나옵니다.

15 는 세 순회 가운데 가장 깁니다. 앞에서 가까운 곳만 고르다가 마지막에 먼 간선 둘을 떠안았기 때문입니다. 최근접 이웃은 도시 수의 제곱에 비례하는 시간이면 끝납니다. 대신 이런 일을 막지 못합니다.

만든 순회를 고치는 대표 방법은 2-opt입니다. 순회에서 간선 둘을 끊고, 끊긴 네 끝을 다른 짝으로 이어 봅니다. 길이가 줄면 그 순회로 바꿉니다. 이름의 2 는 한 번에 바꾸는 간선 수입니다. opt 는 최적화(optimization)에서 왔습니다.

최근접 이웃이 낸 A-B-C-D-A 에서 B-C(3)와 D-A(5)를 끊고 B-D(4)와 C-A(2)로 이으면 아래처럼 됩니다. 위가 원래 순회입니다. 아래가 고친 순회입니다. 점선은 끊은 간선입니다. 굵은 선은 새로 이은 간선입니다.

flowchart TD
    subgraph 고치기전["고치기 전 · 길이 15"]
        A1((A)) -->|1| B1((B))
        B1 -.->|3 · 끊음| C1((C))
        C1 -->|6| D1((D))
        D1 -.->|5 · 끊음| A1
    end
    subgraph 고친뒤["고친 뒤 · 길이 13"]
        A2((A)) -->|1| B2((B))
        B2 ==>|4 · 새로 이음| D2((D))
        D2 -->|6| C2((C))
        C2 ==>|2 · 새로 이음| A2
    end
    고치기전 --> 고친뒤

끊은 두 간선의 합은 8 입니다. 새로 이은 두 간선의 합은 6 입니다. 그래서 길이가 15 에서 13 으로 줄었습니다. 가운데 구간 C-D 는 도는 방향만 뒤집혔습니다.

2-opt 는 어느 간선 둘을 바꿔도 더 줄지 않을 때 멈춥니다. 이렇게 한 가지 고치기로는 더 못 나아지는 상태를 국소 최적이라고 합니다. 예시에서는 국소 최적이 정답이었습니다. 도시가 많으면 정답보다 긴 데서 멈추는 일이 흔합니다.

방법 한눈에 보기

지금까지 돌려 본 방법을 한 표로 모읍니다. 도시가 n 곳일 때입니다.

방법	나오는 답	걸리는 시간	전제
모든 순서 재기	정답	순회 (n − 1)! ÷ 2 개를 잰다	없음
표로 이어 붙이기	정답	n² · 2ⁿ	없음
최소 신장 트리 두 번 돌기	정답의 두 배 이내	트리 구하기가 n² · 도는 것은 n	삼각 부등식
최근접 이웃	보장 없음	n²	없음
2-opt	보장 없음 · 국소 최적에서 멈춤	한 바퀴에 간선 쌍 n² 개를 본다	고칠 순회 하나

표에서 고르는 기준은 도시 수와 보장입니다. 도시가 스무 곳 안팎이면 표로 이어 붙여 정답을 구할 수 있습니다. 그보다 많으면 최근접 이웃으로 순회를 만들고 2-opt 로 고칩니다. 정답과 얼마나 먼지 보장이 필요하면 최소 신장 트리 방법을 씁니다.

정답이 꼭 필요한데 도시가 많으면 가망 없는 순서를 미리 잘라 내며 찾는 분기 한정 같은 방법을 씁니다. 최악의 시간은 여전히 지수입니다. 대신 보는 순서의 수를 크게 줄입니다.