算法介绍
模拟退火是一种最优化随机化算法。什么叫随机化算法？就是抽奖抽正解
一般用于求解最优解，即最优化问题，而且一般比较适合于小数据的最优解和大数据的近似最优解。
算法步骤
每次迭代都随机选择一个解，然后模拟退火得到该解的邻域最优解，如果邻域最优解比当前解更优，则接受该邻域最优解小，则更新当前解为该解。
模拟退火步骤如下：
- 先初始化温度，当前解和当前答案
- 如果温度小于最终温度，跳到第7步结束；否则跳3
- 重复执行4~5步若干次
- 由当前解生成一个临时的新解，并计算新的答案
- 判断是否接受该临时解，接受则更新解和答案，不接受则回退到上个解
- 降温，跳2
- 结束
对于差解的判断和当前温度有关，解越差我们越不想要它，接受它的概率就小一些；贪心往往会在开始的时候陷入局部最优解，我们就要在开始的时候跳出局部最优，也就是通过走向较差的解，所以开始的时候接受差解的概率要大一些；快结束的时候我们需要稳定在当前的最优解，接受差解的概率就小一些，所以我们模拟物理的退火原理，温度从高逐渐降低，对于接受差解概率的计算公式
e^(delta/T) 来说，新解答案的差异值为分子
delta，是个负数（如果正数取负就行），答案越差，delta
绝对值越大，指数越小，概率也越小；温度越低，指数越小，概率也越小，这就符合了我们求解的需要。
代码中定义如下：
delta 表示退火的速度eps 表示极低值。退火时是 tempetare*delta
当然达不到 0T表示初始温度srand(seed) 表示以 seed
为种子生成的随机数。引用于 cstdlib 库。当你想完全随机时可令
seed=time(0)，time() 函数引用于
ctime 库。生成完了后，用 rand() 得到这些值
exp(x) 表示 e^x，引用于 cmath
库
模拟退火的中心公式是在随机出的解差于最优解时，有一定几率跳出该解，并且这个几率会随着次数变小，即：
rand()<exp((ans-newans)/t) * RAND_MAX
POJ 2420
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<ctype.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<cmath>
#include<utility>
#define eps 1e-10
#define INF 1e19
#define delta 0.98
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
const int maxn=2e5+10;
typedef pair<double,double> pairr;
pair <double,double> p[maxn];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
inline double dist(pairr a,pairr b)
{
return sqrt((a.first-b.first)(a.first-b.first)+(a.second-b.second)(a.second-b.second));
}
inline double getsum(pairr p[],int n,pairr z)
{
double ans=0;
while(n--) ans+=dist(p[n],z);
return ans;
}
double search(pairr p[],int n)
{
pairr s=p[0];
double t=100000;
double ans=INF;
while(t>eps)
{
bool flag=1;
while(flag)
{
flag=0;
for(register int i=0;i<4;i++)
{
pairr z;
z.first=s.first+dx[i]t;
z.second=s.second+dy[i]t;
double tp=getsum(p,n,z);
if(ans>tp)ans=tp,s=z,flag=1;
}
}
t*=delta;
}
return ans;
}
int main()
{
int n=read();
for(register int i=0;i<n;i++)p[i]=make_pair(read(),read());
printf("%.0f",search(p,n));
return 0;
}
|
