외판원 문제: 모든 방문 순서를 비교하고 출발점으로 돌아오기

별도 패키지는 필요하지 않습니다. Node.js가 처음이라면 브라우저와 Node.js 시작 안내부터 확인하세요.

tsp-backtracking.mjs 파일을 만들고 아래 전체 코드를 저장합니다.

function checkCosts(costs, start, limit) {
  if (!Array.isArray(costs) || costs.length < 1 || costs.length > limit) {
    throw new RangeError('허용 범위 안의 정사각 비용 행렬이 필요합니다.');
  }
  const n = costs.length;
  if (!Number.isInteger(start) || start < 0 || start >= n) throw new RangeError('출발점 범위 오류');
  for (const row of costs) {
    if (!Array.isArray(row) || row.length !== n) throw new RangeError('정사각 행렬이 아닙니다.');
    for (const value of row) {
      if (value !== null && (!Number.isInteger(value) || value < 0 || value > 1000000)) {
        throw new RangeError('비용은 null 또는 0 이상 1000000 이하의 정수입니다.');
      }
    }
  }
}

function tspBrute(costs, start = 0) {
  checkCosts(costs, start, 9);
  const n = costs.length;
  if (n === 1) return { cost: 0, route: [start, start] };
  const visited = Array(n).fill(false);
  const path = [start];
  visited[start] = true;
  let best = Infinity;
  let bestRoute = [];
  function search(city, accumulated) {
    if (path.length === n) {
      const back = costs[city][start];
      if (back !== null && accumulated + back < best) {
        best = accumulated + back;
        bestRoute = [...path, start];
      }
      return;
    }
    for (let next = 0; next < n; next++) {
      if (visited[next] || costs[city][next] === null) continue;
      visited[next] = true; path.push(next);
      search(next, accumulated + costs[city][next]);
      path.pop(); visited[next] = false;
    }
  }
  search(start, 0);
  return { cost: best, route: bestRoute };
}

const costs = [[null, 2, 9, null], [1, null, 6, 4], [null, 7, null, 8], [6, 3, null, null]];
console.log(JSON.stringify(tspBrute(costs)));

파일이 있는 폴더의 터미널에서 실행합니다.

node tsp-backtracking.mjs

기대 출력

{"cost":21,"route":[0,2,3,1,0]}