MM92 Lighting 参加録
Marathon Match 92の「Lighting」に参加していました。
問題
SxS のセル状空間に光源の強さがDのL個のライトをいい感じに設置して、なるべくたくさんの空間を照らしましょう。
すごいシンプルでした。美術館問題に似た問題だなと思いました。
方針
大きく分けて次の3つを行いました。
- フィールドの拡大率をいい感じに決める
- 焼きなましで照明を設置する場所を決める
- 焼きなまし後にフィールドの拡大率をさらに上げて照明の位置を微調整する
フィールドの拡大率をいい感じに決める
最初に与えられたフィールドをそのまま使うと照明のシミュレーションの精度が粗いので、フィールドをある程度引き伸ばして精度を高めました。テスターの実装では拡大率が f = 100 で定義されていましたが、これをそのまま使うと後の焼きなましパートで試行回数が全然稼げないので、フィールドサイズが「縦 x 横 == 10000」ぐらいになるように値を修正しました。
SCALE = ceil(sqrt(10000 / (S * S))); // 端数は切り上げ
焼きなましで照明を設置する場所を決める
遷移は「照明を1つ選び任意の場所に移動させる（※ただし壁は除く）」を採用し、温度管理は「差分スコア / (任意の定数) * (残り時間)」で管理してました。
1つのセルを16分割して細かく移動出来るようにしています。
↓
高速化
一度照明のシミュレーションをした座標については「照らすことが出来るセルの位置情報」をキャッシュして、次回以降はそれを取り出すようにしました。
照明の位置を微調整
焼きなましパートで照明の位置を決めた後に位置を微調整を行いました。処理的には任意の照明を1つ選んでちょっとだけ動かしてスコアが改善していたら採用という感じで山登り的に行いました。シミュレーションの精度を上げるために事前にフィールドを焼きなましパートのときより少し拡大しています。
それぞれのパートの時間の割り振りは
- 焼きなまし(15秒)
- 微調整(5秒)
としました。
感想
0.1%のスコア範囲で争ったのは初めてかもしれない。みんな大体同じ戦略になってそう。
Example scores: 0) 0.9987473684210526 1) 0.8922939051918736 2) 0.7014297413793104 3) 0.382128527607362 4) 0.15465865921787708 5) 0.13367932926829268 6) 0.98818025477707 7) 0.9328539007092198 8) 0.7149500729927007 9) 0.7206551724137931
