模擬退火學(xué)習(xí)

作業(yè)部落
網(wǎng)上講的不錯的(他好像還有一些其他的東西、、、)

引入

對于一些題目，無法直接算出答案或者想不到正解，想到隨機找答案，那么模擬退火就是一種有系統(tǒng)方法的隨機算法

沒用的不需要了解的來源

百度百科......
模擬退火算法來源于固體退火原理，是一種基于概率的算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。

幾個要記下來的東西

溫度：大概理解為答案的波動范圍，看是否會接受不那么好的解

爬山算法：找很多個答案起點，遇到峰值就記錄答案，最后找最大(小)答案

用途

數(shù)據(jù)范圍不大但爆搜顯然過不了的題目

有一定的求解規(guī)律但又不完全符合規(guī)律的題目

多峰函數(shù)題或者算數(shù)幾何之類的題目

題目想不出，退火總比爆0好的題目

主要思想

• 把當(dāng)前答案看成一只退火兔，一開始很急躁(溫度很高)，所以答案到處亂跑(這中間會記錄最優(yōu)解)，最后兔子慢慢冷靜下來(溫度逐漸降低)，就找到答案
• 利用rand來尋找答案接受劣解的波動范圍(當(dāng)然T也是一個決定性參數(shù))
• 退火找答案之后，可能會有更優(yōu)答案在自己周圍很近的地方，所以rand去周圍看一看是否更優(yōu)
• 一開始根據(jù)自己的猜測來找一個答案“開始”點，可以降低一定時間復(fù)雜度......

板子

我只講大致的思想，具體實現(xiàn)根據(jù)模板題及l(fā)uogu的題解講述來學(xué)習(xí)吧
主要是懶

first

luogu板子題平衡點/吊打xxx
然后，我的優(yōu)美代碼......

#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<iomanip> #include<algorithm> #include<ctime> #include<queue> #include<stack> #include<vector> #define rg register #define il inline #define lst long long #define ldb long double #define cold 0.99 #define N 1050 #define RD T*((rand()<<1)-RAND_MAX)//rand一個-T到T的數(shù),隨機跳多遠 #define Time() (ldb)clock()/(ldb)CLOCKS_PER_SEC using namespace std; const int Inf=1e9;int n; ldb ansx,ansy,ans; ldb etlx,etly,etl; struct WEI{ldb x,y,m; }ljl[N];il int read() {rg int s=0,m=0;rg char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return m?-s:s; }il ldb f(rg ldb xx,rg ldb yy) {rg ldb res=0;for(rg int i=1;i<=n;++i){rg ldb dx=xx-ljl[i].x,dy=yy-ljl[i].y;res+=sqrt(dx*dx+dy*dy)*ljl[i].m;}return res; }int main() {srand(time(NULL));n=read();for(rg int i=1;i<=n;++i){scanf("%Lf%Lf%Lf",&ljl[i].x,&ljl[i].y,&ljl[i].m);ansx+=ljl[i].x,ansy+=ljl[i].y;}etlx=ansx=ansx/n,etly=ansy=ansy/n;etl=ans=f(ansx,ansy);while(Time()<0.3){rg ldb nans=etl,nx=etlx,ny=etly;for(rg ldb T=1000;T>=1e-16;T*=cold){rg ldb xx=nx+RD,yy=ny+RD;//模擬退火答案的波動范圍rg ldb res=f(xx,yy);//找答案的ansif(ans>res)ans=res,ansx=xx,ansy=yy;//更新答案if(nans>res||exp((res-nans)/T)*RAND_MAX<rand())nans=res,nx=xx,ny=yy;}}printf("%.3Lf %.3Lf\n",ansx,ansy);return 0; }

second

有難度，luogu均分數(shù)據(jù)

#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<iomanip> #include<algorithm> #include<ctime> #include<queue> #include<stack> #include<vector> #define rg register #define il inline #define lst long long #define ldb long double #define N 25 #define M 10 #define Time() (ldb)clock()/(ldb)CLOCKS_PER_SEC using namespace std; const int Inf=1e5;int n,m; ldb tot,ans=Inf; ldb v[N],sum[N]; ldb dp[N][N];il int read() {rg int s=0,m=0;rg char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return m?-s:s; }il ldb PF(rg ldb x){return x*x;} il ldb sol() {for(rg int i=1;i<=n;++i)sum[i]=sum[i-1]+v[i];for(rg int i=0;i<=n;++i)for(rg int j=0;j<=m;++j)dp[i][j]=Inf;dp[0][0]=0;for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j)for(rg int k=0;k<i;++k)dp[i][j]=min(dp[i][j],dp[k][j-1]+PF(sum[i]-sum[k]-tot));ans=min(ans,dp[n][m]);return dp[n][m]; }il void SA(rg ldb T) {rg ldb nans=ans;for(;T>1e-3;T*=0.98){rg int xx=1+rand()%n,yy=1+rand()%n;if(xx==yy)continue;swap(v[xx],v[yy]);rg ldb res=sol();if(res<nans||exp((res-nans)/T)*rand()-RAND_MAX<0)nans=res;else swap(v[xx],v[yy]);} }int main() {n=read(),m=read();for(rg int i=1;i<=n;++i)v[i]=read(),tot+=v[i];tot/=m,sol();while(Time()<0.3)SA(1000);printf("%.2Lf\n",sqrt(ans/m));return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cjoierljl/p/9394519.html

總結(jié)

以上是生活随笔為你收集整理的模拟退火学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。