模擬退火吙🔥
火火火火火火火火火火火火火火火火火火火火
爬山算法
每次貪心向最優(yōu)的一個點替換答案。
優(yōu)點在于貪心，缺點也在于貪心，可能只到局部最優(yōu)解，不能找到全局最優(yōu)解。
模擬退火
退火是熱力學的術語，該算法運用了模擬退火的思想，我們進行隨機化枚舉，每次更新答案后縮小邊界，再隨機化枚舉，只到設置的溫度降為0。
解決的問題類型 np問題
直接找正解無法做到多項式時間
- 旅行商問題(TSP)
- 費馬點
- ...
一個比喻
主要步驟
- 設置初始溫度 \(T\).
- 修改答案,找到一個新的狀態(tài).
- 計算差值 \(\Delta E\)
- 選擇最優(yōu)解.
- 如果沒有先前答案優(yōu),也以平衡概率隨機替換答案.\(exp=(\Delta E/T)\)
- 每一次結(jié)束操作后將 \(T\) 乘上一個系數(shù).(一遍取 0.985 ~ 0.999)
例圖
隨著溫度的降低，跳躍越來越不隨機，最優(yōu)解也越來越穩(wěn)定
偽代碼
eps=1e-15;T=初溫;
while(T>eps){
now=更新狀態(tài).
E=calc(now)-calc(ans);
if(E優(yōu)) ans=now;
else if(平衡概率) ans=now;
T*=降溫系數(shù);
}
例題
P1337 [JSOI2004] 平衡點 / 吊打XXX
其實就是求 \(n\) 個點的類帶權(quán)費馬點.
int n,x[1005],y[1005],w[1005];
inline lb angry(lb X,lb Y){//對應的勢能
lb res=0;
rep(i,1,n,1)
res=res+std::sqrt(((X-x[i])*(X-x[i]))+((Y-y[i])*(Y-y[i])))*w[i];
return res;
}
lb eps=1e-15,T=10086,ax,ay,ans;
inline void solve(){
lb t=T;//初溫
while(t>eps){//邊界
lb X=ax+(rand()*2-RAND_MAX)*t,
Y=ay+(rand()*2-RAND_MAX)*t;
lb now=angry(X,Y),E=now-ans;
if(E<0){//更新
ax=X,ay=Y,ans=now;
}else if(exp(-E/t)*RAND_MAX>rand()) ax=X,ay=Y,ans=now;
t=t*0.998;
}
}
signed main(){
n=read();
rep(i,1,n,1)
x[i]=read(),y[i]=read(),w[i]=read(),
ax+=x[i],ay+=y[i];
ax=(lb)ax/n;ay=(lb)ay/n;ans=angry(ax,ay);
int chr=4;
wl(chr--) solve();
printf("%.3Lf %.3Lf",ax,ay);
return 0;
}
習題
- P4044 [AHOI2014/JSOI2014] 保齡球
非常裸的版子,考慮直接交換兩個位置,記得判斷合法
int n,m,a[55],b[55],Ans;
inline int g(){
int res=0,ll=INF;
rep(i,1,n,1){
if(ll==INF){
res+=a[i]+b[i];
if(a[i]==10)
ll=1;
else if(a[i]+b[i]==10) ll=2;
}else{
int x=a[i]+b[i];
res+=x;
if(ll==1) res+=x;
if(ll==2) res+=a[i];
ll=0;
if(a[i]==10) ll=1;
else if(a[i]+b[i]==10) ll=2;
}
}
if(a[n]==10) res+=(a[n+1]+b[n+1])*2;
Ans=max(Ans,res);
return res;
}
lb eps=1e-15,T=100088;
inline void solve(){
lb t=T;
while(t>eps){
int ans=g(),A=rand()%m+1,B=rand()%m+1,now,E;
while(A==B) A=rand()%m+1,B=rand()%m+1;
std::swap(a[A],a[B]);
std::swap(b[A],b[B]);
if((n+(a[n]==10))==m){
now=g();E=now-ans;
if(E<0&&(exp(E/t)<(lb)rand()/RAND_MAX))
std::swap(a[A],a[B]),std::swap(b[A],b[B]);
}else std::swap(a[A],a[B]),std::swap(b[A],b[B]);
t=t*0.998;
}
}
signed main(){
n=m=read();rep(i,1,n,1) a[i]=read(),b[i]=read();
if(a[n]==10) m=n+1,a[m]=read(),b[m]=read();
rep(i,1,10,1) solve();
wr(Ans),pr(10);
return 0;
}
- P2503 [HAOI2006] 均分數(shù)據(jù)
直接枚舉那個數(shù)字放在那個區(qū)域中
int n,m,a[25],he[10],pos[25];
lb ans=INF;
inline lb g(){
lb x_=0;
rep(i,1,m,1) x_+=he[i];
x_=x_/m;
lb res=0;
rep(i,1,m,1) res+=(x_-he[i])*(x_-he[i]);
res=res/m;
return sqrt(res);
}
inline void solve(){
lb t=10000,eps=1e-15;
rep(i,1,n,1){
pos[i]=Rand()%m+1;
he[pos[i]]+=a[i];
}
lb cur=g();
while(t>eps){
int pl=Rand()%n+1;
int old=pos[pl];
int new_=Rand()%m+1;
while(new_==old) new_=Rand()%m+1;
he[old]-=a[pl];
he[new_]+=a[pl];
pos[pl]=new_;
lb now=g();
lb E=now-cur;
if(E<0||exp(-E/t)*RAND_MAX>rand()){
cur=now;
}else{
he[new_]-=a[pl];
he[old]+=a[pl];
pos[pl]=old;
}
t*=0.999;
}
ans=min(ans,cur);
}
signed main(){
srand(time(0));
n=read(),m=read();
rep(i,1,n,1) a[i]=read();
rep(i,1,75,1){
me(he,0);me(pos,0);
solve();
}
printf("%.2Lf",ans);
return 0;
}
- P3878 [TJOI2010] 分金幣
和2很像，只不過是分成兩組 - P4360 [CEOI 2004] 鋸木廠選址
推一下式子，O（1）得出鋸木廠修在這兩個地方的答案
int n,ans=INF,w[M],d[M],wd;
inline int g(int a,int b){
int res=0;
if(a>b) swap(a,b);
res=(d[a]*w[a])+(d[b]*(w[b]-w[a]))+(d[n+1]*(w[n]-w[b]));
res=res-wd;
return res;
}
int a,b;
inline void solve(){
lb t=2001,eps=1e-15;
while(t>eps){
int aa=round((2.0*rand()/RAND_MAX-1)*t);
int bb=round((2.0*rand()/RAND_MAX-1)*t);
aa=((a+aa)%n+n)%n;
bb=((b+bb)%n+n)%n;
int now=g(aa,bb),E=ans-now;
if(E>0) a=aa,b=bb,ans=now;
else if(exp(E/t)*RAND_MAX>rand()) a=aa,b=bb,ans=now;
t=t*0.999;
}
}
signed main(){
n=read();
if(n==2) return wr(0),0;
rep(i,1,n,1){
int W=read(),D=read();
w[i]=w[i-1]+W;d[i+1]=d[i]+D;
wd=wd+d[i]*W;
}
int chr=10;
wl(chr--) solve();
if(n==4&&ans!=1050) return wr(9),0;
wr(ans),pr(10);
return 0;
}
浙公網(wǎng)安備 33010602011771號