焼きなまし法ライブラリ2

以前公開していた焼きなましライブラリが古くなったので、新しく公開します。

そして、以前の記事を編集しようとしたところ、誤って削除してしまいました。もとには戻せないようです・・・。

typedef long long ll;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()

#ifdef _MSC_VER
#include <Windows.h>
ll getTime() {
    return GetTickCount();
}
#else
#include <sys/time.h>
ll getTime() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    ll result =  tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
    //cerr << result << endl;
    return result;
}
#endif

// http://www.jstatsoft.org/v08/i14/xorshift.pdf
unsigned int xor128() {     // 周期は 2^128-1
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned long t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

//TODO:状態を表す型/構造体を作成する
class STATE {
public:
    //TODO:コンストラクタに必要な引数を追加する
    explicit STATE();
    void next();
    void prev();
    double energy();
private:
};

class SimulatedAnnealing {
public:
    //TODO:コンストラクタに必要な引数を追加する
    SimulatedAnnealing();
    STATE run();
private:
    static const int TIME_LIMIT;
    double calculateProbability(double score, double scoreNeighbor, double temperature);
};

//TODO:コンストラクタに必要な引数を追加する
SimulatedAnnealing::SimulatedAnnealing() {
}

//TODO:計算時間をミリ秒単位で設定する
const int SimulatedAnnealing::TIME_LIMIT = 9900;

STATE SimulatedAnnealing::run() {
    const ll timeStart = getTime();
    const ll timeEnd = timeStart + TIME_LIMIT;
    STATE state;
    double energy = state.energy();
    STATE result = state;
    double minEnergy = energy;
    int counter = 0;
    ll timeCurrent;
    while ((timeCurrent = getTime()) < timeEnd){
		REP(loop, 100) {
			state.next();
			const double energyNeighbor = state.energy();
			const double random = xor128() * 0.00000000023283064365386962890625;
			const double probability = calculateProbability(energy, energyNeighbor, (double)(timeEnd - timeCurrent) / (double)(timeEnd - timeStart) + 1e-8);
			if (random < probability){
				//Accept
				if (minEnergy > energyNeighbor) {
#ifdef _MSC_VER
					fprintf(stderr, "minEnergy updated! %.5lf -> %.5lf\n", minEnergy, energyNeighbor);
#endif
					minEnergy = energyNeighbor;
					result = state;
				}
				//fprintf(stderr, "Accepted %.5lf -> %.5lf : minEnergy=%.5lf\n", energy, energyNeighbor, minEnergy);
				energy = energyNeighbor;
			} else {
				//Decline
				state.prev();
				//fprintf(stderr, "Declined\n");
			}
			++counter;
		}
    }
    fprintf(stderr, "counter:%d minEnergy:%.5lf\n", counter, minEnergy);
    return result;
}

double SimulatedAnnealing::calculateProbability(double energy, double energyNeighbor, double temperature) {
	if (energyNeighbor < energy) {
		return 1;
	} else {
		const double result = exp((energy - energyNeighbor) * 0.5) * temperature;
		//fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result);
		return result;
	}
}

//TODO:初期状態を作る関数を記述する
STATE::STATE() {
}

//TODO:遷移後の状態を作る関数を記述する
void STATE::next() {
}

//TODO:遷移前の状態を作る関数を記述する
//     高々一つ前の状態までに戻れれば良い
void STATE::prev() {
}

//TODO:状態のエネルギーを計算する関数を記述する
//     状態はエネルギーの低い所に遷移する点に注意する
double STATE::energy() {
}

追記

2010 TCO Marathon Round 2 で変更した部分を適用しました