模拟退火算法来源于固体退火原理，更多的化学物理公式等等这里不再废话，我们直接这么来看
模拟退火算法简而言之就是一种暴力搜索算法，用来在一定概率下查找全局最优解
找的过程和固体退火原理有所联系，一般来讲，就是设置应该初始温度T（通常为100），一个退火的系数K（通常为0.98），一个退火的结束温度T1（通常为1e-8）
每进行一次查找,T = T * K
如果T = T1，查找停止，（即固体退火完成）
这里以POJ2420和HDU1109为例
POJ2420题目地址：
http://poj.org/problem?id=2420
这个题的题意是给n个点，让你找一个点的距离到这n个点的距离最小
直接设好温度和方向搜索就好了
注意POJ的G++编译器输出%0.0lf会WA
//POJ2420
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define it iterator
#define ll long long
#define eb emplace_back
#define lowbit(x) x & -x
#define all(x) x.begin(),x.end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define per(x,a,b) for(int x = a; x <= b; x++)
#define rep(x,a,b) for(int x = a; x >= b; x--)
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) const int birth = ;
const int mo = ;
const int maxn = 1e5 + ;
const int mod = 1e9 + ;
const int INF = 1e9;
const double eps = 1e-;//停止的温度 char mp[][];
bool vis[][];
//******************THE PROGRAM BEGINING******************
int n;
int d[][] = { { , },{ -, },{ , },{ ,- } }; struct node
{
double x, y;
node() {}
}p[]; double dis(node p[], node x, int n)//求点X与各点距离
{
double sum = ;
per(i, , n - )
sum += sqrt(pow(p[i].x - x.x, ) + pow(p[i].y - x.y, )); return sum;
} double solve(node p[], int n)
{
double ans = 0x3f3f3f3f;
double T = ;//初始温度
double e = 0.98;//系数
node now = p[];//设置初始点（随便设个就好了）
while (T > eps)
{
bool flag = ;
while (flag)
{
flag = ;
per(i, , )
{
node next = now;
next.x += d[i][];
next.y += d[i][];
double temp = dis(p, next, n);
if (ans > temp)//更新
{
ans = temp;
flag = ;
now = next;
}
}
}
T *= e;//冷却
} return ans;
} int main()
{
//IO;
scanf("%d", &n);
per(i, , n - )
scanf("%lf %lf", &p[i].x, &p[i].y);
printf("%.0f\n", solve(p,n));
return ;
}
HDU1109题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=1109
这个题的题意是给一个大小为x*y的房间和n个点，让你找在这个房间里一个点，这个点到n个点中离得它最近点之间距离是最大的
这个题如果跟上题一样做的话，有可能会掉进局部最优解，有两种解决方法：
1：在更新数值的时候允许一定几率跳出当前解法，几率随温度降低而降低
2：多设置几个点同时查找
我这里选择了第二种做法，个人认为更靠谱一点（其实都是随机的了，不过我觉得随机的越少越稳定）
这个题还要注意精度问题，这里采用2种不同的移动精度来保证速度和精度，根据当前温度来决定精度优先或移动优先
本来还打算记忆化搜索来加快速度的，结果MLE了。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define it iterator
#define ll long long
#define eb emplace_back
#define lowbit(x) x & -x
#define all(x) x.begin(),x.end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define per(x,a,b) for(int x = a; x <= b; x++)
#define rep(x,a,b) for(int x = a; x >= b; x--)
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) const int birth = ;
const int mo = ;
const int maxn = 1e5 + ;
const int mod = 1e9 + ;
const int INF = 0x3fffffff;
const double eps = 1e-; //******************THE PROGRAM BEGINING******************
int n,x,y;
int d[][] = { { , },{ -, },{ , },{ ,- },{ , },{ -, },{ , },{ -,- } };
double d1[][] = { { 0.001, },{ -0.001, },{ ,0.001 },{ ,-0.001 },{ 0.001,0.001 },{ -0.001,0.001 },{ 0.001,-0.001 },{ -0.001,-0.001 } };
double ans[];
//bool vis[10000][10000];
struct node
{
double x, y;
node() {}
}p[], r[];; double dis(node p[], node x, int n)
{
double MIN = INF;
per(i, , n - )
{
MIN = min(MIN,sqrt(pow(p[i].x - x.x, 2.0) + pow(p[i].y - x.y, 2.0)));
} return MIN;
} node solve(node p[], int n)
{
double T = ;
double e = 0.98;
node now;
srand(birth);
per(i, , )
{
r[i].x = rand() % x;
r[i].y = rand() % y;
ans[i] = dis(p, r[i], n);
//vis[(int)r[i].x][(int)r[i].y] = 1;
}
while (T > eps)
{
bool flag = ;
while (flag)
{
flag = ;
per(j, , )
per(i, , )
{
node next = r[j];
//if (T < 0.1)
//printf("1: %lf %lf\n", next.x, next.y);
if (T > 0.5)
{
next.x += d[i][];
next.y += d[i][];
}
else
{
next.x += d1[i][];
next.y += d1[i][];
}
if (next.x < || next.y < || next.x > x || next.y > y)
continue;
//if (T > 1 && vis[(int)next.x][(int)next.y])
//continue;
double temp = dis(p, next, n);
//printf("2: %lf %lf\n", next.x ,next.y);
if (ans[j] < temp)
{
ans[j] = temp;
flag = ;
r[j] = next;
//if (T > 1)
//vis[(int)next.x][(int)next.y] = 1;
}
}
}
T *= e;
}
double min = ;
int pos;
per(i, , 5)
{
if (ans[i] > min)
min = ans[i],pos = i;
}
return r[pos];
} int main()
{
//IO;
int t;
scanf("%d", &t);
while (t--)
{
//ZERO(vis);
scanf("%d %d %d", &x, &y, &n);
per(i, , n - )
scanf("%lf %lf", &p[i].x, &p[i].y);
node ans = solve(p, n);
printf("The safest point is (%.1f, %.1f).\n", ans.x, ans.y);
/*
node a;
a.x = 1433.0;
a.y = 1669.9;
cout << dis(p, a, n) << endl;
a.y = 1669.8;
cout << dis(p, a, n) << endl;
*/
}
return ;
}
实际使用中，我们也不要把思路局限在对随机点的上下左右移动上，更要根据题目来判断对时间上和方向上的把握，灵活改变策略
如：POJ2069
大致就是这样吧