http://www.gsic.titech.ac.jp/supercon/supercon2006/honsen-final.pdf
問題の要約：N個の物をいくつかのグループに分ける。N×Nの整数のテーブルMijがあり、-1から8までの値。i番目とj番目の物が違うグループにいると Mijのコストを損する（Mij = -1 の場合は得する）。 コストの合計を小さくするグループ分けを見つけよ。
単純な Simulated Annealing は以下のようにすればいい
- 現在の状態と、少し違う状態の間でコストの差Δを計算する
- Δ＜０なら新しい状態に無条件で移行。Δ＞０なら確率 exp(-βΔ)で移行。βはある実数。
- 始めに戻る
βは小さい値で始めてだんだん大きくしていく。Δは整数なんで exp のテーブルを計算しておく。
βを増やすペースと、新しい状態をどう作るかがポイント。
http://en.wikipedia.org/wiki/Simulated_annealing
追記
おっと、C2=Σδ(Si,Sj)と書けるから、全コストは原点を移動すればΣδ(Si,Sj)(1-Mij)と書ける。純粋な平均場Potts Glass だ。Si はi番目のコンピュータが属しているグループの番号。δは Cっぽく書くと #define δ(x,y) (x==y)?1:0
Si の局所最適解は
を各xについて計算し最小になるxを次のSiの値として採用すればいい。アニーリングするときは
の確率で x を選ぶ熱浴法がよさげ。これらの量を毎回O(1)で計算する工夫が必要になりそうだ。
これはやっぱりアニーリングしかないでしょうという問題かも。
追記
この辺のプレプリが役に立ちそう。ネットワークって流行のネタだからいろいろあるなぁ。
http://www.arxiv.org/find/cond-mat/1/au:+Reichardt_J/0/1/0/all/0/1
高校生は cond-mat 読まないだろうなぁ^^;
追記
ちょいと熱浴方で作ってみた。h_i の計算がどうやってもオーダーNになってしまい、これが一番重い。expの計算より重い。ほんの２行のループなんだが。それで -O 付けると三倍くらい速くなるけど、コンテストは最適化なしなんだよな。うーん。-O ありで 2GHz のマシンでは 20000 MC Step が１０分くらい。高校生の記録はこれで楽勝で抜けるが、きくちさんの記録は出せなかった。
エネルギーの履歴を見ると、6回くらい相転位が起きてそのたびに乱れたまま残っているスピンのうち約半分が秩序化する。あーそうか、行列をああしてこうして作ってノイズ付加して並びをシャッフルすれば問題の行列ができるな。ノイズ付加しすぎて Glassy になちゃったんだろうな。
ソース
追記
前のは Q=16 でやってたけど、Q=6 が最適っぽい。β=0.02〜1.0 で等比増加、熱浴 30000 step で10分。これで 4447860 が出ました。Metropolis だと低温での棄却率が高くなるので熱浴方のほうが有利なのかも。きくちさんの並列化はいろんなQのを同時にやる方法なので、計算量はたぶん同等。
同じ範囲を300000 ステップだと1.5時間。4447811 まで下がりました。各クラスタのサイズは 1707 837 337 91 23 5
