| 1 | double curtime() { |
| 2 | return static_cast<double>(clock()) / CLOCKS_PER_SEC; } |
| 3 | int simulated_annealing(int n, double seconds) { |
| 4 | uniform_real_distribution<double> randfloat(0.0, 1.0); |
| 5 | uniform_int_distribution<int> randint(0, n - 2); |
| 6 | // random initial solution |
| 7 | vi sol(n); |
| 8 | rep(i,0,n) sol[i] = i + 1; |
| 9 | shuffle(sol.begin(), sol.end(), rng); |
| 10 | // initialize score |
| 11 | int score = 0; |
| 12 | rep(i,1,n) score += abs(sol[i] - sol[i-1]); |
| 13 | int iters = 0; |
| 14 | double T0 = 100.0, T1 = 0.001, |
| 15 | progress = 0, temp = T0, |
| 16 | starttime = curtime(); |
| 17 | while (true) { |
| 18 | if (!(iters & ((1 << 4) - 1))) { |
| 19 | progress = (curtime() - starttime) / seconds; |
| 20 | temp = T0 * pow(T1 / T0, progress); |
| 21 | if (progress > 1.0) break; } |
| 22 | // random mutation |
| 23 | int a = randint(rng); |
| 24 | // compute delta for mutation |
| 25 | int delta = 0; |
| 26 | if (a > 0) delta += abs(sol[a+1] - sol[a-1]) |
| 27 | - abs(sol[a] - sol[a-1]); |
| 28 | if (a+2 < n) delta += abs(sol[a] - sol[a+2]) |
| 29 | - abs(sol[a+1] - sol[a+2]); |
| 30 | // maybe apply mutation |
| 31 | if (delta >= 0 || randfloat(rng) < exp(delta / temp)) { |
| 32 | swap(sol[a], sol[a+1]); |
| 33 | score += delta; |
| 34 | // if (score >= target) return; |
| 35 | } |
| 36 | iters++; } |
| 37 | return score; } |
| 38 | // vim: cc=60 ts=2 sts=2 sw=2: |