algorithm - 放置 N 点以最小化与点列表的距离

Question

给定一个二维平面上的点列表，如何在平面上放置 N 个点，使得从点列表到最近放置点的所有距离的总和尽可能小？环境是谨慎的，列表将包含 [(0,0) 范围内的唯一点；(~200:~100)]

优选地，算法的最坏情况性能应该是多项式的（因此实时计算的小范围）。也欢迎任何近似值。

Answer 1

这听起来真的很像K-Means 聚类算法所做的。在您的情况下，点列表是输入，点数 N 是聚类数。

可悲的是，它所做的是 NP 难的。但是有很多研究正在进行，并且有很多方法可以让它变得更好（只需向下滚动 wiki 页面，您就会找到一些）。

另外，我怀疑会有更好的算法，因为 k-means 确实被学术界大量使用。我想如果有更好的算法他们会为那个运行:)

再一次，我向您展示了对我来说最好的数据挖掘教程：Andrew Moore 的幻灯片。虽然我不知道你的目的，但这应该非常接近你的需要。

Answer 2

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.