■ [MM]Marathon Match 56 
焼きなまし→高速化 しか(能|脳)がない僕
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13964&pm=10655
正方形の領域内にN（50<=N<=1000）個の点がある。全部の点を覆うようにM（10<=M<=max(10,N/10)）個の円を配置する。円の合計面積を最小化せよ。
解法
自明解+α
L=sqrt(M)として、領域の縦横をL等分してL*Lのブロックに分ける。各ブロック内で最小包含円を計算して置く、という自明解で提出。
29000点で真ん中くらい。
これでは円が余るので、
- 余ってるやつを最初に密度が高いところに適当に置いてから残りをL*Lに配置したり、
- L*LだけじゃなくてL*(L+1)も試したり、
- 複数の円に重複して含まれている点を片方だけに属させて最小包含円を再計算させたり、
とやってみたけどあまり上がらず。
この時点で33000点くらい、上位は42000点くらい。大差。どうしよう。
焼きなまし
なんかしらランダム性入れて逐次的に改善していくようなアルゴリズムにしないととは思うものの、うまくいきそうな方針が浮かばない。
とりあえずというつもりで、とても単純な戦略の焼きなましをやってみたら結構伸びたw
- N個の点からM箇所選び、円の中心の候補点とする
- N個の点それぞれに対し、一番近い円の中心を探してその円に属させる
- それぞれの円に対して最小包含円を求めて面積を計算
- 焼きなましスケジューリングに従って状態遷移
- 円を1つ選んで、その中心をランダムな位置に移動させる
- 2に戻る
これで40000点、10位台。
高速化
最初の実装はだいぶナイーブなので高速化しました。
- 点の集合から最小包含円を求めるとき、凸包だけを計算の対象にする
- 最小包含円を求めるアルゴリズムは反復法（http://www.ipsj.or.jp/07editj/promenade/4309.pdf）を使ったのだけど、
紹介されている方法そのままでは精度が良すぎるので反復回数を減らして収束の条件も緩く - 一度計算した最小包含円はキャッシュする
- 点ごとにどの円に属するかの再計算は、円の移動によって影響があったものだけを調べる
これらで数十倍速くなって、焼きなましの反復が1万回程度しかできなかったのが、10万～数百万回いけるようになりました。
Top10に到達。
わるあがき
この段階でTopとは4%差くらいある一方、今の方針ではどんなに焼きなましのチューニングを極めてもあと1.5%くらいしか上がらなさそうだと判明…
きっと改善の余地があるのは、点をどの円に属するか振り分けるとき単純に一番近い円に属するのが良いと決めつけてるところなので、
隣接している円から点を奪うような状態遷移も導入してみました。しかし効果はみられず。
あと、よく最適解から遠い局所解にはまるので、一定期間極小値を更新しなかったらむりやり円をいくつか移動させて局所解から抜け出せるようにしました。
これはほんのわずかだけ効果あり。
けど結局このフェーズではほとんど改善できず、Top10は守れませんでした。
チューニングする時間があまりなかったというのもありますが。
撃墜
自作テストケースをサブミットできたので作りました。なかなか面白い試みだと思います。
自分が確実に満点を取れて、うっかりさんをRuntime errorで落とせるかもしれないもの、ということで、
点がたくさん同じ位置に重なって、縮退を除くとM個しか存在しないケースを提出しておきました。
ずいぶん安直ですがその程度しか浮かばなかった。
結果
- 暫定順位 12/220
