sa

ソースコード

  1#include <vector>
  2#include <cmath>
  3#include "titan_cpplib/ahc/timer.cpp"
  4#include "titan_cpplib/algorithm/random.cpp"
  5#include "titan_cpplib/others/print.cpp"
  6
  7using namespace std;
  8
  9// sa 最小化
 10namespace titan23 {
 11
 12namespace sa {
 13
 14struct Param {
 15    double start_temp, end_temp;
 16};
 17
 18Param param;
 19titan23::Random sa_random;
 20using ScoreType = double;
 21
 22struct Changed {
 23    int type;
 24    ScoreType pre_score;
 25    Changed() {}
 26};
 27
 28Changed changed;
 29
 30class State {
 31    public:
 32    ScoreType score;
 33    State() {}
 34
 35    void init() {}
 36
 37    ScoreType get_score() const { return score; }
 38    ScoreType get_true_score() const { return score; }
 39
 40    // thresholdを超えたら、だめ
 41    void modify(const ScoreType threshold) {}
 42
 43    void rollback() {}
 44
 45    void advance() {}
 46
 47    void print() const {}
 48};
 49
 50// TIME_LIMIT: ms
 51State sa_run(const double TIME_LIMIT, const bool verbose = false) {
 52    titan23::Timer sa_timer;
 53
 54    // const double START_TEMP = param.start_temp;
 55    // const double END_TEMP   = param.end_temp;
 56    const double START_TEMP = 1000;
 57    const double END_TEMP   = 1;
 58    const double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT;
 59
 60    State ans;
 61    ans.init();
 62    State best_ans = ans;
 63    ScoreType score = ans.get_score();
 64    ScoreType best_score = score;
 65    double now_time;
 66
 67    int cnt = 0;
 68    int bst_cnt = 0;
 69    int upd_cnt = 0;
 70    while (true) {
 71        // if ((cnt & 31) == 0) now_time = sa_timer.elapsed();
 72        now_time = sa_timer.elapsed();
 73        if (now_time > TIME_LIMIT) break;
 74        ++cnt;
 75        ScoreType threshold = score - (START_TEMP-TEMP_VAL*now_time) * log(sa_random.random());
 76        changed.pre_score = ans.score;
 77        ans.modify(threshold);
 78        ScoreType new_score = ans.get_score();
 79        if (new_score <= threshold) {
 80            ++upd_cnt;
 81            ans.advance();
 82            score = new_score;
 83            if (score < best_score) {
 84                bst_cnt++;
 85                best_score = score;
 86                best_ans = ans;
 87                if (verbose) {
 88                    cerr << "Info: score=" << best_score << endl;
 89                }
 90            }
 91        } else {
 92            ans.score = changed.pre_score;
 93            ans.rollback();
 94        }
 95    }
 96    if (verbose) {
 97        cerr << "Info: bst=" << bst_cnt << endl;
 98        cerr << "Info: upd=" << upd_cnt << endl;
 99        cerr << "Info: cnt=" << cnt << endl;
100    }
101    return best_ans;
102}
103}
104}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/ahc/sa.cpp