bzoj2428:[HAOI2006]均分数据(模拟退火)

Author Avatar
Sakits 3月 28, 2018

题解

  好久没写模拟退火了,顺便总结一下…
  模拟退火算法是一种随机化算法,来源于物理学的固体退火原理。
  当物体的温度很高的时候,分子活动较剧烈,随着温度逐渐降低,粒子趋于有序。
  扯了那么多,实际上就是设定一个初始温度,每循环一次温度下降一些,温度高时随机到劣的地方跳过去的几率较大,而温度低的时候趋于稳定,几率就小,这样就有可能打破爬山算法只能得到局部最优解的局限性了。
  对于这道题,每次选择一个数随机到其他的组,温度高的时候应找和最小的组跳,这样比较优,而温度低的时候已经趋于稳定了,直接随机一个点跳就好。
  大概模拟退火的过程是:
    11.设定初始状态和初始温度TT,温度衰减速度(例如0.9)
    22.温度TT降低
    33.进行随机,若新答案比旧答案更优,则转移过去。否则随机一个值xx,如果x<Tx<T,那么把旧答案更新为新答案。
    44.若T<epsT<eps,则退出,否则回到22

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=50, inf=1e9;
int n, m;
double ave, ANS;
int a[maxn], pos[maxn], sum[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void sa()
{
	memset(sum, 0, sizeof(sum));
	for(int i=1;i<=n;i++) pos[i]=1+rand()%m, sum[pos[i]]+=a[i];
	double ans=0;
	for(int i=1;i<=m;i++) ans+=(sum[i]-ave)*(sum[i]-ave);
	double T=10000;
	while(T>0.1)
	{
		T*=0.9;
		int x=1+rand()%n, nxt=0;
		if(T>500)
		{
			sum[nxt]=inf;
			for(int i=1;i<=m;i++) if(sum[i]<sum[nxt]) nxt=i;
		}
		else nxt=1+rand()%m;
		if(x==nxt) continue;
		double tmp=ans;
		ans-=(sum[pos[x]]-ave)*(sum[pos[x]]-ave);
		ans-=(sum[nxt]-ave)*(sum[nxt]-ave);
		sum[pos[x]]-=a[x]; sum[nxt]+=a[x];
		ans+=(sum[pos[x]]-ave)*(sum[pos[x]]-ave);
		ans+=(sum[nxt]-ave)*(sum[nxt]-ave);
		if(ans<=tmp || rand()%10000<T) pos[x]=nxt;
		else sum[pos[x]]+=a[x], sum[nxt]-=a[x], ans=tmp;
	}
	ANS=min(ANS, ans);
}
int main()
{
	srand(23333333);
	read(n); read(m);
	for(int i=1;i<=n;i++) read(a[i]), ave+=a[i];
	ave/=m; ANS=1e100;
	for(int i=1;i<=10000;i++) sa();
	printf("%.2lf\n", sqrt(ANS/m));
}