Travelling Salesman Problem(TSP): Brute Force부터 Dynamic Programming까지

**Travelling Salesman Problem(TSP)**은 한 지점에서 출발해 모든 지점을 정확히 한 번 방문하고 다시 출발점으로 돌아오는 경로 중 총 비용이 가장 작은 경로를 찾는 문제입니다.

그래프로 표현하기

• 도시 또는 위치는 정점입니다.
• 이동 가능한 연결은 간선입니다.
• 거리, 시간, 비용은 간선의 가중치입니다.

TSP는 단순한 최단 경로 문제가 아닙니다. Dijkstra는 두 지점 사이의 최단 경로를 찾지만, TSP는 모든 지점을 포함하는 전체 순서를 최적화합니다.

Hamiltonian Cycle과의 차이

Hamiltonian Cycle은 모든 정점을 한 번씩 방문하는 순환 경로의 존재를 다룹니다.

TSP는 여기에 비용을 추가하여 가능한 순환 경로 중 최소 비용을 찾습니다.

Brute Force

가장 단순한 exact 방법은 시작점을 고정한 뒤 나머지 도시의 모든 순열을 검사하는 것입니다.

가능한 순서는 대략:

(n - 1)!

이므로 입력이 조금만 커져도 매우 비싸집니다.

Held–Karp Dynamic Programming

대표적인 상태는 다음과 같습니다.

dp[visited][last]

이는 시작점에서 출발해 visited 집합의 도시를 방문하고 last 도시에서 끝나는 최소 비용을 의미합니다.

방문 집합은 보통 bitmask로 표현합니다.

복잡도:

시간: O(n² × 2^n)
공간: O(n × 2^n)

JavaScript 예제

function tspHeldKarp(dist) {
  const n = dist.length;
  const size = 1 << n;

  const dp = Array.from(
    { length: size },
    () => Array(n).fill(Infinity)
  );

  dp[1][0] = 0;

  for (let mask = 1; mask < size; mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;
      if (dp[mask][u] === Infinity) continue;

      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;

        const nextMask = mask | (1 << v);

        dp[nextMask][v] = Math.min(
          dp[nextMask][v],
          dp[mask][u] + dist[u][v]
        );
      }
    }
  }

  const fullMask = size - 1;
  let answer = Infinity;

  for (let last = 1; last < n; last++) {
    answer = Math.min(
      answer,
      dp[fullMask][last] + dist[last][0]
    );
  }

  return answer;
}

왜 어려운가?

TSP의 최적화 버전은 NP-hard입니다. 큰 입력에서는 exact 해를 구하는 대신 Heuristic이나 전문 Solver를 사용하는 경우가 많습니다.

예:

• Nearest Neighbor
• 2-opt
• Branch and Bound
• Genetic Algorithm
• Simulated Annealing
• Ant Colony Optimization

실제 활용

• 배송 경로 최적화
• 현장 기술자 방문 순서
• 창고 로봇 이동
• 영업 담당자의 고객 방문 계획
• CNC 및 제조 공정
• PCB 생산

TSP와 VRP

고전적인 TSP는 보통 하나의 여행자와 하나의 투어를 가정합니다.

Vehicle Routing Problem은 여러 차량, 용량, 시간 창, 여러 창고 등의 제약을 추가합니다.

언제 사용하나?

한 명의 작업자가 모든 위치를 방문해야 하고 방문 순서가 중요하며 전체 이동 비용을 줄이는 것이 목표일 때 적합합니다.

정리

Brute Force는 단순하지만 O(n!) 수준으로 증가합니다. Held–Karp는 Dynamic Programming을 사용해 O(n²2^n)으로 줄이지만 여전히 지수 시간입니다. 큰 실무 문제에서는 Heuristic과 Routing Solver가 중요합니다.