LC 1515. Best Position for a Service Centre
https://leetcode.com/problems/best-position-for-a-service-centre/
https://leetcode-cn.com/problems/best-position-for-a-service-centre/solution/
题解写的非常好，我只看了前面两种解法。其中梯度下降方法学习ML的时候遇到过，但是没有想到可以在这里使用， 或许今后可以在工作中多多使用，好像也没有那么困难。另外一个方法就是爬山法，用于凸函数的话可以得到最优解。
我总结了一下爬山法的大致框架：
- 首先随机选择一个起始点(x, y)，以及探索距离 `step`
- 开始下面的迭代
- 在各个方向上，以 `step` 去做探索
- 如果在某个方向上有更好的结果，那么跳到这个方向上
- 如果没有更好的，那么 `step=step/2`
- 迭代直到 `step` 到非常小的值
class Solution:
def getMinDistSum(self, positions: List[List[int]]) -> float:
step = 100
xs = [x[0] for x in positions]
ys = [x[1] for x in positions]
n = len(positions)
xc = sum(xs) / n
yc = sum(ys) / n
def dist(xc, yc):
res = 0
for i in range(n):
t0 = (xc - xs[i]) ** 2
t1 = (yc - ys[i]) ** 2
res += (t0 + t1) ** 0.5
return res
while step > 1e-7:
iter = False
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
xc2 = xc + dx * step
yc2 = yc + dy * step
if dist(xc2, yc2) < dist(xc, yc):
iter = True
xc, yc = xc2, yc2
break
if not iter:
step = step / 2
ans = round(dist(xc, yc), 5)
return ans
梯度下降算法好像也不是特别困难，最主要的是对cost function求导。求导函数在题解连接里面有，也不是特别复杂。虽然题解说有一定几率能过，但是显然这个几率有点低，不太适合在比赛时候使用。
class Solution2:
def getMinDistSum(self, positions: List[List[int]]) -> float:
decay = 1 - 0.001
batchSize = 100
eps = 1e-7
alpha = 1
xs = [x[0] for x in positions]
ys = [x[1] for x in positions]
n = len(positions)
xc = sum(xs) / n
yc = sum(ys) / n
def dist(xc, yc):
res = 0
for i in range(n):
t0 = (xc - xs[i]) ** 2
t1 = (yc - ys[i]) ** 2
res += (t0 + t1) ** 0.5
return res
value = dist(xc, yc)
while True:
random.shuffle(positions)
dx, dy = 0, 0
for i in range(min(n, batchSize)):
d = ((xc - xs[i]) ** 2 + (yc - ys[i]) ** 2) ** 0.5
dx += (xc - xs[i]) / (d + eps)
dy += (yc - ys[i]) / (d + eps)
xc -= alpha * dx
yc -= alpha * dy
alpha *= decay
newValue = dist(xc, yc)
if abs(newValue - value) < 1e-7:
break
value = newValue
ans = round(value, 5)
return ans