服务中心的最佳位置

难度: Hard

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。

给你一个数组 positions ，其中 positions[i] = [x_i, y_i] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和。

换句话说，请你为服务中心选址，该位置的坐标 [x_centre, y_centre] 需要使下面的公式取到最小值：

与真实值误差在 10^-5之内的答案将被视作正确答案。

示例 1：

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

示例 2：

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

提示：

1 <= positions.length <= 50
positions[i].length == 2
0 <= x_i, y_i <= 100

Submission

运行时间: 65 ms

内存: 16.0 MB

from typing import List

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        def distance(p1, p2):
            return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

        def weiszfeld(positions):
            # Step 1: 初始化中心点
            x = sum(p[0] for p in positions) / len(positions)
            y = sum(p[1] for p in positions) / len(positions)
            centroid = [x, y]

            # 设置阈值和最大迭代次数
            threshold = 1e-7
            max_iterations = 1000

            # Step 2-4: 迭代更新中心点
            for _ in range(max_iterations):
                total_weight = 0.0
                weighted_sum_x = 0.0
                weighted_sum_y = 0.0

                for p in positions:
                    dist = distance(centroid, p)
                    if dist == 0:  # 避免除以零的情况
                        return p
                    weight = 1.0 / dist
                    total_weight += weight
                    weighted_sum_x += weight * p[0]
                    weighted_sum_y += weight * p[1]

                new_centroid = [weighted_sum_x / total_weight, weighted_sum_y / total_weight]

                # 检查收敛性
                if distance(new_centroid, centroid) < threshold:
                    return new_centroid

                centroid = new_centroid

            return centroid

        # 找到中心点
        centroid = weiszfeld(positions)

        # 计算到所有点的距离之和
        return sum(distance(centroid, p) for p in positions)

solution = Solution()
print(solution.getMinDistSum([[0, 1], [1, 0], [1, 2], [2, 1]]))  # 输出: 4.0
print(solution.getMinDistSum([[1, 1], [3, 3]]))  # 输出: 2.82843 (近似值)

Explain

题解采用了Weiszfeld算法来解决此问题，这是一种用于寻找一组点的几何中心（Fermat点）的有效方法，即最小化给定点到一个未知点的距离总和。算法流程如下：1. 初始化中心点为所有点坐标的算术平均值。2. 使用迭代方式，基于加权平均来调整中心点位置，权重为每个点到当前中心的逆距离。3. 检查新中心与旧中心的距离，若变化非常小则认为已收敛，结束迭代。4. 返回中心点到所有位置的欧几里得距离之和。

时间复杂度: O(kn)，其中n是位置数，k是迭代次数

空间复杂度: O(n)，其中n是输入位置的数量

from typing import List

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        def distance(p1, p2):
            return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

        def weiszfeld(positions):
            x = sum(p[0] for p in positions) / len(positions)
            y = sum(p[1] for p in positions) / len(positions)
            centroid = [x, y]
            threshold = 1e-7
            max_iterations = 1000
            for _ in range(max_iterations):
                total_weight = 0.0
                weighted_sum_x = 0.0
                weighted_sum_y = 0.0
                for p in positions:
                    dist = distance(centroid, p)
                    if dist == 0: return p
                    weight = 1.0 / dist
                    total_weight += weight
                    weighted_sum_x += weight * p[0]
                    weighted_sum_y += weight * p[1]
                new_centroid = [weighted_sum_x / total_weight, weighted_sum_y / total_weight]
                if distance(new_centroid, centroid) < threshold:
                    return new_centroid
                centroid = new_centroid
            return centroid
        centroid = weiszfeld(positions)
        return sum(distance(centroid, p) for p in positions)

solution = Solution()
print(solution.getMinDistSum([[0, 1], [1, 0], [1, 2], [2, 1]]))  # 输出: 4.0
print(solution.getMinDistSum([[1, 1], [3, 3]]))  # 输出: 2.82843 (近似值)

Explore

Weiszfeld算法是通过加权平均的方式调整中心点位置，权重为每个点到当前中心的逆距离。当算法迭代过程中的中心点与某个点完全相同时，该点到中心点的距离为0，导致这个点的权重变成无限大（因为1除以0是无限大）。这会使得其他所有点的相对权重变得微不足道，因此算法直接将这个点作为最终结果返回，因为继续迭代也会得到同样的结果。

在Weiszfeld算法中，使用每个点到当前中心的距离的逆作为权重，是为了确保距离中心点近的点对中心点位置的影响更大。这种权重选择反映了一个直观的想法：距离中心越近的点，其位置应该对中心点的确定有更大的影响。使用距离的逆而非距离的平方的逆或其他形式，是因为它提供了一个良好的平衡点，既能有效地拉近中心点与所有点之间的总距离，同时避免了对极端值过于敏感的问题。

收敛阈值1e-7的选择通常是基于实际应用中对精度的需求和计算资源的考量。这个值足够小，可以确保算法的解在实际应用中足够精确，而不会因为迭代终止过早而产生较大的误差。同时，这个值也不能太小，否则会导致算法需要更多的迭代次数，影响算法的执行效率。选择合适的收敛阈值是在算法的精度和效率之间寻找平衡的结果。

最大迭代次数1000次通常是基于经验选择的，这个值通常足以让算法在多数实际情况下达到收敛。如果在1000次迭代后算法还没有达到预定义的收敛阈值，这可能表明输入数据具有某些特殊性质，使得算法难以快速收敛。在这种情况下，可以考虑调整收敛阈值，增加迭代次数，或者对输入数据进行预处理，以改善算法的收敛性能。