给定二维平面上的点列表,如何在平面上放置 N 个点,使得从点列表到最近放置点的所有距离的总和尽可能小?环境是谨慎的,列表将包含 [(0,0) 范围内的唯一点; (~200:~100)]
算法的最坏情况性能最好是多项式(因此实时计算的小范围)。也欢迎任何近似值。
最佳答案
这声音真像什么K-Means clustering algorithm做。在您的例子中,点列表是输入,点数 N 是簇数。
遗憾的是,它所做的是 NP-hard。但是有很多研究正在进行,并且有很多方法可以尝试让它变得更好(只需向下滚动 wiki 页面,您就会找到一些)。
此外,我怀疑是否会有更好的算法,因为 k-means 确实被学术界大量使用。我想如果有更好的算法,他们会为那个算法运行:)
再一次,我向您介绍最适合我的数据挖掘教程:Andrew Moore's slides .虽然我不知道你的目的,但这应该非常接近你的需要。
关于algorithm - 放置 N 点以最小化到点列表的距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6877632/