模拟退火

当前有一个温度,在当前状态做出某个移动之后如果有更优解的话则总是接受这个移动,如果会更差则以一定概率接受这个移动,这个概率随机表示,且随着温度的降低而降低。每做完一次移动则降低温度,直到最低温度为止。

费马点问题

poj2420,给定平面上$n$个点,求一个点到所有点距离之和最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
const double T=100.0;
const double eps=1e-8,dw=0.99;
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
struct point{
int x,y;
point(int x=0,int y=0): x(x),y(y) {}
};
int n;
point p[maxn];
double dist(point A,point B){return sqrt((double)(A.x-B.x)*(A.x-B.x)+(double)(A.y-B.y)*(A.y-B.y));}
double allsum(point idx)
{
double ret=0;
for(int i=1;i<=n;i++) ret+=dist(idx,p[i]);
return ret;
}
double ans=1e60;
void dfs()
{
point s=p[1],nx;
double t=T;
while(t>eps)
{
bool can=true;
while(can)
{
can=false;
for(int i=0;i<4;i++){
nx.x=s.x+dx[i],nx.y=s.y+dy[i];
double res=allsum(nx);
if(res<ans) ans=res,can=true,s=nx;
}
}
t=t*dw;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
ans=1e60;
dfs();
printf("%.0lf\n",ans);
return 0;
}

最小包含球问题

poj2069,给定三维空间的n点,找出一个半径最小的球把这些点全部包围住。最小圆覆盖问题的多一维的样子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int maxn=30+5;
struct point{
double x,y,z;
};
point p[maxn];
int n;
const double eps=1e-6,dw=0.99;
double ans=1e60;
double dist(point A,point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)+(A.z-B.z)*(A.z-B.z));}
void dfs()
{
point s=p[1];
double res=0,T=100;
while(T>eps)
{
int pos=1;
for(int i=1;i<=n;i++){
if(dist(p[i],s)>dist(p[pos],s)) pos=i,res=dist(p[i],s);
}
ans=min(ans,res);
//以一定的概率接受这个移动,概率随温度降低而降低
s.x+=(p[pos].x-s.x)*T/res;
s.y+=(p[pos].y-s.y)*T/res;
s.z+=(p[pos].z-s.z)*T/res;
T*=dw;
}
}
int main()
{
while(scanf("%d",&n)==1)
{
if(n==0) break;
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
ans=1e60;
dfs();
printf("%.5lf\n",ans);
}
return 0;
}

函数最值问题

hdu2899,已知$F(x) = 6 x^7+8x^6+7x^3+5x^2-yx (0 \leq x \leq 100) $,告诉你$y$,求$x \in [0,100] $里这个函数的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-8,dw=0.99;
double ans=1e60;
int tim;
double Y;
double x[10];
int myabs(int x){return x<0?-x:x;}
int range(int l,int r){return myabs(rand())%(r-l+1)+l;}
double dbrand(){return ((rand()&1)?-1:1)*(double)rand()/RAND_MAX;}
double F(double x) {return 6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-Y*x;}
void RandPre(){for(int i=0;i<10;i++) x[i]=dbrand();}
void Fire()
{
double T=100;
while(T>eps)
{
for(int i=0;i<10;i++)
{
double tmp=F(x[i]),nx=x[i]+dbrand()*T;
if(nx>-eps && nx-100.0<eps){
double ntmp=F(nx);
if(ntmp<tmp) x[i]=nx;
}
}
T*=dw;
}
for(int i=0;i<10;i++) ans=min(ans,F(x[i]));
}
int main()
{
srand((unsigned)time(NULL));
scanf("%d",&tim);
for(int z=0;z<tim;z++)
{
scanf("%lf",&Y);
RandPre();
ans=1e60;
Fire();
printf("%.4lf\n",ans);
}
return 0;
}