05 August 2008
服务中心的最佳位置
一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。
给你一个数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和 。
换句话说，请你为服务中心选址，该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值：
与真实值误差在 10^-5 之内的答案将被视作正确答案。
机器学习中凸函数的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
private static int[][] dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public double getMinDistSum(int[][] positions) {
double eps = 1e-7;
double step = 1;
double decay = 0.5;
int n = positions.length;
double x = 0.0, y = 0.0;
for (int[] pos : positions) {
x += pos[0];
y += pos[1];
}
x /= n;
y /= n;
while (step > eps) {
boolean modified = false;
for (int i = 0; i < 4; ++i) {
double xNext = x + step * dirs[i][0];
double yNext = y + step * dirs[i][1];
if (getDist(xNext, yNext, positions) < getDist(x, y, positions)) {
x = xNext;
y = yNext;
modified = true;
break;
}
}
if (!modified) {
step *= (1.0 - decay);
}
}
return getDist(x, y, positions);
}
// 计算服务中心 (xc, yc) 到客户的欧几里得距离之和
public double getDist(double xc, double yc, int[][] positions) {
double result = 0;
for (int[] pos : positions) {
result += Math.sqrt((pos[0] - xc) * (pos[0] - xc) + (pos[1] - yc) * (pos[1] - yc));
}
return result;
}
}