Leetcode難題 1515. Best Position for a Service Centre

 Leetcode難題 1515. Best Position for a Service Centre

A delivery company wants to build a new service center in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new center in a position such that the sum of the euclidean distances to all customers is minimum.

Given an array positions where positions[i] = [xi, yi] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.

In other words, you need to choose the position of the service center [xcentre, ycentre] such that the following formula is minimized:

Answers within 10-5 of the actual value will be accepted.

這題是有名的 Geometric median

可以使用gradient descent來操作 

或是隨機選四個方向，緩慢減少步長，

可以證明這個問題是convex，詳情可以參考 https://arxiv.org/abs/1302.5244

所以找尋local minimum 等於找尋global minimum。

可以參考底下的python Code

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        n=len(positions)
        
        # boundary 
        if n==1:
            return 0 
        
        def dist(x,y):
            res=0
            for i in positions:
                a,b=i
                res+=math.sqrt((x-a)**2+(y-b)**2)
            return res
        # initial point
        inix,iniy=0,0
        cur=dist(inix,iniy)
        step=1
        while step>0.000001:
            f=False
            for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
                curx,cury=inix+step*dx,iniy+step*dy
                if dist(curx,cury)<cur:
                    cur=dist(curx,cury)
                    inix,iniy=curx,cury
                    f=True
                
                    
                    
            if f==False:
                step=step/10
        return cur