1515. 服务中心的最佳位置

ITCharge大约 5 分钟

---

1515. 服务中心的最佳位置

标签：几何、数组、数学、随机化
难度：困难

题目链接

1515. 服务中心的最佳位置 - 力扣

题目大意

描述：给定一个数组 $positions$ ，其中 $positions[i] = [x_i, y_i]$ 表示第 $i$ 个客户在二维平面上的坐标。

要求：返回一个服务中心的最佳位置（可以在任何位置），使得服务中心到所有客户的欧几里得距离之和最小。返回最小距离和。与实际答案误差在 $10^{-5}$ 以内即视为正确。

说明：

$1 \le positions.length \le 50$ 。
$positions[i].length == 2$ 。
$0 \le x_i, y_i \le 100$ 。

示例：

示例 1：

输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。

示例 2：

输入：positions = [[1,1],[3,3]]
输出：2.82843
解释：欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843

解题思路

思路 1：数学 + 梯度下降/模拟退火

1. 核心思想

这是一个几何中位数（Geometric Median）问题。给定二维平面上的 $n$ 个点，求平面上一点使得该点到所有点的欧几里得距离之和最小。

几何中位数没有闭式解，通常用迭代方法求解：

梯度下降法：利用距离和的梯度方向迭代更新位置。
模拟退火：随机搜索 + 逐渐减小的步长。
三元搜索嵌套：分别在 $x$ 和 $y$ 方向上进行三元搜索。

由于 $n \le 50$ ，坐标范围 $[0, 100]$ ，使用模拟退火（或梯度下降） 是简单有效的做法。

2. 距离和的梯度

设当前位置为 $(x, y)$ ，目标函数（到各点的距离和）为：

f(x, y) = \sum_{i=1}^{n} \sqrt{(x - x_i)^2 + (y - y_i)^2}

目标是最小化 $f(x, y)$ 。梯度为：

\frac{\partial f}{\partial x} = \sum_{i=1}^{n} \frac{x - x_i}{\sqrt{(x - x_i)^2 + (y - y_i)^2}}

\frac{\partial f}{\partial y} = \sum_{i=1}^{n} \frac{y - y_i}{\sqrt{(x - x_i)^2 + (y - y_i)^2}}

当点 $(x, y)$ 与某个客户点重合时（分母为 $0$ ），跳过该点即可。

3. 具体步骤（梯度下降法）

第 1 步：选取初始位置。可以用所有点的平均坐标作为起点：

x = \frac{1}{n}\sum x_i, \quad y = \frac{1}{n}\sum y_i

第 2 步：设置初始步长 $step$ （如 $50$ ），衰减因子 $alpha$ （如 $0.99$ ）。

第 3 步：迭代更新：

计算梯度 $\frac{\partial f}{\partial x}$ 和 $\frac{\partial f}{\partial y}$ 。
沿负梯度方向移动： $x = x - step \times \frac{\partial f}{\partial x}$ ， $y$ 同理。
步长衰减： $step = step \times alpha$ 。

第 4 步：当步长足够小（如 $< 10^{-12}$ ）时停止迭代。

第 5 步：计算最终位置的距离和并返回。

4. 举例说明

以 $positions = [[0,1],[1,0],[1,2],[2,1]]$ 为例：

初始点取中心 $(1, 1)$ ：

$dist = \sqrt{2} + 1 + 1 + \sqrt{2} \approx 4.828$
经过迭代逐步调整，最终收敛到 $(1, 1)$ ，最小距离和为 $2 + 2\sqrt{2} \approx 4.828$ 。

以 $positions = [[1,1],[3,3]]$ 为例：

直观最优位置在 $[1,1]$ 或 $[3,3]$ 之间任意点均可，最小距离和为 $\sqrt{(3-1)^2 + (3-1)^2} = 2\sqrt{2} \approx 2.828$ 。

思路 1：代码

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        n = len(positions)
        # 初始点取均值
        x = sum(p[0] for p in positions) / n
        y = sum(p[1] for p in positions) / n

        step = 50.0          # 初始步长
        alpha = 0.99         # 衰减因子
        eps = 1e-12          # 停止阈值

        # 定义距离和函数（也可用于验证）
        def total_dist(cx, cy):
            res = 0.0
            for px, py in positions:
                dx = cx - px
                dy = cy - py
                res += math.sqrt(dx * dx + dy * dy)
            return res

        while step > eps:
            dx_grad = 0.0
            dy_grad = 0.0
            for px, py in positions:
                d = math.sqrt((x - px) ** 2 + (y - py) ** 2)
                if d < 1e-12:  # 重合时跳过
                    continue
                dx_grad += (x - px) / d
                dy_grad += (y - py) / d
            # 沿负梯度方向移动
            x -= step * dx_grad
            y -= step * dy_grad
            step *= alpha

        return total_dist(x, y)

思路 1：复杂度分析

时间复杂度： $O(n \times \log_{alpha}(eps/step_0))$ ，迭代次数约 $\log_{0.99}(10^{-12}/50) \approx 3000$ 次，每次 $O(n)$ 。总体约 $O(n \times 3000) = O(n)$ 。
空间复杂度： $O(1)$ ，仅常数变量。

思路 2：模拟退火

1. 核心思想

模拟退火是一种随机优化算法。从一个初始点出发，每次在当前位置附近随机扰动，若新位置的距离和更小则接受，否则以一定概率接受（以跳出局部最优）。

2. 具体步骤

第 1 步：初始温度 $T$ （如 $100$ ），降温速率 $rate$ （如 $0.99$ ）。

第 2 步：在当前点 $(x, y)$ 附近随机扰动得到新点 $(nx, ny)$ 。

第 3 步：计算 $delta = f(nx, ny) - f(x, y)$ 。

若 $delta < 0$ （更优），接受新点。
否则以概率 $e^{-delta / T}$ 接受。

第 4 步：降温 $T = T \times rate$ 。

第 5 步：温度足够低时停止。

import math
import random

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        n = len(positions)
        x = sum(p[0] for p in positions) / n
        y = sum(p[1] for p in positions) / n

        def total_dist(cx, cy):
            res = 0.0
            for px, py in positions:
                dx = cx - px
                dy = cy - py
                res += math.sqrt(dx * dx + dy * dy)
            return res

        T = 100.0          # 初始温度
        rate = 0.99        # 降温速率
        eps = 1e-8
        cur_dist = total_dist(x, y)
        best_dist = cur_dist

        while T > eps:
            # 随机扰动
            nx = x + (random.random() - 0.5) * T
            ny = y + (random.random() - 0.5) * T
            new_dist = total_dist(nx, ny)
            delta = new_dist - cur_dist

            if delta < 0:
                x, y = nx, ny
                cur_dist = new_dist
                if new_dist < best_dist:
                    best_dist = new_dist
            else:
                if random.random() < math.exp(-delta / T):
                    x, y = nx, ny
                    cur_dist = new_dist

            T *= rate

        return best_dist

思路 2：复杂度分析

时间复杂度： $O(n \times \log_{rate}(eps/T_0))$ ，同上近似 $O(n)$ 。
空间复杂度： $O(1)$ 。