1. paizaラーニングトップ
  2. レベルアップ問題集
  3. 巡回セールスマン問題メニュー(言語選択)
  4. 問題一覧
  5. 2-近似によるTSP

巡回セールスマン問題メニューのサムネイル
2-近似によるTSP (paizaランク A 相当)

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

問題

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

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

ここでは、巡回セールスマン問題に対する 2-近似アルゴリズムを学習しましょう。このアルゴリズムは、最悪でも最適値の 2 倍以下の値を持つ解を出力します。

巡回セールスマン問題に対する 2-近似アルゴリズムの概要は、以下の通りです。

・ 都市をグラフの頂点とみなし、最小全域木 MST を求める
・ MST の辺を複製して二重にしたグラフを作り、一筆書きをする
・ 一筆書きにおいて訪れる都市を先頭から順に並べる。ただし既に訪れた都市には再度訪れないようにして、全都市をちょうど 1 度ずつ訪れる経路 (巡回路) を作る


n 個の都市 (都市 0、都市 1、...、都市 n-1) のデータが与えられます。この 2-近似アルゴリズムを実装し、「最適値 (巡回路長の最小値) の 2 倍」以下の巡回路長を持つ巡回路を求めてください。なお、各都市は二次元平面上の点として与えられ、都市間の距離にはユークリッド距離を用いるものとします。

正解は一通りとは限りません。巡回路が正しく、巡回路長が「最適値 (巡回路長の最小値) の 2 倍」以下であれば正解と判定されます。
例えば、出力例 1 の巡回路長は 11.877054302287245 ですが、これは最適値 11.048627177541 の 2 倍以下となっています。

入力される値

n
x_0 y_0
x_1 y_1
...
x_{n-1} y_{n-1}


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


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

「最適値 (巡回路長の最小値) の 2 倍」以下の巡回路長を持つ巡回路を出力してください。巡回路は都市番号 (0, 1, ... , n-1) の順列で表し、半角スペース区切りで出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 20
・ -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
0 -2

出力例1

3 2 0 1

問題一覧へ戻る

ページの先頭へ戻る