【POJ】2420 A Star not a Tree?

http://poj.org/problem?id=2420

题意:给n个点,求一个点使得到这个n个点的距离和最短,输出这个最短距离(n<=100)

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=5005;
struct P { int x, y; }a[N];
int n;
inline int rand(int x, int y) { return x+(rand()%(y-x+1)); }
inline double sqr(double x) { return x*x; }
inline double dis(double x1, double y1, double x2, double y2) { return sqrt(sqr(x1-x2)+sqr(y1-y2)); }
inline double getdis(double x, double y) {
double ret=0;
for(int i=0; i<n; ++i) ret+=dis(x, y, a[i].x, a[i].y);
return ret;
}
double getnode(double x, double y, double T, double &xx, double &yy) {
double tx, ty, dis, ret=1e300;
for(int i=0; i<50; ++i) {
tx=x+((double)rand(-100, 100)/100)*T;
ty=y+((double)rand(-100, 100)/100)*T;
dis=getdis(tx, ty);
if(dis<ret) {
ret=dis;
xx=tx;
yy=ty;
}
}
return ret;
}
int main() {
srand(1998);
while(~scanf("%d", &n)) {
double x=0, y=0, T=1e20, dE, tans, ans, nans, xx, yy;
for(int i=0; i<n; ++i) scanf("%d%d", &a[i].x, &a[i].y), x+=a[i].x, y+=a[i].y;
x/=n; y/=n;
nans=ans=getdis(x, y);
while(T>0.01) {
tans=getnode(x, y, T, xx, yy);
dE=nans-tans;
if(dE>=0 || exp(dE/T)>(double)rand(1, 99999)/100000) {
nans=tans; x=xx; y=yy; ans=min(ans, nans);
}
T*=0.9;
}
printf("%.0f\n", ans);
}
return 0;
}

  

随机化大法好= =

学习了下模拟退火...其实就是啥玩意随机一下再随机一下QAQ

具体学习看http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

引用一个上边的比喻:

爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。

模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

现在有个退火公式= =

$$exp(dE/T)$$

其中$dE$是解的代表值之间的差,即$ans-temp$,其中$ans$是之前得到的最优解,$temp$是当前的解。$dE>=0$显然是可以取的,$dE<0$那么就要一定概率的取= =;$T$代表此时的温度,而且T是一直下降的

由于这个式子的取值在$(0, 1)$之间,所以我们在这个区间随机取一个值然后来搞就行了= =

具体看代码QAQ

upd:我发现我的模拟退火好像写错了啊...降温是在接受较差的解那里降温啊......

上一篇:GridSearchCV网格搜索得到最佳超参数, 在K近邻算法中的应用


下一篇:java 锁!