외판원 순회 문제 (Traveling Salesman Problem, TSP)

 

문제: 한 외판원이 N개의 도시를 순회하여 각 도시를 한 번씩 방문한 뒤 다시 시작 도시로 돌아오려고 합니다. 각 도시 간의 이동 거리가 주어질 때, 최단 경로를 찾아 시작 도시로 돌아오는 최소 거리를 구하는 프로그램을 작성하세요.

입력:

• N: 도시의 수 (2 이상 10 이하의 정수)
• distance: N x N 크기의 2차원 배열로 표현된 도시 간의 이동 거리. distance[i][j]는 도시 i에서 도시 j로 이동하는데 필요한 거리를 나타냅니다. (1 이상 1,000 이하의 정수)

출력:

• 시작 도시로 돌아오는 최단 경로의 거리

제약 조건:

• 외판원은 모든 도시를 한 번씩 방문한 뒤 시작 도시로 돌아와야 합니다.
• 각 도시 간의 이동 거리는 양수입니다.
• 시작 도시와 도착 도시는 항상 동일합니다.
• 도시 간의 이동은 양방향으로 가능합니다.

코드

function tsp(graph) {
  const n = graph.length;
  const dp = new Array(n).fill(null).map(() => new Array(1 << n).fill(null));
  
  // 초기 조건 설정: 시작 도시에서 다른 도시들을 방문한 뒤 다시 시작 도시로 돌아오는 경우를 처리
  for (let i = 0; i < n; i++) {
    dp[i][1 << i] = graph[i][0];
  }
  
  // 동적 계획법을 사용하여 최단 경로 구하기
  for (let subsetSize = 2; subsetSize <= n; subsetSize++) {
    for (let subset = 0; subset < (1 << n); subset++) {
      if (countSetBits(subset) !== subsetSize || !(subset & 1)) {
        // 도시의 개수가 subsetSize가 아니거나, 시작 도시가 포함되지 않은 경우는 건너뜁니다.
        continue;
      }
      
      for (let j = 0; j < n; j++) {
        if (!(subset & (1 << j))) {
          // subset에 도시 j가 포함되지 않은 경우 건너뜁니다.
          continue;
        }
        
        dp[j][subset] = Infinity;
        
        for (let k = 0; k < n; k++) {
          if (k === j || !(subset & (1 << k))) {
            // 도시 j와 k가 동일하거나, subset에 도시 k가 포함되지 않은 경우 건너뜁니다.
            continue;
          }
          
          const prevSubset = subset ^ (1 << j);
          dp[j][subset] = Math.min(dp[j][subset], graph[j][k] + dp[k][prevSubset]);
        }
      }
    }
  }
  
  // 최단 경로 찾기
  let minDistance = Infinity;
  for (let j = 1; j < n; j++) {
    const distance = graph[j][0] + dp[0][(1 << n) - 1];
    minDistance = Math.min(minDistance, distance);
  }
  
  return minDistance;
}

// 헬퍼 함수: 정수의 이진 표현에서 1의 개수 세기
function countSetBits(num) {
  let count = 0;
  while (num > 0) {
    count += num & 1;
    num >>= 1;
  }
  return count;
}

// Example usage
const graph = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
];

const minDistance = tsp(graph);
console.log(`최단 경로의 거리: ${minDistance}`);

 

설명:

이 문제에서 1 << i는 2를 i번 왼쪽으로 시프트한 값을 나타냅니다. 이는 이진수로 표현하면 i번째 비트만 1이고 나머지 비트는 0인 수를 의미합니다.

예를 들어, i가 0일 때 1 << i는 1이 됩니다. 이는 이진수로 표현하면 0001입니다. i가 1일 때 1 << i는 2가 되고, 이진수로 표현하면 0010입니다. i가 2일 때 1 << i는 4가 되고, 이진수로 표현하면 0100입니다. 이런 식으로 i가 증가할수록 1 << i는 이진수에서 한 자리씩 왼쪽으로 이동하여 값을 2배씩 증가시킵니다.

이러한 값을 이용하여 dp 배열을 생성하는데, dp 배열은 동적 계획법을 수행하는 과정에서 부분집합의 상태를 나타내기 위한 용도로 사용됩니다. 각 행은 도시를 의미하고, 각 열은 해당 도시를 방문한 부분집합을 나타냅니다.

즉, dp[i][subset]는 도시 i를 마지막으로 방문한 후, subset에 해당하는 도시들을 모두 방문한 상태에서의 최단 경로의 길이를 나타냅니다. 따라서 부분집합의 개수에 해당하는 비트마스크를 이용하여 dp 배열의 크기를 설정해야 합니다. 1 << n을 사용하면 모든 도시의 부분집합을 표현할 수 있습니다.

그래서 dp 배열은 n을 행으로, 1 << n을 열로 가지는 2차원 배열로 생성되어 각 요소가 부분집합의 상태를 나타내도록 하여 동적 계획법을 수행할 수 있게 됩니다.

도시의 부분집합은 해당 문제에서 도시들의 집합에서 일부 도시들을 선택한 부분 집합을 말합니다.

예를 들어, 총 4개의 도시가 있다고 가정해봅시다. 이를 숫자로 표현하면 1, 2, 3, 4로 나타낼 수 있습니다. 그러면 가능한 부분집합은 다음과 같습니다:

• 공집합: {}
• 도시 1개 선택: {1}, {2}, {3}, {4}
• 도시 2개 선택: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
• 도시 3개 선택: {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
• 전체 도시 선택: {1, 2, 3, 4}

이렇게 도시들을 선택한 부분집합을 모두 고려하여 최단 경로를 계산하는 것이 동적 계획법을 사용한 외판원 문제의 핵심 아이디어입니다. 각 부분집합은 비트마스크를 사용하여 표현할 수 있으며, 이진수의 비트를 이용하여 도시의 선택 유무를 표현합니다. 예를 들어, 도시 1, 3을 선택한 부분집합은 이진수 101로 표현됩니다. 이진수의 각 비트가 1인 위치는 해당 도시가 선택되었음을 나타냅니다.

따라서 동적 계획법을 수행하기 위해 도시의 부분집합을 고려하고, 각 부분집합의 상태를 나타내기 위해 비트마스크를 사용하는 것입니다. 이를 통해 모든 가능한 도시의 선택 상태를 고려하여 최단 경로를 계산할 수 있습니다.