Simulated Annealing
(marathon/simulated-annealing.hpp)

• View this file on GitHub
• Last update: 2023-08-10 13:25:59+09:00
• Include: #include "marathon/simulated-annealing.hpp"

テンプレート

using score_t = double;
struct Input {
  Input() = default;
  void scan() {}
};
struct State {
  struct Diff {
    const State *st;
    Diff() = default;
    Diff(const State &state) : st(&state) {}
    double diff() const {}
  };

  State() = default;
  State(const Input &input) {}
  void update(const Diff &b) {}
  void undo(const Diff &) {}
  score_t score() const {}
  bool operator>(const State &s) { return score() > s.score(); };
  void dump() {}
};
using SA = Simulated_Annealing<Input, State, typename State::Diff>;

Depends on

• marathon/log_table.hpp
• misc/timer.hpp

Verified with

• verify/verify-unit-test/simulated-annealing.test.cpp

Code

#pragma once

#include "../misc/timer.hpp"
#include "log_table.hpp"

template <typename Input, typename State, typename Diff>
struct Simulated_Annealing {
 private:
  log_table rand_log;
  double end_time, inv_time, cur_time;
  double start_temp, diff_temp, cur_temp;
  Timer *timer;

  void set_time(double start_time) {
    inv_time = 1.0 / (end_time - start_time);
    cur_time = start_time;
  }
  void set_temp() {
    cur_temp = max(0.0, start_temp - cur_time * diff_temp * inv_time);
  }

 public:
  Simulated_Annealing(double _end_time, double _start_temp, double _end_temp,
                      Timer *_timer = nullptr)
      : end_time(_end_time),
        start_temp(_start_temp),
        diff_temp(_start_temp - _end_temp),
        timer(_timer) {
    if (timer == nullptr) timer = new Timer;
    set_time(timer->elapsed());
    set_temp();
  }

  void reset() { timer->reset(); }

  State run(const Input &input) {
    State st(input);
    for (int iter = 0;; iter++) {
      if ((iter & 0xFF) == 0) {
        st.dump();
        if ((cur_time = timer->elapsed()) > end_time) break;
        set_temp();
      }
      Diff d(st);
      if (d.diff() > cur_temp * rand_log.l[iter & 0xFFFF]) {
        st.update(d);
      } else {
        st.undo(d);
      }
    }
    return st;
  }

  decltype(State().score()) test(const vector<string> &filenames) {
    decltype(State().score()) scores = 0.0;
    for (auto &filename : filenames) {
      timer->reset();
      ifstream is(filename);
      cin.rdbuf(is.rdbuf());
      Input input;
      input.scan();
      auto res = run(input);
      scores += res.score();
    }
    return scores;
  }
};

/**
 * @brief Simulated Annealing
 * @docs docs/marathon/simulated-annealing.md
 */

#line 2 "marathon/simulated-annealing.hpp"

#line 2 "misc/timer.hpp"

#include <chrono>
using namespace std;

struct Timer {
  chrono::high_resolution_clock::time_point st;

  Timer() { reset(); }
  void reset() { st = chrono::high_resolution_clock::now(); }

  long long elapsed() {
    auto ed = chrono::high_resolution_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(ed - st).count();
  }
  long long operator()() { return elapsed(); }
};
#line 2 "marathon/log_table.hpp"

struct log_table {
  static constexpr int M = 65536;
  static constexpr int mask = M - 1;
  double l[M];
  log_table() : l() {
    unsigned long long x = 88172645463325252ULL;
    double log_u64max = log(2) * 64;
    for (int i = 0; i < M; i++) {
      x = x ^ (x << 7);
      x = x ^ (x >> 9);
      l[i] = log(double(x)) - log_u64max;
    }
  }
  double operator()(int i) const { return l[i & mask]; }
};
#line 5 "marathon/simulated-annealing.hpp"

template <typename Input, typename State, typename Diff>
struct Simulated_Annealing {
 private:
  log_table rand_log;
  double end_time, inv_time, cur_time;
  double start_temp, diff_temp, cur_temp;
  Timer *timer;

  void set_time(double start_time) {
    inv_time = 1.0 / (end_time - start_time);
    cur_time = start_time;
  }
  void set_temp() {
    cur_temp = max(0.0, start_temp - cur_time * diff_temp * inv_time);
  }

 public:
  Simulated_Annealing(double _end_time, double _start_temp, double _end_temp,
                      Timer *_timer = nullptr)
      : end_time(_end_time),
        start_temp(_start_temp),
        diff_temp(_start_temp - _end_temp),
        timer(_timer) {
    if (timer == nullptr) timer = new Timer;
    set_time(timer->elapsed());
    set_temp();
  }

  void reset() { timer->reset(); }

  State run(const Input &input) {
    State st(input);
    for (int iter = 0;; iter++) {
      if ((iter & 0xFF) == 0) {
        st.dump();
        if ((cur_time = timer->elapsed()) > end_time) break;
        set_temp();
      }
      Diff d(st);
      if (d.diff() > cur_temp * rand_log.l[iter & 0xFFFF]) {
        st.update(d);
      } else {
        st.undo(d);
      }
    }
    return st;
  }

  decltype(State().score()) test(const vector<string> &filenames) {
    decltype(State().score()) scores = 0.0;
    for (auto &filename : filenames) {
      timer->reset();
      ifstream is(filename);
      cin.rdbuf(is.rdbuf());
      Input input;
      input.scan();
      auto res = run(input);
      scores += res.score();
    }
    return scores;
  }
};

/**
 * @brief Simulated Annealing
 * @docs docs/marathon/simulated-annealing.md
 */

Back to top page