最近傍法によるTSP
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。
ここでは、最近傍法と呼ばれるアルゴリズムを学習しましょう。このアルゴリズムは発見的解法 (ヒューリスティクス) と呼ばれるもので、ある程度良い解が出力されることが期待されるものの、解の精度は全く保証されません。
最近傍法の概要は、以下の通りです。
・ 始点となる都市を適当に 1 つ選ぶ
・ すべての都市を訪れるまで、以下を繰り返す
・ 今までに訪れたことのない都市のうち、今いる都市に最も近い都市を訪れる
・ 最後に始点へと戻る
n 個の都市 (都市 0、都市 1、...、都市 n-1) のデータが与えられます。この最近傍法を実装し、巡回路を求めてください。ただし、始点として都市 0 を用いてください。また、訪れたことのない都市のうち今いる都市に最も近い都市が複数存在する場合は、都市番号が一番小さい都市を次訪れる都市としてください。なお、各都市は二次元平面上の点として与えられ、都市間の距離にはユークリッド距離を用いるものとします。
答えは一意です。
- 入力される値
-
n
x_0 y_0
x_1 y_1
...
x_{n-1} y_{n-1}
・ 1 行目に都市の個数 n が与えられます。
・ 続く n 行のうち i (1 ≦ i ≦ n) 行目には、都市 i-1 の座標が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
最近傍法を用いて巡回路を求め、出力してください。出力は n 行となります。巡回路は都市番号 (0, 1, ... , n-1) の順列で表し、都市番号を先頭から順に各行に 1 つずつ出力してください。最初の都市は 0 でなければいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 4 ≦ n ≦ 5,000
・ -1,000 ≦ x_i, y_i ≦ 1,000 (0 ≦ i ≦ n-1)
・ i ≠ j ならば (x_i, y_i) ≠ (x_j, y_j)
- 入力例1
-
4
0 0
2 2
-1 1
1 -1
- 出力例1
-
0
2
3
1
