模拟退火，第一次做模拟退火，搞了好几天才明白原理是怎么回事，启发式算法，运行时程序不稳定，会有一定的概率性，这些启发式算法有很多共同的特点，百度百科里有对启发式算法的简单介绍，数学中国网有很多模拟退火和其他启发式算法的很多资料，主要是数学建模方面的，但是知识都是互通的，学一学也很好，http://baike.baidu.com/view/476038.htm
其实看程序就比较好理解启发式算法的思想了，但是我找了很多解题报告，发现都没有出现概率性选择并不是最优解的解决办法，有的利用了同时产生好几个点，利用并发性，这也不能算是概率性选择，还是搞不太明白怎么办。但是就这道题说还是比较简单的，确定步长，减小速度为0.9，因为精度比较低，所以就比较好办了。保存一个当前最优解集，利用随机性，步长和最优解集产生新的最优解集，最后得到的解有很大程度上不是最优解，但是对于这道题这个精度来说还是可以做到的。
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<ctime> 7 #include<cstdlib> 8 #define inf 1e50 9 using namespace std; 10 const int NUM=20; 11 const int RAD=1000; 12 struct point 13 { 14 double x,y,val; 15 point(){} 16 point(double _x,double _y) 17 { 18 x=_x; 19 y=_y; 20 } 21 }; 22 point p[10001],May[NUM],e1,e2; 23 int n; 24 double X,Y; 25 double dis(point a,point b) 26 { 27 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 28 } 29 double judge(point t)//评价函数，得到点t的评价值val 30 { 31 double len=inf; 32 for(int i=0;i<n;i++) 33 len=min(len,dis(t,p[i])); 34 return len; 35 } 36 double Rand(){return rand()%(RAD+1)/(1.0*RAD);}//随机产生0-1的浮点数 37 point Rand_point(point a,point b)//在a,b框定的四边形内随机生成点 38 { 39 double xx=a.x+(b.x-a.x)*Rand(); 40 double yy=a.y+(b.y-a.y)*Rand(); 41 point tmp=point(xx,yy); 42 tmp.val=judge(tmp); 43 return tmp; 44 } 45 void solve(double D) 46 { 47 May[0]=point(0,0); 48 May[1]=point(X,Y); 49 May[2]=point(0,Y); 50 May[3]=point(X,0); 51 //4个顶点的可能行较大，所以特殊构造 52 for(int i=4;i<NUM;i++) 53 May[i]=Rand_point(May[0],May[1]);//步骤2 54 while(D>0.01)//步骤 3 55 { 56 for(int i=0;i<NUM;i++) 57 for(int j=0;j<NUM;j++) 58 { 59 point tmp=Rand_point(point(max(0.0,May[i].x-D),max(0.0,May[i].y-D)),point(min(X,May[i].x+D),min(Y,May[i].y+D))); 60 if(tmp.val>May[i].val) 61 { 62 May[i]=tmp; 63 } 64 } 65 D*=0.9; 66 } 67 point ans; 68 ans.val=0; 69 for(int i=0;i<NUM;i++) 70 if(May[i].val>ans.val) 71 ans=May[i]; 72 printf("The safest point is (%.1f, %.1f).\n",ans.x,ans.y); 73 } 74 int main() 75 { 76 srand(time(0)); 77 e2=point(0,0); 78 int Case; 79 int i; 80 scanf("%d",&Case); 81 while(Case--) 82 { 83 scanf("%lf%lf%d",&X,&Y,&n); 84 for(i=0;i<n;i++) 85 { 86 scanf("%lf%lf",&p[i].x,&p[i].y); 87 } 88 solve(max(Y,X)); 89 } 90 return 0; 91 }