我在由 (x,y) 坐标定义的图形上有一组 N 个点，还有一个包含它们成对距离的表格。我正在寻找生成一个表格，其中包含他们的相对“亲密度排名”，例如如果 closeness[5][9] == 4，则节点 9 是相对于节点 5 第四近的项目。
这样做的明显方法是生成索引列表并根据 d[i][j] < d[i][k] 对每个 i (1->n) 对它们进行排序，然后转换表知道 sorted[5][4] == 9 意味着 closeness[5][9] == 4。
这需要 O(n² log n) 时间。我觉得可能有更有效的方法。有什么想法吗？
最佳答案
好的，我会尝试尝试一下。
背景知识:这个问题跟k-nearest neighbor有点关系。我不确定你是如何生成成对距离的，但 k-d 树非常擅长解决这类问题。
现在，即使你使用 k-d 树，它也会有所帮助(你只查询你需要的，而不是对所有点进行排序):在 O(N log N) 时间内构建树，然后为 K 个最近的您要查询的点，每个点都需要 O(log N) 时间。最后，您看到的是 O(N log N) + O(NK log N)。
好的，现在是真正的启发式部分。这将取决于您的数据，您可能想看看它们是靠得很近还是相距很远。但是，您可以尝试分而治之的方法，将飞机分成多个箱子。当您需要找到最近的点时，找出您正在处理的点属于哪个 bin，然后您只处理相邻的 bin，并在需要更多点时探索更多相邻的 bin。
希望这对您有所帮助，祝您好运。
关于algorithm - 高效重复分拣，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13842164/