给定一个点之间距离的矩阵,是否有一个算法来确定一组具有这些距离的n维点?(或至少最小化错误)
有点像N维版的收费公路问题。
我能想到的最好办法就是使用多维缩放。

最佳答案

你是正确的轨道与多维缩放(MDS),但MDS是不切实际的大数据集,因为它的时间复杂度是二次的点的数量。您可能想看看FASTMAP,它具有线性时间复杂度,并且更适合于索引。见:
克里斯托斯·法洛托斯和叶林国王:
“fastmap:一种快速算法
索引、数据挖掘和
传统和
多媒体数据集,进程中。
SIGMOD,1995年,doi:10.1145/223784.223812

08-27 21:14
查看更多