AtCoder Heuristic Contest 011(AHC011) -Sliding Tree Puzzle- 参加記
問題
結果
最終2,440,715,276 点で20位。暫定は40.6M点で21位。
解法
完成図の木を作るパートと完成図のパズルを解くパートの2つがある。
完成図の木構築
基本方針はBFSでランダムに枝を伸ばしていく。完成図は木なので、タイルを置いたらそのタイルが伸びる方向には、必ず置いたタイルから枝が伸びる。なので、別のタイルが伸びる方向が重ならないように枝刈りすることができる。例えば、下図において、マスAに左図のようにタイルを置いた場合、マスBにはAから枝が伸びる。なので、右図のようにマスCにマスBに繋がるタイルをおくことができない。
どのマスに何のタイルを置いたかを管理する配列と、伸ばす方向が重ならないように管理する配列を用意することで、木であることを保持しながらあるタイルを置けるかどうかの判定をO(1)で行える。葉のタイルはそれ以外のタイルが置けない場合にのみ置く。
以上の操作で、完成図が作れなかった場合、ランダムに1タイルを選び、そのタイルの伸びる1方向を残してその他の方向の部分木を除去し、もう一度BFSを行う。木のサイズが大きくなったら更新していく。5000イテレーションで完成しなかった場合は局所解にハマっていると判断して、一からやり直す。
パズルを解く
- 完成図と現在の配置から、マンハッタン距離をコストにして最小二部マッチングをハンガリアン法で解いて、どのタイルをどこへ移動させるかを決める。パズルとして不可能な配置の場合には、同種のタイル1ペアの移動先をスワップすることで完成可能にする。(参考:https://manabitimes.jp/math/979)
- 外周の4辺のうち、1タイルあたりのコスト(1.で計算した最小コスト)が最小の辺を次に揃える辺に決める。
- 2.で決めた辺をビームサーチで揃える。評価値は揃える辺のタイルの完成図とのマンハッタン距離。揃える辺のタイル以外は全て同一視して状態を管理する(そうしないと完成しなかった)。
- 1〜3を繰り返し行い、3x3になったらBFSで最短手順を探索する。
アルゴリズム全体
完成図は一定時間内(1,000ms〜1,500ms)でできるだけ沢山見つける(N=6で300個、N=10で10個程度見つかる)。残り時間で、マンハッタン距離のコストが小さい順に、完成図のパズルを解き、一番良い解を出力する。完成図の探索時間、ビーム幅はNごとにパラメータ調整した。
ざっくり時系列
1〜3日目
まずは木を完成させないとなぁと思い、頑張って実装する。最初のプログラムだとN=10で一つ完成図を見つけるのに5秒くらいかかったので、高速化する。
4日目
パズルを解きたいけど、ルールベースで解いても絶対にスコア伸びなさそうだし実装も重そうなので、全部を一気に揃えるビームサーチを書く。N=6は揃うこともあるけど、N=10だと全く揃わない。完成図の空きマスから遠いほどコストを高くすれば外側から上手いこと埋まっていくのでは？と思ったが、コストが低いところをぐるぐるするだけでダメ。
5〜6日目
多分、高コストのタイルを一旦悪い方向に動かす操作が行われないのがいけない。ので、1辺ずつ揃える&揃えるタイル以外は無視、で上手くいった。初提出で12位くらい。
7〜8日目
完成図を複数見つけたり、細かい調整を行う。
9日目
c4.8xlargeを借りて、大量ケースでバグチェック&パラメータ調整を行う。1000ケースに1回ぐらいSegmentation Faultするバグがあった。やっぱりチェックは大事。
その他
距離を最初にマンハッタン距離にして放置して、そこを改良するのを完全に忘れていた…。二乗和にするだけで暫定スコア40.6M→41.3Mになるという…。最終順位で言うとおそらく20位→17位になっていたはず。アホすぎる。。
