paizaラーニング レベルアップ問題集 巡回セールスマン問題メニュー JavaScript 順列全列挙によるTSP

順列全列挙によるTSP (paizaランク B 相当)

解答例(C++の場合参考)

前問までの各関数を定義し、組み合わせる。

ユークリッド距離を計算する関数定義→巡回路距離を計算する関数定義→巡回路の長さと巡回路の更新関数→順列全列挙関数

配列pを変数tourに代入するとき、連動しないように、sliceでコピーを作成。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//各都市の座標、都市の個数nは最大8
const points = Array(8).fill().map(v => v = Array(2));
let tour_length = Infinity;//巡回路長の最小値
let tour;//巡回路

//ユークリッド距離を計算する関数
function dist(a, b) {
  return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));    
} 

//巡回路距離を計算する関数
function calc_length(n, p) {
  let length = 0;
  for (let i = 0; i < n; i++) {
    length += dist(points[p[i] - 1], points[p[(i + 1) % n] - 1]);
  }
  return length;
}

//巡回路の長さと巡回路の更新をする関数
function update_tour(n, p) {
  const tmp_length = calc_length(n, p);
  if (tmp_length < tour_length) { //最小なら
    tour_length = tmp_length;//更新
    tour = p.slice();//連動しないようにslice
  }
}

//順列全列挙する関数
function permutations(n, p) {
  if (p.length == n) { //巡回路長がnになったら
    update_tour(n, p);//更新
    return;
  }

  for (let i = 1; i <= n; i++) {
    if (p.includes(i)) {
      continue;
    }
    p.push(i);
    permutations(n, p);
    p.pop();
  }
}

//メイン
//都市の個数 n
const n = Number(lines[0]);
//各都市の座標をpointsに
for (let i = 0; i < n; i++) {
  [points[i][0], points[i][1]] = lines[i + 1].split(" ").map(Number);
}

const p = [];//暫定の巡回路
permutations(n, p);//順列全列挙

console.log(tour_length.toFixed(12));//巡回路長の最小値
console.log(tour.join(" "));//巡回路

解答例(Python3の場合参考)

メインのところ、
pointsの宣言でsliceを使用、
関数permutations実行時に、p=[]の空配列を直接引数へ。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//各都市の座標、都市の個数nは最大8
const points = Array(8).fill().map(v => v = Array(2));
let tour_length = Infinity;//巡回路長の最小値
let tour;//巡回路

//ユークリッド距離を計算する関数
function dist(a, b) {
  return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));    
} 

//巡回路距離を計算する関数
function calc_length(n, p) {
  let length = 0;
  for (let i = 0; i < n; i++) {
    length += dist(points[p[i] - 1], points[p[(i + 1) % n] - 1]);
  }
  return length;
}

//巡回路の長さと巡回路の更新をする関数
function update_tour(n, p) {
  const tmp_length = calc_length(n, p);
  if (tmp_length < tour_length) { //最小なら
    tour_length = tmp_length;//更新
    tour = p.slice();//連動しないようにslice
  }
}

//順列全列挙する関数
function permutations(n, p) {
  if (p.length == n) { //巡回路長がnになったら
    update_tour(n, p);//更新
    return;
  }

  for (let i = 1; i <= n; i++) {
    if (p.includes(i)) {
      continue;
    }
    p.push(i);
    permutations(n, p);
    p.pop();
  }
}

//メイン
//都市の個数 n
const n = Number(lines[0]);
//各都市の座標をpointsに
const points = lines.slice(1, n + 1).map(line => line.split(" ").map(Number));

permutations(n, []);//順列全列挙
console.log(tour_length.toFixed(12));//巡回路長の最小値
console.log(tour.join(" "));//巡回路

解答例(経路全部求めて、その中の１つ出力)

前問までの関数を組み合わせる。
経路を全部求めて、その中の一番最初添字０を出力する方法で実装した。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//ユークリッド距離を計算する関数定義
const dist = (a, b) => {
  return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));    
}; 

//順列つくる関数
const permutations = (n, p, P) => {
  //長さnなら出力
  if (p.length == n) {
    P.push(p.slice());//連動しないようにslice
    return;//関数完了、スタックの一番上に残った関数へ戻る
  }
  //長さがn未満なら、順列つくる
  for (let i = 1; i <= n; i++) {
    //pにiがあればスキップ
    if (p.includes(i)) {
      continue;
    }
    //pにiがなければ
    p.push(i);
    permutations(n, p, P);//さらに関数実行、スタック積む
    p.pop();//１つの関数実行完了して、スタックの一番上の関数に戻ってきて末尾削除
  }
  //関数完了
};

//メイン

//都市の個数 n
const n = Number(lines[0]);
//都市 i の座標 (x_i, y_i) 
const cities = lines.slice(1, n + 1).map(line => line.split(" ").map(Number));

//最小距離
let minL = Infinity;
//最小経路
let minP = [];

//全経路
const P = [];
//経路
const p = [];

//順列全列挙
permutations(n, p, P);

//全経路の全探索
for (let h = 0; h < P.length; h++) {
  //都市番号の順列で表された巡回路
  const p = P[h].map(v => Number(v) - 1);//インデックスで扱うので-1
  //巡回路長を求める
  let l = 0;//巡回路長
  for (let i = 0; i <= n - 1; i++) {
    l += dist(cities[p[i]], cities[p[(i + 1) % n]]);//最初に戻るので%  
  }
  
  //最小更新
  if (l < minL) {
    minL = l;
    minP = [];
    minP.push(p);
  //最小同じなら  
  } else if (l === minL) {
    minP.push(p);
  }
}
console.log(minL);
console.log(minP.map(v => v.map(v => v = v + 1).join(" "))[0]);