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的时候遇到过,但是没有想到可以在这里使用, 或许今后可以在工作中多多使用,好像也没有那么困难。另外一个方法就是爬山法,用于凸函数的话可以得到最优解。

我总结了一下爬山法的大致框架:

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