一、模拟退火

步骤：

①选定一个初始状态和一个初始温度（变化幅度）T

②在T的范围内随机变化坐标

③计算新解与当前解的差△T'

④如果新解比当前解优（△T'>0），用新解替换当前解；

 否则以exp(△T'/T)的概率接受新解

⑤温度乘上一个小于1的系数，即降温

⑥如果温度小于一个给定值（精度）则退出，否则回到步骤②

BZOJ3680：模拟退火裸题

#include<cstdio>
#include<cmath>
#include<cstdlib>
#define N 11111
using namespace std;
int n,i;
double ansx,ansy,nowx,nowy,dis,nx,ny,T,now,x[N],y[N],w[N];
double Rand(){return (double)(rand()%20000)/20000.0;}
double dist(double xx,double yy){
	now=0;
	for(int i=1;i<=n;i++)now+=sqrt((xx-x[i])*(xx-x[i])+(yy-y[i])*(yy-y[i]))*w[i];
	if(now<dis)dis=now,ansx=xx,ansy=yy;
	return now;
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%lf%lf%lf",&x[i],&y[i],&w[i]),ansx+=x[i],ansy+=y[i];
	ansx/=(double)n;ansy/=(double)n;T=100000;//变化幅度
	nowx=ansx=nowy=ansy;//初始位置
	dis=dist(ansx,ansy);//当前最优解
	while(T>0.001){
		nx=nowx;ny=nowy;
		nx=nx+T*(Rand()*2-1);
		ny=ny+T*(Rand()*2-1);//在当前位置的变化幅度内随机取一点
		now=dist(nowx,nowy)-dist(nx,ny);//计算当前解
		if(now>0||exp(now/T)>rand()){//如果当前解比最优解好那么取为当前解，否则以exp|当前解-最优解|/T的概率接受当前解
			nowx=nx;
			nowy=ny;
		}
		T*=0.98;//降低搜索范围（降温）
	}
	printf("%.3lf %.3lf",ansx,ansy);
}

BZOJ2428：神奇的模拟退火

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 11111
using namespace std;
double miv=1e30,ave=0;
int n,m,a[N],sum[N],belong[N];
void SA(){
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)sum[belong[i]=rand()%m+1]+=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){
        int t=rand()%n+1,x=belong[t],y;
        if(T>500)y=min_element(sum+1,sum+m+1)-sum;
        else y=rand()%m+1;
        if(x==y) continue;
        double tmp=ans;
        tmp-=(sum[x]-ave)*(sum[x]-ave);
        tmp-=(sum[y]-ave)*(sum[y]-ave);
        sum[x]-=a[t],sum[y]+=a[t];
        tmp+=(sum[x]-ave)*(sum[x]-ave);
        tmp+=(sum[y]-ave)*(sum[y]-ave);
        if(tmp<=ans)belong[t]=y,ans=tmp;
        else if(rand()%10000>T)sum[x]+=a[t],sum[y]-=a[t];
        else belong[t]=y,ans=tmp;
        T*=0.9;
	}
    if(ans<miv) miv=ans;
}
int main(){
    srand(12345678);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),ave+=a[i];
    ave/=(double)m;
    for(int i=1;i<=10000;i++) SA();
    printf("%.2lf\n",sqrt(miv/m));
}

二、A*/IDA*

这两个神奇的算法一直都不会，今天上午听刘老师讲课稍微听懂了一点，下午又看到一道A*的题，做抄了一下，感觉好神奇啊

#include<cstdio>
#include<iostream>
using namespace std;
int ans[5][5]={{1,1,1,1,1},
    {0,1,1,1,1},
    {0,0,2,1,1},
    {0,0,0,0,1},
    {0,0,0,0,0}};
int xx[8]={1,1,-1,-1,2,2,-2,-2};
int yy[8]={2,-2,2,-2,1,-1,1,-1};
int T,i,j,x,y,k,a[5][5];
bool flag;
char ch[9];
bool judge(int a[5][5]){
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			if(a[i][j]!=ans[i][j])return 0;
	return 1;
}
bool ok(int a[5][5],int s){
	int v=0;
	for(int i=0;i<5;i++)	
		for(int j=0;j<5;j++)
			if(a[i][j]!=ans[i][j]){v++;if(v+s>k)return 0;}
	return 1;
}
void search(int s,int a[5][5],int x,int y){
	if(s==k){if(judge(a))flag=1;return;}
	if(flag)return;
	for(int i=0;i<8;i++){
		int nowx=x+xx[i],nowy=y+yy[i];
        if(nowx<0||nowx>4||nowy<0||nowy>4)continue;
        swap(a[x][y],a[nowx][nowy]);
        if(ok(a,s))search(s+1,a,nowx,nowy);
        swap(a[x][y],a[nowx][nowy]);
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		flag=0;
		for(i=0;i<5;i++){
			scanf("%s",ch);
			for(j=0;j<5;j++){
				if(ch[j]=='*')a[i][j]=2,x=i,y=j;
				else a[i][j]=ch[j]-'0';
			}
		}
		for(k=1;k<=15;k++){
			search(0,a,x,y);
			if(flag){printf("%d\n",k);break;}
		}
		if(!flag)puts("-1");
	}
}

• 相关文章推荐
• 全局相关文章