문제 : TSP (travelling salesman problem)

외판원 문제(travelling salesman problem, 이하 TSP)는 아래와 같이 정의됩니다.

• 여러 도시들의 위치가 주어졌을 때, 모든 도시들을 단 한번씩 방문하는 최단 거리를 구하세요.

각 도시의 위치를 나타내는 좌표평면 위의 점들을 입력받아, TSP의 최단 거리를 리턴해야 합니다.

let placesToVisit = [
  [0, 0],
  [1, 1],
  [1, 3],
  [2, 2],
];
let output = TSP(placesToVisit);
console.log(output); // --> 423
// 방문 순서: [0, 0], [1, 1], [2, 2], [1, 3]

placesToVisit = [
  [0, 0],
  [3, 3],
  [-3, 3],
  [2, 3],
  [1, 3],
];
output = TSP(placesToVisit);
console.log(output); // --> 940
// 방문 순서: [-3, 3], [1, 3], [2, 3], [3, 3], [0, 0]

Advanced

아래 내용에 유념하여 TSP에 대해 학습해 보세요.

• TSP 처럼 모든 꼭지점을 한 번씩 지나는 경로를 해밀턴 경로(Hamiltonian path)라고 합니다.
• TSP는 조합 최적화 문제의 일종으로 NP-hard라는 것이 증명되었습니다.
• 완전탐색(exhaustive search) 외의 방법이 존재하지 않습니다.

Reference

// 좌표평면 위의 두 점 사이의 거리를 계산하는 함수입니다.
function calculateDistance(p1, p2) {
  const yDiffSquared = Math.pow(p2[0] - p1[0], 2);
  const xDiffSquared = Math.pow(p2[1] - p1[1], 2);
  const dist = Math.sqrt(yDiffSquared + xDiffSquared);
  return Math.round(dist * 100);
}

const TSP = function (places) {
  let currentMinDist = Number.MAX_VALUE;
  const LENGTH = places.length;
  function traverse(lastVisited, visited, totalDist, visitNum) {
    if (visitNum === LENGTH) {
      if (currentMinDist > totalDist) {
        currentMinDist = totalDist;
      }
      return;
    }

    visited.forEach((value, idx) => {
      if (value === false) {
        // 아직 방문하지 않은 도시와
        // 마지막으로 방문한 도시와의 거리를 구한다.
        const distToNext = calculateDistance(places[lastVisited], places[idx]);
        visited[idx] = true;
        traverse(idx, visited, totalDist + distToNext, visitNum + 1);
        visited[idx] = false;
      }
    });
  }

  // 각 도시의 현재 방문 여부를 관리하는 배열
  const visited = Array(LENGTH).fill(false);
  places.forEach((_, idx) => {
    // 각 도시에서 출발하는 경우를 구분한다.
    visited[idx] = true;
    traverse(idx, visited, 0, 1);
    visited[idx] = false;
  });

  return currentMinDist;
};