爬山算法與模拟退火

以一道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;
}