問題
方針
- 機械は連結を維持する、ただし序盤は非連結をある程度許容する
- 野菜の「出現位置」「出現時間」を元にヒートマップを作成してそれを元に機械の配置を決めていく
- 探索で使用しているパラメータを変化させながらシミュレーションを複数回実行して一番良い結果を得られたものを採用する
ヒートマップの作成
探索の際に「どの位置に機械を配置するか」「どの野菜を回収するか」を決定するためにシミュレーション実行前に作成を行う。 作成方法については実際の出現時間を変更して早めに野菜が出現しているような状態を表現しました。
例えば出現時間が 7 ~ 9 の野菜に対して 4 ~ 9 のように出現時間を早めています。
こうすることで、まだ出現していない野菜に対しても事前に機械を先置き出来るようになります。
収穫する野菜の決定
収穫する野菜について
- 野菜の価値
- 周辺のヒートマップの値の合計値
- 野菜消失までの時間
- 野菜までの距離
の 4つの要素から決定しました。 コードとして色々なパラメータが絡んでいるので説明し辛いのですが、基本的には「価値 / 距離」をベースにそこから消失までの残り時間を見て、収穫を後回しにしても良いかどうかを評価値に含んでいる感じです。
収穫する野菜までの経路作成
収穫する野菜を決定したら、その野菜をスタート地点としてダイクストラでヒートマップの価値が高い順に探索していき経路を作成しました、ただし経路自体は最短経路になるようにしています。（スタートからの距離のコストを高くしている）
機械の移動
経路を作成後、機械の移動を行います。移動の際には連結を崩さないように移動しても連結が崩れない機械を探索します。この部分については特に難しいことはしておらず、素直にその機械を実際に消して連結状態が維持されているかどうかを再帰探索で調べています。
移動可能な機械を列挙する
列挙後、移動可能な機械の中でヒートマップの値が一番小さいものを移動させます。（ヒートマップの値が高い場合はその後そこに野菜が来る可能性があるのでなるべくその位置に機械を配置するようにする）
この作業を目標の野菜に到達するまで繰り返します。
例外
移動に関して、目標の野菜までの距離が現在の機械の数よりも大きい場合は連結を解除して野菜を収穫しに行きます。
シミュレーションを複数回実行
このシミュレーションを時間制限いっぱい、探索に使用しているパラメータを変化させながらシミュレーションを複数回実行して、その中で一番良い結果が得られたものを採用しています。主に変化させたパラメータとしては以下になります。
- 購入する機械の数
- 消失までの残り時間の重み
- 周辺のヒートマップの重み
- ヒートマップ作成時の野菜の出現時間をどれだけ早めるか
動作状況
実際どんな感じで動いているかのキャプチャです
