放置 N 个点以最小化到点列表的距离
给定 2D 平面上的点列表，如何在平面上放置 N 个点，使得从点列表到最近放置的点的所有距离的总和尽可能小？环境是谨慎的，列表将包含 [(0,0) ; 范围内的唯一点。 (~200:~100)]
优选地，算法的最坏情况性能应该是多项式的（因此可以实时计算小范围）。也欢迎任何近似值。
Given a list of points on a 2D plane how could one place N points on the plane in such a way that that the total sum of all distances from the list of points to the closest placed point were as small as possible? The environment is discreet and the list will contain unique points within a range of [(0,0) ; (~200:~100)]
Preferably the algorithm's worst case performance should be polynomial (and thus with the small ranges computational in real time). Any approximations are welcome as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这听起来真的很像 K-Means 聚类算法 所做的。在您的情况下，点列表是输入，点的数量 N 是簇的数量。
遗憾的是，它所做的事情是 NP 困难的。但是正在进行许多研究，并且有很多方法可以尝试使其变得更好（只需向下滚动 wiki 页面，您就会找到一些）。
另外，我怀疑是否会有更好的算法，因为 k 均值确实被学术界大量使用。我想如果有更好的算法，他们会运行这个算法:)
再一次，我向您展示数据挖掘中最好的教程：安德鲁·摩尔的幻灯片。虽然我不知道你的目的，但这应该非常接近你的需要。
This sound really like what K-Means clustering algorithm do. In your case, the list of points are the input, and the number of points N is the number of clusters.
Sadly, what it does is NP-hard. But there are many researches going on, and a lot ways to try to make it better (just scroll down the wiki page you'll find some).
Also, I doubt there will be a better algorithm, since k-means is really heavily used by academics. I guess if there is a better algorithm they'd run for that one:)
And again, I present you the best tutorial in Data Mining for me: Andrew Moore's slides. Although I don't know your purpose, this should be very close to what you need.
您可以获得节点列表的质心（带有权重 = 1)。
或者用 x^2 表示距离的方差。
您已将问题简化为将 N 个节点放置在质心区域中与其余节点的距离最小的位置。
在完美的世界中，您只需将一个点放在质心即可。但因为我假设你不能将 2 个点放在同一个地方，所以你需要选择质心附近。
这样问题就简化为只选择质心附近 8 个点中最好的一个，然后重新计算质心，然后再做一次。
You could get the Center of mass of the list of nodes (with weights = 1).
Or a variance of it with x^2 for distances.
You've reduced the problem to where to place the N nodes in the area of center of mass where the distance to the rest is minimal.
In a perfect world you'd just put one point in the center of mass. But because I assume you can't place 2 points in the same place, you need to choose the vicinity of the center of mass.
So that reduces the problem to just choosing the best of 8 points near the center of mass, then recalculate center of mass, and do it again.