返回题库

服务中心的最佳位置

Best Position for a Service Centre

专题
Algorithmic Programming / 算法编程
难度
L4
来源
Citadel

题目详情

问题：服务中心的最佳位置

考察：贪心

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/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.

 

Example 1:

Input: positions = [[0,1],[1,0],[1,2],[2,1]]
Output: 4.00000
Explanation: As shown, you can see that choosing [xcentre, ycentre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.

Example 2:

Input: positions = [[1,1],[3,3]]
Output: 2.82843
Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843

 

Constraints:

  • 1 <= positions.length <= 50
  • positions[i].length == 2
  • 0 <= xi, yi <= 100
解析

思路：目标函数是到所有点欧氏距离之和，属于凸优化问题。可以从所有点的平均位置出发做二维梯度下降/模拟退火式步长下降：若朝某方向移动能降低距离和就更新，否则逐步缩小步长，直到达到精度要求。

复杂度：每次评估 O(n)，迭代次数由精度控制，通常可视为 O(n log(1/eps))。