给定具有x和y坐标的N个点(在2D中).您必须找到一个点P(在N个给定点中),使得从其他(N-1)个点到P的距离之和最小.
对于前 N个点给定p1(x1,y1),p2(x2,y2)...... pN(xN,yN).我们在p1,p2 ...... PN中找到了一个点P,它与所有其他点的距离之和最小.
我使用蛮力方法,但我需要更好的方法.我也试过找到中位数,意思等,但它并不适用于所有情况.
然后我想出了一个想法,我将X视为多边形的顶点并找到该多边形的质心,然后我将从最接近质心的Y中选择一个点.但我不确定质心是否最小化了它到多边形顶点的距离之和,所以我不确定这是否是一个好方法？有没有解决这个问题的算法？
如果您的点分布得很好，并且点数量太多，以至于暴力（计算每个点到其他点的总距离）没有吸引力，那么以下内容可能会给您一个足够好的答案。我所说的“分布良好”是指（大约）均匀或（大约）随机，并且在多个位置没有明显的聚类。
在您的空间中创建一个统一的k*k网格，其中k是一个奇数。如果您的点分布得很好，那么您正在寻找的点（可能）就位于该网格的中央单元格中。对于网格中的所有其他单元格，计算每个单元格中的点数并近似每个单元格中点的平均位置（使用单元格中心或计算单元格(x,y)中点的平均值）。
对于中心单元中的每个点，计算到中心单元中每个其他点的距离，以及到其他单元中点的加权平均距离。当然，这将是从该点到其他单元格中点的“平均”位置的距离，并按其他单元格中的点数进行加权。
您必须权衡较高值的准确性k与增加的计算负载，并找出最适合您的点的方法。如果单元格之间的点分布很不均匀，那么这种方法可能不合适。
这种方法在大规模模拟中应用相当广泛，其中点具有在一定距离内运行的属性，例如重力和电荷。是否适合你的需求，我不知道。