ローカル最適化コードに３行足してグローバル最適化に

http://q.hatena.ne.jp/1317373518
たとえば20人が5卓使ってマージャンを5半荘やる。同じ人と二回以上当たらないことは可能か？
これを二回以上卓を囲むペアの数を評価関数として最小値を求める問題として解いてみる。
まず適当な席順からスタート。第S会戦の卓g1のi1番の人と卓g2(!=g1)のi2番の人を入れ替えて、評価関数がどう変わるか調べる。
局所最適解は、評価関数が減るなら実際に入れ替え、そうでなければ入れ替えない、というのを繰り返せば到達できる。
メインループ

while(1)
{
    int s;
    for(s=0;s<5;s++)
    {
        //ランダムに卓２つと２人を選ぶ
        get_shuffle(&g1, &g2, &i1,&i2);
        //入れ替えた場合の評価関数の変化を計算
        int de=eval_excchange(s, g1,g2,i1,i2);
        if(de<0)
        {
            accept_exchange(s,g1,g2,i1,i2);
            score_now += de;
        }
    }
}

コード全体はこちらhttp://d.hatena.ne.jp/ita/00010421/p1

Wang-Landauアルゴリズムでは、評価関数の値がある範囲で均等な確率で出るように学習していく。評価関数が良くなったり悪くなったりランダムウォークするようになり、いろいろな局所最適解を訪れることになる。
昔これをクラス化したので、上のコードに3行足せば使えるようにしてある。

// 追加：ヘッダ
#include "wl.h"

//  追加：評価関数の範囲を指定し初期化。最小値は0(これ以下にはならないから)。最大値は始めに適当に作った配置の値(かなり悪い値)。
WangLandau wl(0, e_init);

while(1)
{
    int s;
    for(s=0;s<5;s++)
    {
        get_shuffle(&g1, &g2, &i1,&i2);
        int de=eval_excchange(s, g1,g2,i1,i2);
        // 変更：採用の判断を Wang-Landauで行いつつ学習
        if (wl.Accept(score_now, score_now+de))
        {
            accept_exchange(s,g1,g2,i1,i2);
            score_now += de;
        }
    }
}

クラスのソースはこちらhttp://d.hatena.ne.jp/ita/20100216/p1
評価関数は整数のみ（負でもいい）。メモリは範囲に比例。計算時間は筋のいい問題ならだいたい範囲の二乗に比例。
評価関数が実数なら、(int)(dscore*1000)とかで代用できると思う。