1

我在由 (x,y) 坐标定义的图上有一组 N 个点，以及一个带有成对距离的表格。我希望生成一个具有它们相对“密切度排名”的表，例如如果 closeness[5][9] == 4，则节点 9 是相对于节点 5 的第四个最接近的项目。

这样做的明显方法是生成一个索引列表并根据每个 i (1->n) 的 d[i][j] < d[i][k] 对它们进行排序，然后通过知识转换表sorted[5][4] == 9 意味着接近度[5][9] == 4。

这将需要 O(n² log n) 时间。我觉得可能有更有效的方法。有任何想法吗？

4

1 回答 1

1

好的，我将尝试对此进行尝试。

背景知识：这个问题与k-最近邻有些关系。我不确定你是如何生成成对距离的，但是 kd 树非常擅长解决这类问题。

现在，即使您使用 kd 树，它也会有所帮助（您只查询您需要的内容，而不是对所有点进行排序）：在 O(N log N) 时间内构建树，然后为您想要的 K 个最近点要查询，每个都需要 O(log N) 时间。最后，您正在查看 O(N log N) + O(NK log N)。

好的，现在，实际的启发式部分。这将取决于您的数据，您可能想查看它们是靠在一起还是相距很远。但是，您可以尝试分而治之的方法，将飞机分成垃圾箱。当您需要找到最近的点时，找出您正在处理的点属于哪个 bin，然后您只使用相邻的 bin，并在需要更多点时探索更多的相邻 bin。

希望这会有所帮助，祝你好运。

于 2012-12-16T04:31:09.397 回答