c - 实现几何中位数

Question

当我在谷歌搜索几何中位数时，我得到了这个链接Geometric median 但我不知道如何在 C 中实现它。我不太擅长理解这个数学解释。假设我有 11 对坐标，我将如何计算相同的几何中位数。

我正在尝试解决这个问题Grid CIty。我得到了一个提示，几何中位数将帮助我实现它。我不是在寻找最终的解决方案。如果有人可以引导我走向正确的道路，那将有所帮助。

谢谢是提前

下面是坐标列表a（测试用例）。结果：3 4

1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5

Answer 1

如果没有迭代算法，我认为这是无法解决的。

这是一个类似于爬山版本的伪代码解决方案，除了它可以在任意精度和更高维度上工作。

CurrentPoint = Mean(Points)
While (CurrentPoint - PreviousPoint) Length > 0.01 Do
    For Each Point in Points Do
        Vector = CurrentPoint - Point
        Vector Length = Vector Length - 1.0
        Point2 = Point + Vector
        Add Point2 To Points2
    Loop
    PreviousPoint = CurrentPoint
    CurrentPoint = Mean(Points2)
Loop

笔记：

常数 0.01 并不能保证结果在真值的 0.01 范围内。使用较小的值以获得更好的精度。

常数 1.0 应该调整为（我猜）大约是最远点之间距离的 1/5。太小的值会减慢算法的速度，但太大的值会导致不准确，可能导致无限循环。

Answer 2

答案是 (x _i , y _j )，其中 x _i 是所有 x 的中位数，y _j是所有 y 的中位数。

Answer 3

您没有义务使用几何中位数的概念；所以看到它不容易计算，你最好不计算它来解决你的问题！

这是一个算法/实现的想法。

1. 从任意点开始（例如给定数据中的第一个点）。
2. 计算当前点和 8 个相邻点的距离总和（每个方向上 +/-1，x 和 y）
3. 如果其中一个邻居比当前点好，则更新当前点并从 1 开始
4. （找到最佳距离；现在在距离相等的点中选择最佳点）
5. 计算当前点和 3 个相邻点的距离总和（每个方向 -1，x 和 y）
6. 如果其中一个邻居与当前点相同，则更新当前点并从 5 继续

Answer 4

要解决此问题，您只需计算每个坐标的平均值并将结果四舍五入即可。它应该可以解决您的问题。

Answer 5

正如我评论的那样，您的问题的解决方案不是几何平均值，而是算术平均值。

如果必须计算算术平均值，则需要将列的所有值相加，然后将答案除以元素数。