외판원 순회 문제(TSP): 비트마스킹과 동적 계획법으로 최소 비용 경로 찾기

문제 개요

한 명의 외판원이 특정 도시에 위치해 있으며, 목록에 포함된 모든 도시를 반드시 방문해야 합니다. 각 도시 간 이동 비용은 미리 주어져 있습니다. 이때 모든 도시를 정확히 한 번씩 방문한 뒤 출발 도시로 되돌아오는 경로 중 이동 비용이 최소가 되는 경로를 찾는 것이 바로 외판원 순회 문제(Traveling Salesman Problem, TSP)입니다.

이 문제에서 그래프는 완전 그래프(complete graph)여야 합니다. 완전 그래프란 임의의 두 정점 사이에 항상 간선이 존재하는 그래프로, 외판원이 어떤 도시에서든 다른 어떤 도시로든 직접 이동할 수 있음을 의미합니다.

결국 우리가 구해야 하는 것은 최소 가중치 해밀턴 순환(minimum weighted Hamiltonian cycle)입니다. 해밀턴 순환이란 그래프의 모든 정점을 정확히 한 번씩 지나 다시 시작점으로 돌아오는 닫힌 경로를 말합니다.

입력 및 출력 형식

Input:
Cost matrix of the matrix.
0  20 42 25 30
20  0 30 34 15
42 30  0 10 10
25 34 10  0 25
30 15 10 25  0

Output:
Distance of Travelling Salesman: 80

알고리즘 설명

이 문제는 비트마스킹(bitmasking)과 동적 계획법(Dynamic Programming)을 결합하여 효율적으로 해결할 수 있습니다. 핵심 함수의 시그니처는 다음과 같습니다.

travellingSalesman(mask, pos)

계산 결과를 저장하는 dp 테이블과, 모든 노드가 방문되었음을 표시하는 VISIT_ALL 값을 사용합니다.

입력: 방문한 도시를 비트로 마스킹하는 mask 값, 현재 위치 pos
출력: 모든 도시를 방문하는 최단 경로의 총 비용

의사 코드

Begin
    if mask = VISIT_ALL, then //모든 도시를 방문한 경우
       return cost[pos, 0]
    if dp[mask, pos] ≠ -1, then
       return dp[mask, pos]
    finalCost := ∞

    for all cities i, do
       tempMask := (shift 1 left side i times)
       if mask AND tempMask = 0, then
          tempCost := cost[pos, i] +
          travellingSalesman(mask OR tempMask, i)
          finalCost := minimum of finalCost and tempCost
    done

    dp[mask, pos] = finalCost
    return finalCost
End

알고리즘 동작 원리

종료 조건 확인: mask가 VISIT_ALL과 같다면 모든 도시를 방문한 것이므로, 현재 도시에서 출발 도시(0번)까지의 비용을 반환합니다.
메모이제이션 확인: dp[mask][pos] 값이 이미 계산되어 있다면(-1이 아니라면) 저장된 값을 그대로 반환하여 중복 연산을 제거합니다.
재귀 탐색: 아직 방문하지 않은 도시(mask의 i번째 비트가 0인 도시)를 대상으로, 현재 도시에서 i번 도시로 이동하는 비용과 이후 경로의 재귀적 최소 비용을 더합니다.
최솟값 저장: 가능한 모든 선택지 중 최소 비용을 finalCost에 저장하고, dp 테이블에 기록한 뒤 반환합니다.

각 도시의 방문 여부는 비트마스크로 관리됩니다. 예를 들어 도시가 5개라면 VISIT_ALL은 (1 << 5) - 1 = 31(2진수 11111)이 됩니다. mask의 i번째 비트가 1이면 i번 도시를 이미 방문했다는 뜻입니다.

C++ 구현 예제

#include<iostream>
#define CITY 5
#define INF 9999
using namespace std;

int cost[CITY][CITY] = {
   {0, 20, 42, 25, 30},
   {20, 0, 30, 34, 15},
   {42, 30, 0, 10, 10},
   {25, 34, 10, 0, 25},
   {30, 15, 10, 25, 0}
};

int VISIT_ALL = (1 << CITY) - 1;   // 모든 도시 방문 상태 (11111 = 31)

int dp[32][5];   // dp 배열 크기는 (2^n, n)

int travellingSalesman(int mask, int pos) {
   if(mask == VISIT_ALL)          // 모든 도시를 방문으로 표시한 경우
      return cost[pos][0];        // 현재 도시에서 출발 도시(0번)로 돌아가는 비용

   if(dp[mask][pos] != -1)        // 이미 계산된 적이 있다면
      return dp[mask][pos];       // 저장된 값 반환 (메모이제이션)

   int finalCost = INF;

   for(int i = 0; i<CITY; i++) {
      if((mask & (1 << i)) == 0) {   // i번째 비트가 0이면 아직 방문하지 않은 도시
         int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i);   // i번 도시를 방문 처리
         finalCost = min(finalCost, tempCost);
      }
   }
   return dp[mask][pos] = finalCost;
}

int main() {
   int row = (1 << CITY), col = CITY;
   for(int i = 0; i<row; i++)
      for(int j = 0; j<col; j++)
         dp[i][j] = -1;              // dp 배열을 -1로 초기화
   cout << "Distance of Travelling Salesman: ";
   cout << travellingSalesman(1, 0); // 초기 mask는 0001 (0번 도시는 이미 방문한 상태)
}

실행 결과

Distance of Travelling Salesman: 80

시간 복잡도

완전 탐색(brute force)으로 모든 순열을 검사하면 O(n!)의 시간이 걸리지만, 위와 같이 비트마스킹과 메모이제이션을 활용하면 상태 공간이 (mask, pos) 조합으로 압축되어 시간 복잡도를 O(n² × 2ⁿ), 공간 복잡도를 O(n × 2ⁿ)까지 줄일 수 있습니다. 도시 수가 많아지면 여전히 지수적으로 증가하지만, n!보다는 훨씬 효율적이므로 중소 규모의 TSP 문제에서 널리 사용되는 표준적인 접근 방식입니다.