順列全列挙によるTSP Ruby編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。

この問題に対する直感的な解法として、巡回路を全列挙するというものがあります。つまり、都市の順列を全通り試して、それぞれについて巡回路長を計算し、巡回路長が最小のものを答えとする解法です。

n 個の都市 (都市 1、都市 2、...、都市 n) のデータが与えられます。この解法で巡回セールスマン問題を解き、巡回路長と巡回路を出力してください。なお、各都市は二次元平面上の点として与えられ、都市間の距離にはユークリッド距離を用いるものとします。

正解は一通りとは限りません。巡回路が正しく、巡回路長が最小であれば正解と判定されます。
例えば入力例 1 では巡回路を 3 2 4 1 や 2 3 1 4 と出力しても正解と判定されます。

入力される値

n
x_1 y_1
x_2 y_2
...
x_n y_n

・ 1 行目に、都市の個数 n が与えられます。
・続く n 行のうち i 行目には、都市 i の座標 (x_i, y_i) が半角スペース区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 1 行目に巡回路長の最小値を出力してください。絶対誤差が 10^-6 以下なら正解と判定されます。
2 行目に巡回路長が最小となるような巡回路を出力してください。巡回路は都市番号 (1, 2, ... , n) の順列で表し、半角スペース区切りで出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。
・入力はすべて整数
・ 2 ≦ n ≦ 8
・ -1,000 ≦ x_i, y_i ≦ 1,000 (1 ≦ i ≦ n)
・ i ≠ j ならば (x_i, y_i) ≠ (x_j, y_j)

入力例1: 4
0 0
2 2
-1 1
0 -2

出力例1: 11.048627177541
1 3 2 4

問題一覧へ戻る