【面】到各点距离和最小的位置

已知一个数组positions,其中positions[i]=[xi,yi]表示第i个客户在二维地图上的位置,返回服务中心的位置,该位置到所有客户的欧几里得距离的总和最小。

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
48
class Solution:
def getMinDistSum(self, positions):
if len(set([tuple(v) for v in positions])) <= 1: return 0

# 初始迭代位置
x0 = sum([p[0] for p in positions]) / len(positions)
y0 = sum([p[1] for p in positions]) / len(positions)

# 初始步长
step = 16
while True:
dx, dy = self.deri(x0, y0, positions)
# 导数都为0, 说明当前是极值点, 退出循环。凹函数的证明可以参考其他文章
if (dx, dy) == (0, 0): break

while True:
x1 = x0 - step * dx
y1 = y0 - step * dy
# 保持x0、y0不变,一直寻找下一个下降点,并在此期间改变步长
if self.dist(x1, y1, positions) < self.dist(x0, y0, positions): break

# 减少步长
step /= 4

if abs(self.dist(x1, y1, positions) - self.dist(x0, y0, positions)) < 10 ** -7:
break

# 转移到下一个位置点
x0, y0 = x1, y1
return self.dist(x0, y0, positions), (x0, y0)

# 计算欧式距离
def dist(self, x, y, positions):
return sum([((x - xi) ** 2 + (y - yi) ** 2) ** 0.5 for xi, yi in positions])

# 计算导数(偏微分)
def deri(self, x, y, positions):
dx, dy = 0, 0
for xi, yi in positions:
div = ((x - xi) ** 2 + (y - yi) ** 2) ** 0.5
if div == 0: continue
dx += (x - xi) / div
dy += (y - yi) / div
return dx, dy

if __name__=='__main__':
s = Solution()
print(s.getMinDistSum([[0,1],[1,0],[1,2],[2,1]]))
0%