1344 线型网络
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamo
______________________________________________________________________________________________________________________________
题目数据范围看似很小，实际细算，肯定超时。常规方法不行。
随机了一下，结果能够过5个点。
没办法了，只好模拟退火。临时学的，更确切的说是临时抄的。
模拟退火，一种启发式搜索方法，据说是模拟物理上的退火过程而发明的。
个人理解：
爬山算法就是用贪心的方法求出局部最优解。就是说你只要只走上坡路就一定可以走到一个山顶，但不一定是珠穆朗玛峰。
而模拟退火就是从一个点试着向四周蹦，如果蹦到点比这里高，那就上去（这个好理解，总忘高处走，这就是爬山算法嘛）；如果蹦到的点比较低，则有定的概率上去。
为什么一定要接受更低的点呢？只有这样才可以从局部最优的情况中跳出来，从而试着去爬更高的山。
关键为题在于概率如何计算。也就是随着时间的推移，接受的概率要逐渐降低。
代码如下
1 bool accept(double delta,double cur) 2 { 3 if(delta<=0)return 1; //若果跳到的点更符合要求 4 return rand()<exp((-delta)/cur)*RAND_MAX;
5 //若果跳到的点更差....,cur为当前温度，它会随着时间降低（退火），RAND_MAX为最大随机整数，exp(负数)产生0-1间的实数，明白了吗？
6 }
还不明白就看大神的吧！
https://zhuanlan.zhihu.com/p/23968011
______________________________________________________________________________________________________________________________
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 int cx[21],cxf[21]; 8 double x[21],y[21],dis[21][21]; 9 double ans; 10 int n; 11 double getdis(int * s) 12 { 13 double tp=0; 14 for(int i=1;i<n;i++)tp+=dis[s[i-1]][s[i]]; 15 return tp; 16 } 17 bool accept(double delta,double cur) 18 { 19 if(delta<=0)return 1; 20 return rand()<exp((-delta)/cur)*RAND_MAX; 21 } 22 double solve() 23 { 24 double dec=0.999; 25 double tp,ttp=ans; 26 double cur=10000; 27 while(cur>0.01) 28 { 29 memcpy(cxf,cx,sizeof(cx)); 30 int a=rand()%n,b=rand()%n; 31 swap(cxf[a],cxf[b]); 32 tp=getdis(cxf); 33 if(accept(tp-ttp,cur)) 34 { 35 memcpy(cx,cxf,sizeof(cx)); 36 ttp=tp; 37 } 38 cur*=dec; 39 } 40 return ttp; 41 } 42 int main() 43 { 44 srand(2323); 45 scanf("%d",&n); 46 for(int i=0;i<n;++i) 47 scanf("%lf%lf",x+i,y+i); 48 for(int i=0;i<n;++i) 49 for(int j=0;j<i;++j) 50 { 51 dis[i][j]=dis[j][i]=hypot(x[i]-x[j],y[i]-y[j]); 52 } 53 for(int i=0;i<n;i++)cx[i]=i; 54 ans=getdis(cx); 55 int t=150; 56 while(t--) 57 { 58 ans=min(ans,solve()); 59 } 60 printf("%.2lf ",ans); 61 return 0; 62 }