数独を最適化問題に焼直して解いてみた。いろいろ統計力学の背景があるんだけど、方法自体は簡単なんでそういうのを一切省いても説明できる。そして応用範囲が広い。応用できる問題のタイプは、膨大な場合の数の中からある一定の条件を満たすものを見つけ出す、というもの。
条件を満たしている度合を整数のスコアで表せるとする。たとえば数独ならルールを破っているマスの数とすればいい。これが０になれば解。地図のｎ色問題であれば両側が同色の国境の数、などなど。スコアが０でなくてもなるべく小さければいい、という問題でもOK。配送経路の最短化のような場合でも、経路の長さを１００ｍ区切りにして整数にするとかで応用できる。
まずこのスコアの最大値を見積もる。これをSMAXとする。完全にめちゃくちゃな場合を選んだ場合のだいたいのスコアより少し多めにすればいい。
- 1a: 配列 double weight[SMAX+1]を用意し、全部0にしておく。
- 1b: 配置を一つ適当に選びスコアを計算する。
- 1c: double dw = 0.1;// 後で説明
- 2: 現在の配置C0を少しだけ変えた配置C1を乱数で作る。数独なら１マスだけ別の数字に変えたもの。そのスコアを計算する。
- 3: C0のスコアをS0、C1のスコアをS1とする。
- 4a: S1、S0どちらかでもSMAXより大きい場合、S1＜S0ならC1を採用、そうでなければC0のまま。2へ戻る。
- 4b: double wdif = weight[S1]-weight[S0];
- 4b: wdif ＞０ならC1を採用する。
- 4b: wdif＜０ なら確率exp(wdif)でC1を採用、1-exp(wdif)でC0のまま。wdif==0.0なら確率半々。
- 5: 現在のスコアをSとする。weight[S] -= dw;
- 6: (optional) 有る程度の回数繰り返しても解がでない場合、dw=dw*0.5
- 7: 2へもどる
数独で難しい問題の場合、数十秒で解けた。速度はたいしたことないかもしれないけど、ロジックを全く考えなくていいからすぐコーディングできるのが利点。ただし一番難しいという 17 hints てのは解けなかった。
weight は定数-Log(場合の数)に収束していく。制限なしの数独でしばらく流したところ、スコア０は場合の数が5.7e+21、スコア最大(全部同じ数字)は9.2となった。厳密な値はスコア０が約6.67e+21らしい。悪くない。
追記：
そんなうまい話はねえよ！（笑）
wikipedia:ノーフリーランチ定理
