最近学了一波模拟退火。个人感觉，就是随机算法，然后我们的目标点，一开始温度T高的时候会移动的剧烈，T小的时候移动的缓和（所以这就是为什么每一次移动的距离都是乘T）。然后真正的模拟退火是如果当前的tem比ans优，那就毫不犹豫地接受，否则则以一定概率接受。也就是那个exp（dE/T）> rand 那个。
然后还有爬山算法，就是只会一直找更优解，不接受差解，具体就是在模拟退火基础上，一直找最优解，找不到就降温（所以会陷入局部最优解的坑）。在网上嫖了一份代码（https://blog.csdn.net/just_sort/article/details/51648958）
1 while(t>eps) 2 { 3 bool fuck = 1; 4 while(fuck) 5 { 6 fuck = 0; 7 for(int i=0; i<4; i++) 8 { 9 z.x = s.x+dir[i][0]*t; 10 z.y = s.y+dir[i][1]*t; 11 double tmp = getSum(p,n,z); 12 if(ans>tmp) 13 { 14 ans = tmp; 15 s = z; 16 fuck= 1; 17 } 18 } 19 } 20 t*=delta; 21 }
求费马点：poj2420
题目链接：https://vjudge.net/problem/POJ-2420
一开始就以坐标平均点作为起始点，然后移动的时候虽然可以无脑的向四周移动，但是我们可以这样看，求出每一个点和当前点的dx，dy，然后肯定是当前点朝dx和dy方向移动。这样会更好
（这个是带上一定概率接受更差解的）
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<ctime> 5 #include<algorithm> 6 using namespace std; 7 #define eps 1e-6 8 int n; 9 const int N = 109; 10 struct Point{ 11 double x,y; 12 }p[N],now; 13 double dis(Point a,Point b){ 14 return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y - b.y)); 15 } 16 double getsum(Point u){ 17 double res = 0; 18 for(int i = 1;i<=n;++i){ 19 res += dis(p[i],u); 20 } 21 return res; 22 } 23 int main(){ 24 scanf("%d",&n); 25 for(int i = 1;i<=n;++i){ 26 scanf("%lf %lf",&p[i].x,&p[i].y); 27 now.x += p[i].x; 28 now.y += p[i].y; 29 } 30 now.x /= n; now.y /= n; 31 double ans = getsum(now); 32 double T = 100; 33 srand(23333); 34 while(T > eps){ 35 double dx = 0,dy = 0; 36 for(int i = 1;i<=n;++i){ 37 dx += (p[i].x - now.x)/dis(now,p[i]); 38 dy += (p[i].y - now.y)/dis(now,p[i]); 39 } 40 Point next = (Point){now.x + dx*T, now.y + dy*T}; 41 double tem = getsum(next); 42 if(tem < ans){ 43 ans = tem; 44 now = next; 45 } 46 else if(exp( (ans - tem) / T) > (rand()%10000)/10000.0){ 47 ans = tem; 48 now = next; 49 } 50 T *= 0.98; 51 } 52 printf("%.0f",ans); 53 return 0; 54 }
最小球覆盖：poj2069
题目链接：https://vjudge.net/problem/POJ-2069
和上一题差不多，先以平均点做起始点，然后每次移动肯定是往距离当前点的最远点移动。
（这个没有接受更差解了）
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #define eps 1e-6 5 using namespace std; 6 const int N = 40; 7 int n; 8 struct Point{ 9 double x,y,z; 10 }p[N],now; 11 double dis(Point u,Point v){ 12 return sqrt( (u.x-v.x)*(u.x-v.x) + (u.y-v.y)*(u.y-v.y) + (u.z - v.z)*(u.z - v.z)); 13 } 14 int main(){ 15 while(~scanf("%d",&n) && n){ 16 for(int i = 1 ; i <= n ;++i){ 17 scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].z); 18 now.x+=p[i].x; now.y+=p[i].y; now.z += p[i].z; 19 } 20 now.x/=n; now.y/=n; now.z/=n; 21 double T = 100; 22 double ans = 1e99; 23 while(T > eps){ 24 int k = 1; 25 for(int i = 1;i <= n ;++i){ 26 if(dis(now,p[i]) > dis(now,p[k]) ){ 27 k = i; 28 } 29 } 30 double tem = dis(p[k],now); 31 ans = min(ans,tem); 32 now.x += ( (p[k].x - now.x)/tem )*T; 33 now.y += ( (p[k].y - now.y)/tem )*T; 34 now.z += ( (p[k].z - now.z)/tem )*T; 35 T *= 0.98; 36 } 37 printf("%.6f\n",ans); 38 } 39 return 0; 40 }
至于最小园覆盖，模拟退火的话和最小求覆盖一样啦。不过最小圆覆盖有线性的点增量法（下一篇讲到），所以就不妨在这里了。