题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

· · 题解

这道题作为模拟退火的板子，缘于评价函数是一个单峰函数，故模拟退火AC率较高。而在相同时间内，粒子群算法的正确率是高于模拟退火的。

但是粒子群算法有一个缺点，在后期如果陷入了局部最优，就不容易调整。

所以我们可以将粒子群算法和模拟退火结合！这样粒子有一定概率跳出当前解，从而获得更优秀的全局搜索性。

注：因为这个算法跑得还是比较快的，可以多跑几遍pso增加正确率。

update 2019/7/23 20:51：粒子初始位置随机分布确实会增加AC率，更新了代码。

code：

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define PSO_NUM 20
static int n,xx[1001],yy[1001],W[1001];
double T,w,bstans,gbx,gby,X1,Y1,r1,r2,f1,f2,dc;
struct obj{
    double x,y,vx,vy,pbx,pby,bstans;
}obs[PSO_NUM|1];
inline double F(double x,double y){
    double ans=0,dx,dy;
    for(reg int i=1;i<=n;++i)
        dx=x-xx[i],dy=y-yy[i],ans+=W[i]*sqrt(dx*dx+dy*dy);
    return ans;
}
inline void pso(){
    obs[1].x=gbx,obs[1].y=gby,obs[1].bstans=bstans;
    for(reg int i=2;i<=PSO_NUM;++i)
        obs[i].x=gbx+double((rand()<<1)-RAND_MAX)/RAND_MAX*10000,
        obs[i].y=gby+double((rand()<<1)-RAND_MAX)/RAND_MAX*10000,
        obs[i].bstans=F(obs[i].x,obs[i].y);
    for(T=1000,w=0.7;T>1e-6;T*=0.92,w=max(0.0,w-0.005))
        for(reg obj *i=obs+1,*j=obs+PSO_NUM+1;i!=j;++i)
            r1=(double)rand()/RAND_MAX,r2=(double)rand()/RAND_MAX,
            i->vx=w*i->vx+2*r1*(i->pbx-i->x)+2*r2*(gbx-i->x),
            r1=(double)rand()/RAND_MAX,r2=(double)rand()/RAND_MAX,
            i->vy=w*i->vy+2*r1*(i->pby-i->y)+2*r2*(gby-i->y),
            i->x+=i->vx,i->y+=i->vy,
            f1=F(i->x,i->y),
            f1<i->bstans&&(i->bstans=f1,i->pbx=i->x,i->pby=i->y),
            f1<bstans&&(bstans=f1,gbx=i->x,gby=i->y),
            X1=i->x+double((rand()<<1)-RAND_MAX)/RAND_MAX*T,
            Y1=i->y+double((rand()<<1)-RAND_MAX)/RAND_MAX*T,
            f2=F(X1,Y1),
            dc=f2-f1,
            dc<0?i->x=X1,i->y=Y1:(
            r1=(double)rand()/RAND_MAX,
            r1<min(1.0,exp(-dc/T))&&(i->x=X1,i->y=Y1)
            ),
            f2<i->bstans&&(i->bstans=f2,i->pbx=X1,i->pby=Y1),
            f2<bstans&&(bstans=f2,gbx=X1,gby=Y1)
            ;
}
int main(){
    srand(time(0));
    srand(rand()^rand());
    scanf("%d",&n);
    for(reg int i=1;i<=n;++i)
        scanf("%d%d%d",xx+i,yy+i,W+i),gbx+=xx[i],gby+=yy[i];
    gbx/=n,gby/=n;
    bstans=F(gbx,gby);
    pso(),pso(),pso();
    printf("%.3lf %.3lf",gbx,gby);
    return 0;
}