MM119参加記
MM119に参加しました。
他の人と方針が違うようなので書きます。
URL
https://www.topcoder.com/challenges/30134026
問題概要
グリッド上にR台ロボットがある。各ロボットにはそれぞれT個のtargetマスが存在する。各ロボットごとにすべてのtargetを最低一回ずつ通るような最短パスを計算した時の総長を最大化するように壁マスを配置せよ
考えたこと
残り二日での参加だったので、実装が楽で失敗しなさそうな方法を選ぶように考えた。最初は単純にSAを考えたが、スコア計算が重いので回数が稼げるかわからないし、良い近傍を見つけるのが難しいと思った。やってみてダメだった時に再実装する時間があるかもわからないし、他の方法を考えた。実際のところSAでやってる人は多く、別にSAでもよかったっぽい。
実装が簡単な構築をパラメタライズして山登りするやつをやった。
dfs
開始targetと各マスの優先度を設定する。開始targetを起点にdfsする。
dfsで通ったところは白で塗る。白マスの連結成分はunion findで管理する。新しい白マスができるたびに、各隣接マスに対しそのマスを白マスにしたときサイクルができるなら黒で塗る、という操作を行う。サイクルの判定はUFを使って高速にできる（連結成分に含まれるtargetの集合をビットマスクで持って、隣接白マスのマスクがdistinctかを調べればよい）。隣接マスの未確定マスのうち、優先度の高いマスを選んで進む。
スコア計算
愚直にやるとそこそこ時間がかかるが、木とみなすことでTSPを線形時間で解くことが出来る。（全域木中の辺の数×２- startからtargetまでの最長距離）
山登り
dfsにおいて、開始targetとマスの優先度がパラメータとなっている。
開始targetは後述する多スタートに任せるとして、優先度を探索する。近傍は適当なサイズのサブグリッドを取って、その中でswapを数回行うことで生成する。
優先度の初期値は任意の順列から一様ランダムとした。外側の優先度を高くしたほうが最初は良い解は得やすいのだが、山登りを繰り返したときより良い解にたどり着くのは一様ランダムだった。この逆転はTLを9秒として初めて判明した。
多スタート
山登りを複数行う。開始targetはこの時点でランダムに決める。並列に探索させて、successive halvingで枝刈りを行う。最初128個持っておき、3のべき乗ステップ終わるごとに下位半分を消す。
考察
この解法はマスの塗り方を直接探索するわけではないので、全域性が欠けており、偏った領域を探索しているといえる。そのため小さいケースでも最適解を見落としがちだと思われる（実際seed1でも最適解は出ない）。この問題は探索空間に対して探索数が少ないので、そもそも最適解を狙いに行くようなタイプではないのでなんとかなってる。
探索の結果を見るとわかるように、ほぼ全体で一つのパスとなるような解が出力されている。ほんとはstartから各targetまでが等距離になっているのが理想なのだが、アルゴリズム上仕方ない。
このままハイパラ調整をすれば1位は狙えそうだが、偏った領域を探索しているなどの理由から究極的に強い解法でもないと思っている。
感想
ここ最近の問題の中でも特に面白い問題だったと思う。問題設定に無理がなく、いろんな強い解法があったと思う。
今回は時間がなかったのでそんなに深いところまで考察はできず、多スタートとか外側の部分を使ってごり押したという感じ。暫定4位は解法ガチャ引き当てた感がある
