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

Question

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

算法的最坏情况性能最好是多项式(因此实时计算的小范围)。也欢迎任何近似值。

Answer 1

这声音真像什么K-Means clustering algorithm做。在您的例子中，点列表是输入，点数 N 是簇数。

遗憾的是，它所做的是 NP-hard。但是有很多研究正在进行，并且有很多方法可以尝试让它变得更好(只需向下滚动 wiki 页面，您就会找到一些)。

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

再一次，我向您介绍最适合我的数据挖掘教程:Andrew Moore's slides .虽然我不知道你的目的，但这应该非常接近你的需要。