概述

爬山算法

爬山算法很简单,即每次从当前解的邻近解空间中选择一个最优解作为当前解,但是有可能陷入局部最优而无法到达全局最优。

Hill Climbing

如上图到达A点时搜索就会停止

模拟退火

可以理解为步长逐渐缩小的搜索,且搜索过程逐渐收敛

  1. 从当前状态开始搜索,直到所有后继状态都不优
  2. 降温(步长变小)

模板

poj2420

求费马点,求一个到所有点距离最小的点

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
50
51
52
53
54
typedef pair<double,double> Point;
#define x first
#define y second

const double eps = 1e-8; //终止温度
const double delta = 0.98; //温度衰减率 一般取 0.99/0.98
const int T = 100; //初始温度
const double INF = 1e20;
const int maxn = 110;

int n;
Point p[maxn];

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

double dist(Point A,Point B)
{
return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) );
}

double cal(Point t)
{
double ans = 0;
for(int i=0;i<n;++i) ans += dist(p[i],t);
return ans;
}

void solve()
{
Point s = p[0];
double t = T,ans = INF;
while(t > eps)
{
bool flag = 1;
while(flag)
{
flag = 0;
for(int i=0;i<4;++i)
{
Point c = make_pair(s.x+dx[i]*t,s.y+dy[i]*t);
double cur = cal(c);
if(ans > cur)
{
ans = cur;
s = c;
flag = 1;
}
}
}
t *= delta;
}
printf("%d\n",(int)(ans+0.5));
}

题目

poj2069

最小球覆盖