首页 > 代码库 > poj 2420，模拟退火算法，费马点
poj 2420，模拟退火算法，费马点
题目链接：http://poj.org/problem?id=2420
题意：给n个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。
参考链接：http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html
这一篇文章写的很好，我这个小白都有一点小明白了。
记一下笔记：
模拟退火： 就是在一定范围内接受一些不是最优的解，来跳出局部最优，靠近整体最优。
贴一下伪代码：
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<deque>#include<functional>#include<iterator>#include<set>#include<utility>#include<stack>#include<queue>#include<iomanip>#include<cmath>using namespace std;#define N 1005#define eps 1e-8#define INF 1e99#define delta 0.98#define T 100int dx[4] = {0,0,-1,1};int dy[4] = {-1,1,0,0};struct Point{ double x,y;} p[N];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 GetSum(Point p[],int n,Point t){ double ans = 0; while(n--) { ans+=dist(p[n],t); } return ans;}double Search(Point p[],int n){ Point s = p[0]; double t = T; double ans = INF; while(t>eps) { bool flag = 1; while(flag) { flag = 0; for(int i=0; i<4; i++) { Point z; z.x = s.x + dx[i]*t; z.y = s.y + 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; while(~scanf("%d",&n)) { for(int i=0; i<n; i++) scanf("%lf%lf",&p[i].x,&p[i].y); printf("%.0lf\n",Search(p,n)); } return 0;}
poj 2420，模拟退火算法，费马点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。