TCO 16 Round2 が終了しました。
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16703&pm=14268
問題文
ある宇宙空間にN個の星とM個の宇宙船とK個のUFOが存在しています。宇宙船は星と星の間を移動する際にその星と星の間の距離の長さ分の燃料を消費します。
宇宙船は移動する際に、UFOと一緒に移動した場合は消費燃料が0.001倍になります。（UFOが複数ある場合は効果が重複されます）あなたは「全ての星を1回訪れるような宇宙船の移動計画を立てる」のが目的となります。使用する燃料が最小となるように計画を立ててください。
TSP問題（巡回セールスマン問題）がベースとなっている問題でした。（宇宙船 1でUFO 0の場合とか完全にTSPです）
戦略
自分の今回の戦略についてです。
1ターン目
1ターン目は全宇宙船に対して停止命令を出します。というのも1ターン目は星の到達判定が発生しないので、宇宙船の初期位置が訪問済みと認定されないためです
追跡するUFOを決める
今回の問題では通常移動とUFOと一緒に行動する時の燃料の消費差が1000倍あるので、基本的にはUFOと一緒に行動します。ただUFOに乗り込むタイミングが結講難しくて、その辺り苦労しました（最後もここでずっと悩んでました）。というのも UFOに乗り込むのに通常コストで燃料を消費 しないといけないので「なるべく早く乗り込みたい。。。でも距離が遠い。。。」みたいなところでトレードオフをうまく調整する必要があったからです。（あとは1つのUFOに乗る宇宙船は1台にしてました）
消費コストを考えると乗りにくい
かと言って、待ちすぎると今度は到達できる星の数が減ってしまう
自分の場合はUFOと宇宙船の遭遇率を考えてその辺りは調整しました。（例えば宇宙船1つでUFO1つのケースなら遭遇率は低いので、乗り込む閾値を高く設定、一方、宇宙船10個のUFO20個のケースであれば遭遇率は高いはずなので乗り込む閾値を低くする）
この辺りは若干、過学習させた感はあるので本番スコア下がるかも。。。
UFOを追跡する
追跡するUFOを決めたら「残り時間 - 未到達星 > 0」の間ずっとUFOを追跡します。
経路を作成する
最後に残った星を訪問する経路を作成します、自分の場合は宇宙船が1つの時と2つ以上ある場合で経路の作成方法を分けています。経路の作成には「初期解の構成」+ 「山登り法 or 焼きなまし法」を使用しました
初期経路の構成
まずは初期経路を生成します。初期経路の生成には「NN法 (Nearest Neighbor)」と「FI法 (Farthest Insertion)」の2つを使用しました（今回は制限時間が長かったので両方試してスコアが良いほうを選択しています）。個人的にNN法のほうが後半の焼きなましの時に改善しやすく、FI法は初期の精度は良いが焼きなましで改善しにくい印象を受けました。
NN法 (Nearest Neighbor)
NN法では以下の手順で経路が作成されます
1. 未到達の星の中からランダムで1つを選択
1が選択されたと仮定
2. 選択された星から一番近い星を求める
2番が選択される
3. その星に移動
1-2の経路が作成される
4. 未到達の星がなくなるまで2-3を繰り返す
こんな感じで経路を作成していきます。NN法では終盤にかなり効率の悪い経路を作成する傾向があります
FI法(Farthest Insertion)
FI法では以下の手順で経路を作成していきます
1. 既に作成している経路から一番遠い未到達の星を選択
ここでは既に1-3の経路が完成しているものとします
現在完成している経路から一番遠い星を選択します
ちなみにここで逆に一番近い星を選択するとNI法（Nearest Insertion）になります。
2. コストが最小となるように星を挿入
星を選択後、経路「A -> B」に挿入するとして「A -> C -> B」、この時のコスト「AC + CB - AB」が一番最小となる場所に挿入を行います
3. 未到達の星がなくなるまで1-2を繰り返します
4を追加
最後に2を追加して終了
FI法ではNN法に比べ、精度の高い経路が生成されます。（特に星の数が1000を超えてくると顕著です）
宇宙船が1つのとき
初期の経路の生成後、以下の操作を近傍と定義し焼きなましを行いました。
1. ある2点間の星の訪問順番を交換する
ランダムで経路から2点を選び交換します
2点をランダムで選択
交換する
2. 交差している経路が存在する場合に、交差部分を取り除く
下のような経路が存在している場合に
以下の2点を選択したとします（実際にはランダムで選択しています）
選択した星からスタートして、交換処理ができなくなるまで交換し続けます
処理が完了すると交差していた部分が解消されます
3. 経路から任意の場所を抜き出して、任意の場所に入れなおす
経路の中からランダムから1つ選択します
2が選ばれた場合
切り離して
ランダムで選択された場所に挿入します（図は4-5の間が選択された場合）
宇宙船が2つ以上の場合
初期経路の生成後、以下の操作を行った後にコストが減少した場合に経路の更新を行いました（山登り）
1. 任意の宇宙船の経路が交差していた場合にこれを取り除く
2. 任意の宇宙船の訪問経路から2点を選び、これを入れ替える
3. 任意の宇宙船の経路を反転する
4. ある宇宙船の経路の一部を切り取り、それを別の宇宙船の経路の最後に追加する
5. ある宇宙船の経路の一部を切り取り、それを別の宇宙船の経理の先頭に追加する
その他
他にも細かく調整したポイントについて
UFOの乗り換え
UFO追跡中に時折、他のUFOと重なるタイミングがあります。この時に重なったUFOが無人でかつ平均移動距離が今のUFOより長い場合はそこで乗り換えを行いました。（平均移動距離が長いと星の到達率が高くなる傾向があるので）、特に宇宙船が1つのケースではスコアの上昇が顕著でした。
一時離脱
UFOの行動は2ターン先まで与えられているのですが、たまにUFOが行って戻ってくる時があります。この時は次の訪問地が到達済みの場合にUFOから下りてました。（0.001倍になっていてもチリも積もればなんとやら）
2が到達済みならばUFOが戻ってくるまで1で待機しておく
離れすぎた宇宙船の回収
自分は1つのUFOに対して1つの宇宙船を乗せていましたが、宇宙船の数 > UFOの数のケースにおいて、UFOに乗れない宇宙船が出てきました。このケースだと、一定ターン経つと 周りに未到達の星が全く無い 状態が発生します。
この状態は後で星を探索する際に不利なので 、近くにUFOが来たらそれに乗っかり未到達星の近くまで移動します。
近くにUFOが来る
それに乗っかる（他の宇宙船が乗っていても関係なし）
未到達の星がある近くまで移動する
UFOから下りて再度停止モード
Examples
Example scores:
0) 2063.911340486327
1) 7700.186086852073
2) 4577.47499473865
3) 2367.5522684008797
4) 8787.464703717615
5) 5524.8693553478615
6) 8296.651085271313
7) 4765.360580919411
8) 6927.3815665480315
9) 12032.230311687837
