Topcoder Marathon KnightsAndPawns
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&pm=14994
焼きなましに飽きた1点をのぞけば、おもしろい問題だったと思います。
方針
- 空のボードにナイトをごく少数ランダムに配置して初期状態とする。
- ナイト数を固定してペナルティ最小化の焼きなまし(SA)をする。近傍はナイト1つの移動だけで追加や削除はしない。
- ペナが0つまりvalidな状態に到達したら、ベストを更新して、その状態にナイトを1つランダムに追加して2に戻る。
例えば、
ナイト数100のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数101のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数102のvalidな状態をSAで求める…
これを時間いっぱい繰り返します。
この方針の優位性
方針に悩んだので、とりあえずナイト数とvalidが存在するかどうかの関係性を洗いました。雑なSAで調べました。それによると、あるX以下のナイト数はすべてvalidをつくれて、Xより大きいナイト数はすべてvalidをつくれないという綺麗な感じに分かれました。また、Xのvalidな最適解はわりと高速に求まったので、これは最適解を拾えるケースはきっちり拾えないと死にそうという印象になりました。(最終方針だとケースの半分強で最適解と思われるものが安定して出る)
これらを元に前述の方針を立てました。
メリット
- ナイト数を1つずつ増やしながらvalid解を求めていくので、時間に余裕があれば安定して最適解が出る
- SAのスコアが単なるペナなのでペナ方向のランダムウォークは理想的に行われる
デメリット
- ナイト数を1つずつ増やしながらvalid解を求めていくので、収束が遅い。ですが、valid解にナイトを1つ追加した解つまりペナがとても少ない解からSAをはじめることでこのデメリットはかなり軽減される。
- ナイト数を固定しているので、ナイト数方向のランダムウォークは皆無
他にもいくつか考えましたが、この方針が強そうだったので採用しました。
方針の続き
前述の方針そのままにさらに工夫を足します。
近傍を絞る
近傍はナイトを1つ動かす。ですが、ランダムなナイトをランダムな空きマスに動かすのではなく、
- invalidなナイトをランダムな空きマスに動かす。
- 攻撃されすぎなナイトを攻撃しているナイトを、ランダムな空きマスに動かす。
- 攻撃されなさすぎなナイトを攻撃できる空きマスに、ランダムなナイトを動かす。
の3種類に絞ります。いずれもあるナイトのinvalidを解消する近傍です(たいていは別のマスにinvalidが移るだけですが)。SAはこのようなたとえスコアが下がっても部分的に改善する近傍だけが必要かつ十分なようで、それ以外の近傍を削ることが重要かつ頻出です。状態内のinvalidなナイトはとても少ないのでものすごい削られます。
毎試行必ず遷移するSA
普通のSAは近傍をランダムに選んで受理されたら遷移するので、試行回数×受理確率=遷移回数がパフォーマンスの目安になります。もし受理確率を100%にできたらもともとの受理確率が1%だとしたら100倍の高速化になります。今回の問題はこれができます(別途処理を追加するので10倍くらいの高速化(うろ覚え
このテク、過去のKnightsAttacksというコンテストで使ったのでそのときのツイートを流用します。(別にKnightがらみでなくてもこのテクは使ええます)
あるマスをflipしたことによってスコア変化量が変わる他の近傍は33種類しかないので高速に"すべての近傍のスコア変化量"を追従できる
— hakomo (@hakomof) September 2, 2017
黒をflipしたときに変化するattackが赤でその赤を共有するマスが青で33種類 pic.twitter.com/6vMJvlYoZc
— hakomo (@hakomof) September 2, 2017
今回は黒赤青すべてのマスが変化するので41種類
スコアの変化量は-8から+8の17通りしかないので近傍はスコア変化量ごとのqueueに詰めておけば、更新O(1)、ランダムセレクトO(17)
— hakomo (@hakomof) September 2, 2017
今回は-16から+16の31通り
過去のコンテストのツイートバリバリ流用できるのほんと草生える
多スタート
局所にはまることはあるのでボードが小さいときは2回スタート
Example scores
Example scores: 0) 15.0 1) 1293.0 2) 3391.0 3) 1444.0 4) 1869.0 5) 173.0 6) 1415.0 7) 261.0 8) 230.0 9) 1499.0