외판원 DP: 현재 도시와 방문 집합을 함께 저장하기

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

tsp-bitmask-dp.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 tspDP(costs, start = 0) {
  checkCosts(costs, start, 16);
  const n = costs.length;
  if (n === 1) return { cost: 0, route: [start, start] };
  const full = (1 << n) - 1;
  const memo = new Map();
  const choice = new Map();
  function remaining(city, mask) {
    if (mask === full) return costs[city][start] ?? Infinity;
    const key = mask * n + city;
    if (memo.has(key)) return memo.get(key);
    let best = Infinity;
    for (let next = 0; next < n; next++) {
      if ((mask & (1 << next)) !== 0 || costs[city][next] === null) continue;
      const candidate = costs[city][next] + remaining(next, mask | (1 << next));
      if (candidate < best) { best = candidate; choice.set(key, next); }
    }
    memo.set(key, best);
    return best;
  }
  let mask = 1 << start;
  let city = start;
  const cost = remaining(city, mask);
  if (!Number.isFinite(cost)) return { cost: Infinity, route: [] };
  const route = [start];
  while (mask !== full) {
    const next = choice.get(mask * n + city);
    route.push(next); mask |= 1 << next; city = next;
  }
  route.push(start);
  return { cost, route };
}

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

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

node tsp-bitmask-dp.mjs

기대 출력

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