爬山算法与模拟退火

以一道ai引论的课程作业为例：

翻译过来就是：找一个多边形的费马点（到多边形每个角距离之和最小的点）

一、爬山算法

//by szj
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

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

int n;
double eps = 1.0;//定义比较精度
double ans,step;
bool flag;

struct POS{
	double x,y;
}pos[110];

double dist(POS a,POS b){
	return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}

double Dis_of_All(POS x){
	double res = 0;
	for(int i=1;i<=n;++i)res+=dist(x,pos[i]);
	return res;
}

int main() {
	
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lf %lf",&pos[i].x,&pos[i].y);
	step=100.0;//定义初始步长
	POS cur = pos[1];
//要注意这里，爬山撒点应该随机选择多个，但此题直接选取第一个点也可ac
	ans=Dis_of_All(cur);
	while(step>=eps){
		flag=false;
		for(int i=0;i<8;++i){
			POS tmp_cur = (POS){cur.x+step*dx[i],cur.y+step*dy[i]};
			double tmp_ans = Dis_of_All(tmp_cur);
			if(tmp_ans<ans){//如果当前解比答案更优，则更新
				cur = tmp_cur;
				ans = tmp_ans;
				flag = 1;
			}
		}
		if(!flag)step/=2.0;//如果当前的步长已经无法改变答案，就改变步长
	}
	printf("%.lf\n",ans);

	return 0;
}
           

二、模拟退火

//by szj
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const double delta = 0.996;//温度变动量

int n;

struct POS{
	double x,y;
}pos[110];
POS ans;

double dist(POS a,POS b){
	return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}

double Dis_of_All(POS x){
	double res = 0;
	for(int i=1;i<=n;++i)res+=dist(x,pos[i]);
	return res;
}

void Set_Fire(){
	double t = 2020;//设置初始温度
	while(t>1e-16){
		POS nw = (POS){ans.x + ( (rand()<<1) -RAND_MAX ) * t , ans.y + ( (rand()<<1) -RAND_MAX ) * t};
		double tmp = Dis_of_All(nw)-Dis_of_All(ans);
		if(tmp<0)ans=nw;//当前解优于答案，则更新
		else if(exp(-tmp / t) * RAND_MAX > rand())ans = nw;//不优于，则按照Metropolis接受准则
		t*=delta;
	}
}

int main() {
	
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lf %lf",&pos[i].x,&pos[i].y);
	
	ans.x=ans.y=0;
	Set_Fire();
	printf("%.lf\n",Dis_of_All(ans));
	
	return 0;
}