模拟退火入门题*3

左手的ㄟ右手 2021-11-05 00:58 219阅读 0赞

CTS2019Day2T1出了道可以乱搞的的计算几何，我辛辛苦苦写了280多行，结果就给了我10分，这不气炸了。  
据我分析，可能是因为我没有学过模拟退火，乱搞是真的乱搞，儿切既没有经验也没有感觉：比如随机前20个最优性合并。  
所以我就决定先把模拟退火学了。  
  
这东西特别好理解，但是原理我是真的搞不懂，凭啥这样就行，而且关于接受为啥是\\(e ^ \{\\frac\{\\Delta f\}\{T\}\}\\)，就更说不清了。  
大体来讲，就是随机范围从最大开始不断缩小，如果当前随机的解比最优解优，那必定更新；否则有概率接受这个决策，而这个概率就是上面的那个式子。由此可见，这个概率还受温度影响，温度越低，接受的概率越小。  
然后每一次随机后，\\(T = T \* Delta\\)，\\(Delta\\)我一般取值0.97~0.999左右，然后到\\(T < eps\\)的时候退出，\\(eps\\)一般取\\(1e-14\\)吧。  
接下来看几道入门题吧。  
  
**[\[JSOI2004\]平衡点 / 吊打XXX][JSOI2004_ _ _XXX]**  
这道题大概就是模拟退火的经典题。  
首先平衡点肯定是一个点，使\\(\\sum dis(i, x) \* w\_i\\)最小（用力矩分析一下就差不多了这不是物理课）。  
我们先在平衡点的基础上随机一个点，然后算上面那个值，如果比答案小，平衡点就更新为这个点；否则当前点有概率是这个点。这么搞好多次，结果就越来越接近了。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> #include<ctime> #include<assert.h> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-14; const int maxn = 1e3 + 5; const db DELTA = 0.994; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } In void MYFILE() { #ifndef mrclr freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif } int n; struct Node { db x, y; int w; friend In db dis(Node A, Node B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)); } }p[maxn]; db ansx, ansy, ans = 1e18; In db Rand(db T) {return (rand() * 2 - RAND_MAX) * T;} In db calc(db x, db y) { Node t = (Node){x, y, 0}; db ret = 0; for(int i = 1; i <= n; ++i) ret += dis(t, p[i]) * p[i].w; return ret; } In void HIAHIA() { db T = 1900; while(T > eps) { db nx = ansx + Rand(T), ny = ansy + Rand(T); db nans = calc(nx, ny), del = nans - ans; if(del < 0) { ansx = nx, ansy = ny; ans = nans; } else if(exp(-del / T) * RAND_MAX > rand()) //把RAND_MAX除过来，就是一个0~1的数 ansx = nx, ansy = ny; T *= DELTA; } } int main() { //MYFILE(); n = read(); srand(time(0)); for(int i = 1; i <= n; ++i) p[i].x = read(), p[i].y = read(), p[i].w = read(); for(int T = 1; T <= 30; ++T) HIAHIA(); //跑30次，提高准确率 printf("%.3lf %.3lf\n", ansx, ansy); return 0; }

**[\[HAOI2006\]均分数据][HAOI2006]**  
这题就更有意思了。  
一个直观的想法就是我们让每一组数据尽量平均，但如果直接贪心的话肯定gg，所以我们模拟退火随机交换两个数，再贪心看解是否更优。  
另一种做法是直接`random_shuffle`几次，每次贪心或dp求出最优解。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> #include<assert.h> #include<ctime> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-14; const int maxn = 25; const db DELTA = 0.997; In ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans; } In void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } In void MYFILE() { #ifndef mrclr freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif } int n, m, a[maxn]; db ans = INF, ave; In db TIME() {return (db)clock() / CLOCKS_PER_SEC;} int b[maxn], c[maxn]; In db calc() { Mem(c, 0); for(int i = 1; i <= n; ++i) { int pos = 1; for(int j = 2; j <= m; ++j) if(c[j] < c[pos]) pos = j; c[pos] += b[i]; } db ret = 0; for(int i = 1; i <= m; ++i) ret += (1.0 * c[i] - ave) * (1.0 * c[i] - ave); ret = sqrt(ret / m); return ret; } In void HIA() { db T = 1000; while(T > eps) { int x = rand() % n + 1, y = rand() % n + 1; while(y == x) y = rand() % n + 1; swap(b[x], b[y]); db tp = calc(), del = tp - ans; if(del < 0) ans = tp; else if(exp(-del / T) * RAND_MAX > rand()) swap(b[x], b[y]); T *= DELTA; } } int main() { //MYFILE(); srand(19260817); n = read(), m = read(); for(int i = 1; i <= n; ++i) a[i] = read(), ave += a[i]; ave /= m; ans = calc(); while(TIME() < 0.8) { for(int i = 1; i <= n; ++i) b[i] = a[i]; HIA(); } printf("%.2lf\n", ans); return 0; }

**[luogu P2210 Haywire][]**  
这题和上一题一样，模拟退火随机交换两个数。  
然后我们可以一直让程序跑到快超时为止。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> #include<assert.h> #include<ctime> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-14; const int maxn = 15; const db DELTA = 0.997; In ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans; } In void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } In void MYFILE() { #ifndef mrclr freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif } int n, t[maxn][3], a[maxn]; int ans = 0; In db TIME() {return 1.0 * clock() / CLOCKS_PER_SEC;} In int calc() { int ret = 0; for(int i = 1; i <= n; ++i) ret = ret + abs(a[i] - a[t[i][0]]) + abs(a[i] - a[t[i][1]]) + abs(a[i] - a[t[i][2]]); return ret >> 1; } In void HIA() { db T = 1000; while(T > eps) { int x = rand() % n + 1, y = rand() % n + 1; while(x == y) y = rand() % n + 1; swap(a[x], a[y]); int tp = calc(), del = tp - ans; if(del < 0) ans = tp; else if(exp(-del / T) * RAND_MAX > rand()) swap(a[x], a[y]); T *= DELTA; } } int main() { //MYFILE(); srand(19260817); n = read(); for(int i = 1; i <= n; ++i) t[i][0] = read(), t[i][1] = read(), t[i][2] = read(); for(int i = 1; i <= n; ++i) a[i] = i; ans = calc(); while(TIME() < 0.8) { for(int i = 1; i <= n; ++i) a[i] = i; HIA(); } write(ans), enter; return 0; }

转载于:https://www.cnblogs.com/mrclr/p/10878572.html

[JSOI2004_ _ _XXX]: https://www.luogu.org/problemnew/show/P1337
[HAOI2006]: https://www.luogu.org/problemnew/show/P2503
[luogu P2210 Haywire]: https://www.luogu.org/problemnew/show/P2210