問題
提出コード
https://gist.github.com/siman-man/bc6e0deb94d8498716e9118f52e00826
戦略
- 各人について「どのキノコを回収してどのタイミングで小屋に戻るのか」について焼きなましを使って最適化を行う
キノコの回収順番の最適化
各人についてどのキノコをどの順番で回収してどのタイミングで小屋に戻るのかを求めていきます。持っている情報としては「キノコを訪れる順番」と「このキノコを回収したら小屋に戻るフラグ」の2つを管理しています。
コード的には int 型を 16bit, 16bit で分割して前半を「小屋に戻るフラグ」後半を「どこのキノコを回収するか」にして管理しています。
どの小屋に戻るのか
キノコを回収していく中でどの小屋に戻るべきかを決める必要がありますが、これは「今回収しているキノコの場所」と「次に回収するキノコの場所」の 2つがわかれば最適な小屋の場所が確定します。
上記の画像でキノコを 1 -> 2 の順番で集めているとします。
この時、キノコ1 を回収した段階で小屋に帰ろうとした場合候補として小屋 1、小屋 2の２つがありますが、このケースでは次に回収するキノコが 2なので「キノコ 1 -> 小屋 1 -> キノコ 2」と「キノコ 1 -> 小屋 2 -> キノコ 2」の距離を調べて短い方を選べば良いです。
これをすべてのキノコの組み合わせについて調べることでその都度調べなくても、小屋に戻るときの最適な小屋の位置を決定することが出来ます。
回収したキノコが最後のキノコの場合は一番近い小屋に戻ればよいのでそれも事前に計算しておきます。
焼きなましによる最適化
各人の回収経路を焼きなましによって最適化を行っていきます。スコア計算については差分計算などは行っておらず毎回変更があった人に対して再計算を行っています。
近傍は 5つあります。
1. 訪問順の移動
任意の 1箇所を選択して別の場所に移動させます。
2. 小屋に戻るフラグの切り替え
任意の 1箇所を選択して「小屋に戻るフラグ」が有効なら無効化し、無効なら有効化にします。
3. 探索経路の反転
任意の範囲を選択してその部分の経路を反転させます。
4. 探索箇所の交換
任意の人 A, B を選んで、さらに任意の探索位置 i, j を選択した後に path[A][i] とpath[B][j] の値を入れ替えます。
5. 探索箇所の移動
任意の人 A, B を選んで、さらに任意の探索位置 i, j を選択した後に path[A][i] の値を path[B][j] の位置に挿入します。
この焼きなましを制限時間が来るまで実行します。
感想
久々にTSP系統の問題が出たなという印象。スコア計算部分を高速化できればもう少しスコアは上がると思うけどかなり複雑なので良い高速化案が思い浮かばず終了した。今回のMMでは新規参加者が多かったけど、提出の難しさとサンプルコードのバグでほとんどの提出が失敗に終わっていた。ただ、1人続けて改善を続けてた人がいたので少し感動してしまった。今後も継続してヒューリスティックコンテストに参加してくれると嬉しい。
