挑战建立信号基站问题成功，下面说说具体的想法。
模拟退火法其实很简单，分如下几步：
1、首先确定评价函数。
2、选取初始点，并用评价函数计算初始值，把初始值作为当前值。
3、按步进规则获取新点
4、计算新点的值(也可能是附近的多个值)。
5、比较新值和当前值差距，如果小于预期，执行步骤6，否则按一定概率执行步骤6。
6、那么取把新值作为当前值，新点作为当前点，执行步骤3。
7、更新步进值，执行步骤3。
首先说评价函数，在这个问题中，即为选取点到所有基站的距离和。在这里说一下，网上不少人用欧式空间距离，即sqrt((x1-x0)*(x1-x0),(y1-y0)*(y1-y0))，增加了计算时间。其实没必要，完全可以用max(|x1-x0|,|y1-y0|)。因为作为空间长度的度量只要满足如下几个条件就可以了：
1、||A,A||=0;
2、||A,B||=||B,A||
3、||A,B||+||B,C||>=||A,C||
大家可以证明下，max(|x1-x0|,|y1-y0|)是可以作为空间距离度量的。
初始点选取，我就选择了第一点，没什么道理，随便选的一个，反正最后都会收敛的。
唯一修改的地方就是步进值得选择上，稍稍改进了一下，判断新值和原值的差距，如果相差大，就大幅调整步进，否则小幅调整步进。
贴上代码
package pango.bestdistance;
public class Main {
public static double getDistance(double[] pointA, double[] pointB) {
return Math.max(Math.abs(pointA[0] - pointB[0]),
Math.abs(pointA[1] - pointB[1]));
}
public static double getSumDistance(double[][] points, double[] point0) {
double result = 0;
for (int i = 0; i < points.length; i++) {
result += getDistance(points[i], point0);
}
return result;
}
public static double bestDistance(int[] x, int[] y) {
if (x == null || y == null || x.length != y.length)
throw new UnknownError();
double[] nextPoint = new double[2];
double[] curPoint = new double[2];
double[][] direct = new double[][] { { 0, 1 }, { 0, -1 }, { 1, 0 },
{ -1, 0 }, { 0.7071, 0.7071 }, { 0.7071, -0.7071 },
{ -0.7071, 0.7071 }, { -0.7071, -0.7071 }, };
double step = 100000000;
double r = 0.99;
double chance = 0.99;
double precision = 0.0001;
double[][] points = new double[x.length][2];
for (int i = 0; i < x.length; i++) {
points[i][0] = x[i];
points[i][1] = y[i];
}
curPoint[0] = points[0][0];
curPoint[1] = points[0][1];
double result = getSumDistance(points, curPoint);
while (Double.compare(step, precision) > 0) {
boolean ok = true;
double good = 0.0;
while (ok) {
ok = false;
for (int i = 0; i < direct.length; i++) {
nextPoint[0] = direct[i][0] * step + curPoint[0];
nextPoint[1] = direct[i][1] * step + curPoint[1];
if (Double.compare(nextPoint[0], -1000000000.0) < 0
|| Double.compare(nextPoint[1], -1000000000.0) < 0) {
continue;
}
double t = getSumDistance(points, nextPoint);
if(Double.compare(result, 0.0) != 0 ) {
good=Math.abs(1.0 - Math.abs(t - result / result));
}else {
good=Math.abs(1 - Math.abs(t));
}
if (Double.compare(t, result) < 0) {
result = t;
curPoint[0] = nextPoint[0];
curPoint[1] = nextPoint[1];
ok = true;
} else if (Math.random() > chance) {
result = t;
curPoint[0] = nextPoint[0];
curPoint[1] = nextPoint[1];
ok = true;
}
}
}
step = Double.compare(good, 1) > 0 ? step * r : step * good * 0.9;
}
return result;
}
public static void main(String[] args) {
/***
* （1，4） （2，3） （0，1） （1，1）
*/
int[] x = new int[] { 1, 2, 0, 1 };
int[] y = new int[] { 4, 3, 1, 1 };
System.out.println(bestDistance(x, y));
}
}
解释一下69行那个步长更新，原来解释不是很清楚，实际上是越接近最优点，步长减的更慢，我称之为让子弹多飞一会儿。道理嘛，是根据我的本专业《金属材料》知识，凭直觉加的那么一句。步长的更新速度实际上等同于温度降低的快慢，让温度降的慢一点，就更有利于原子的向更低的能级组成方式排列。