読者です 読者をやめる 読者になる 読者になる

simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

TCO 16 Round3参戦記録 - TerrainCrossing -

競技プログラミング

TCOMMの最終ラウンドが終わりました。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283


問題文

縦横長さが S あるフィールドがあります。フィールド上にはN個のアイテムとN個の目的地が存在しています。あなたは全てのアイテムを各目的地に運ぶ必要があります。この時、各目的地には1つのアイテムしか届けることが出来ません。(複数のアイテムを同じ目的地に置くことは不可)

フィールドの移動についてですが、現在いるセルから隣接するセルへ移動が可能です。また、各セルにはコストが割り振られており、そのセル内での移動では「移動した距離 x セルのコスト」のコストがかかります。さらにセル間の移動については以下の計算式によって追加コストが発生します。

セル(x, y) -> セル(nx, ny) への移動
addCost = pow(fieldCost[x][y] - fieldCost[nx][ny], 2)

アイテムの回収についてですが、プレイヤーがアイテムの座標から距離0.001以内のフィールドに到達すると自動的に回収されます。アイテムの保持数については上限があり、上限を超えてアイテムを保持することは出来ません。また、アイテムの設置については回収と同様に目的に0.001以内のフィールドに到達すると自動的に配置されます。アイテムを保持していない場合は設置は行われないので注意してください。

また、経路の開始地点と終了地点についてですが、開始時は任意のマップの端から0.001以内の距離にある座標から開始し終了地点も同様にマップの端から0.001以内の距離を指定してください。なお、連続している経路の間隔は0.001より大きく、かつ座標が存在しているセルのマンハッタン距離が1以下になるようにしてください。さらに始点と終点を除いた各経路の座標はセルの端から0.001より離れた場所を指定してください。

最終的にコストの消費を少なく全てのアイテムを目的地に届けて下さい。

今回の問題、細かい制約のせいでたくさんのバグを埋め込みました。 あと参加した中で一番疲れました。

戦略

今回は「各オブジェクト間のコストを計算」「巡回セールスマン問題を解く」「山登りで経路を修正」と大きく分けて3つのフェーズに分けて処理を行いました。

各オブジェクト間のコストを計算

まず最初にフィールドに散らばっている「アイテム」と「目的地」それぞれの経路間のコストを求めます。基本的には各オブジェクトからダイクストラ法で経路を生成しました。

f:id:simanman:20160706224555p:plain

なるべくコストが小さくなるように移動。

f:id:simanman:20160706225209p:plain

今回はこのコストをどう計算するかでかなり頭を悩ませました。というのも、下の図のようなフィールドが存在し

f:id:simanman:20160706231156p:plain

このフィールドを次のように移動した時に、図の経路だと「1 + 1 = 2」と計算するのですが、実際には

f:id:simanman:20160706231409p:plain

この移動が可能なので1.41ぐらいのコストにしたい、かといってこの状態でさらに右に進んだ場合

f:id:simanman:20160706231748p:plain

今度は赤線の経路が最短になり、前回時点での最短を固定してしまうとロスが発生してしまう。

f:id:simanman:20160706232113p:plain

このロスは経路を進めれば進めるほど発生するので、このロスをいかに減らすかが難しかったです。

自分は通常のコストの計算時に追加コストを通常の2倍で計算を行いました。(これは評価値としては微妙な気がしなくもないですが

また、Sが小さい場合は、1つ進める毎に今までの経路に対して後述する山登り法を適用して経路のコストをその都度再計算していました。

巡回セールスマン問題を解く

求めたオブジェクト間のコストを元に巡回セールスマン問題を解きます。経路には以下の制限をつけました

  • アイテムが0個の状態で「目的地」に到達してはいけない
  • アイテムの所持数が上限の状態で「アイテム」に到達してはいけない

巡回セールスマン問題を解いた内容については前回の予選の感想ブログで書いた内容とほぼ一緒なのでそちらをどうぞ

simanman.hatenablog.com

簡単に説明すると、現在の経路に対して以下の操作のいずれかを選択します。

  • 2点間のオブジェクトを入れ替える
  • 2点間の交差を削除する
  • 1点を取り出し任意の場所に追加する
  • 連続した2点を取り出し任意の場所に追加する

また、仮に経路のコストが増加しても一定の確率でその経路を採用します(焼きなまし法

山登りで経路を修正

最終的な経路が確定したら、経路の座標をランダムに選択し、ランダムに動かしてスコアが改善されたらそれを採用する、という処理を行いました。

この様な経路が存在している時に

f:id:simanman:20160706233252p:plain

始点と終点とアイテムと目的地を除いた座標をランダムに1つ選び動かします

f:id:simanman:20160706233859p:plain

スコアが改善された場合はそちらを採用します。

セルを飛び越える移動も有効にしています

f:id:simanman:20160706235123p:plain

f:id:simanman:20160706235132p:plain

感想

まさか同じ予選で巡回セールスマン問題を2回も出題されるとは思いませんでした。点をばらまいてそれをくっつけたり切り離したり移動させたりする案もあったのですが、時間が無くて断念しました。序盤の「オブジェクト間のコストを算出」する部分が精確に出せなかったのが心残りです。

Example

Example scores:
0) 8.106127476192645
1) 85.36355804638156
2) 384.75769417466637
3) 5627.9464135616445
4) 551.6884483017363
5) 311.8191310808154
6) 313.3568643271177
7) 921.3633059194917
8) 1493.4400096579031
9) 664.7891337391771