用語がウケた。
http://www.gsic.titech.ac.jp/supercon/supercon2007/honsen_mondai_v2.pdf
問題は、二次元版で説明すると、紙の上にランダムに点が描いてあるとき、十円玉を何枚使ってもいいから、なるべく洩れがないように点を隠すように置く問題。ギチギチいっぱいに置いたとしてもすき間があるから改善の余地がある。
高密度な剛体球の分子動力学、て感じか。シミュレーテッド・アニーリングかな。
あるいは各星に基地があるかないか、なのでスピン系に落とせるか。
Ciは星iから半径R以内にある星の数、Oij は星iと星jが距離2R 以内なら1, そうでなければ0。Kを0からだんだん無限大まで増やしつつ最小値を探す。スピン系とはいえ格子じゃないからベクトル化が面倒だ。独立に更新できる複数のセットに分割することをまずやらねば。
うーんしかし問題データを見ると干渉範囲内に一万個とか星がある。1スピンflip ごとに一万の値を参照しないといけないから、スピン系じゃきついな。基地は100個程度でいけそうだから、やっぱ剛体球MDだな。スポンジ玉を詰め込んで、だんだん玉を硬くしていけばいい。エネルギー = -覆ってる星の数 +玉同士の重なりエネルギー。
追記
Superconのキーワードたどって見ると、高校生たちが当り前のようにSA(シミュレーテッド・アニーリング)を使ってるようだ。ほげぇー。
