[关闭]
@Junlier 2018-08-31T22:11:18.000000Z 字数 3145 阅读 2022

模拟退火学习

搜索——模拟退火

引入

对于一些题目,无法直接算出答案或者想不到正解,想到随机找答案,那么模拟退火就是一种有系统方法的随机算法

用途

  1. 数据范围不大但爆搜显然过不了的题目
  2. 有一定的求解规律但又不完全符合规律的题目
  3. 多峰函数题或者算数几何之类的题目
  4. 题目想不出,退火总比爆0好的题目

没用的不需要了解的来源

百度百科......
模拟退火算法来源于固体退火原理,是一种基于概率的算法,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

几个要记下来的东西

  1. 温度:大概理解为答案的波动范围,看是否会接受不那么好的解
  2. 爬山算法:找很多个答案起点,遇到峰值就记录答案,最后找最大(小)答案

主要思想

  • 把当前答案看成一只退火兔,一开始很急躁(温度很高),所以答案到处乱跑(这中间会记录最优解),最后兔子慢慢冷静下来(温度逐渐降低),就找到答案
  • 利用rand来寻找答案接受劣解的波动范围(当然T也是一个决定性参数)
  • 退火找答案之后,可能会有更优答案在自己周围很近的地方,所以rand去周围看一看是否更优
  • 一开始根据自己的猜测来找一个答案“开始”点,可以降低一定时间复杂度......

板子

我只讲大致的思想,具体实现根据模板题及luogu的题解讲述来学习吧
主要是懒

first

luogu板子题平衡点/吊打xxx
然后,我的优美代码......

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define cold 0.99
  17. #define N 1050
  18. #define RD T*((rand()<<1)-RAND_MAX)//rand一个-T到T的数,随机跳多远
  19. #define Time() (ldb)clock()/(ldb)CLOCKS_PER_SEC
  20. using namespace std;
  21. const int Inf=1e9;
  22. int n;
  23. ldb ansx,ansy,ans;
  24. ldb etlx,etly,etl;
  25. struct WEI{
  26. ldb x,y,m;
  27. }ljl[N];
  28. il int read()
  29. {
  30. rg int s=0,m=0;rg char ch=getchar();
  31. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  32. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  33. return m?-s:s;
  34. }
  35. il ldb f(rg ldb xx,rg ldb yy)
  36. {
  37. rg ldb res=0;
  38. for(rg int i=1;i<=n;++i)
  39. {
  40. rg ldb dx=xx-ljl[i].x,dy=yy-ljl[i].y;
  41. res+=sqrt(dx*dx+dy*dy)*ljl[i].m;
  42. }
  43. return res;
  44. }
  45. int main()
  46. {
  47. srand(time(NULL));
  48. n=read();
  49. for(rg int i=1;i<=n;++i)
  50. {
  51. scanf("%Lf%Lf%Lf",&ljl[i].x,&ljl[i].y,&ljl[i].m);
  52. ansx+=ljl[i].x,ansy+=ljl[i].y;
  53. }
  54. etlx=ansx=ansx/n,etly=ansy=ansy/n;
  55. etl=ans=f(ansx,ansy);
  56. while(Time()<0.3)
  57. {
  58. rg ldb nans=etl,nx=etlx,ny=etly;
  59. for(rg ldb T=1000;T>=1e-16;T*=cold)
  60. {
  61. rg ldb xx=nx+RD,yy=ny+RD;//模拟退火答案的波动范围
  62. rg ldb res=f(xx,yy);//找答案的ans
  63. if(ans>res)ans=res,ansx=xx,ansy=yy;//更新答案
  64. if(nans>res||exp((res-nans)/T)*RAND_MAX<rand())
  65. nans=res,nx=xx,ny=yy;
  66. }
  67. }
  68. printf("%.3Lf %.3Lf\n",ansx,ansy);
  69. return 0;
  70. }

second

有难度,luogu均分数据

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 25
  17. #define M 10
  18. #define Time() (ldb)clock()/(ldb)CLOCKS_PER_SEC
  19. using namespace std;
  20. const int Inf=1e5;
  21. int n,m;
  22. ldb tot,ans=Inf;
  23. ldb v[N],sum[N];
  24. ldb dp[N][N];
  25. il int read()
  26. {
  27. rg int s=0,m=0;rg char ch=getchar();
  28. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  29. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  30. return m?-s:s;
  31. }
  32. il ldb PF(rg ldb x){return x*x;}
  33. il ldb sol()
  34. {
  35. for(rg int i=1;i<=n;++i)sum[i]=sum[i-1]+v[i];
  36. for(rg int i=0;i<=n;++i)
  37. for(rg int j=0;j<=m;++j)dp[i][j]=Inf;
  38. dp[0][0]=0;
  39. for(rg int i=1;i<=n;++i)
  40. for(rg int j=1;j<=m;++j)
  41. for(rg int k=0;k<i;++k)
  42. dp[i][j]=min(dp[i][j],dp[k][j-1]+PF(sum[i]-sum[k]-tot));
  43. ans=min(ans,dp[n][m]);
  44. return dp[n][m];
  45. }
  46. il void SA(rg ldb T)
  47. {
  48. rg ldb nans=ans;
  49. for(;T>1e-3;T*=0.98)
  50. {
  51. rg int xx=1+rand()%n,yy=1+rand()%n;
  52. if(xx==yy)continue;
  53. swap(v[xx],v[yy]);
  54. rg ldb res=sol();
  55. if(res<nans||exp((res-nans)/T)*rand()-RAND_MAX<0)nans=res;
  56. else swap(v[xx],v[yy]);
  57. }
  58. }
  59. int main()
  60. {
  61. n=read(),m=read();
  62. for(rg int i=1;i<=n;++i)
  63. v[i]=read(),tot+=v[i];
  64. tot/=m,sol();
  65. while(Time()<0.3)
  66. SA(1000);
  67. printf("%.2Lf\n",sqrt(ans/m));
  68. return 0;
  69. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注