c++ - 硬排序问题——我应该使用什么类型的算法？

Question

问题:

N 个节点通过范围从 0 到 1 的“接近度”因子相互关联，其中因子 1 表示两个节点没有任何共同点，0 表示两个节点完全相同。

如果两个节点都靠近另一个节点(即它们的因子接近于 0)，那么这并不意味着它们将靠近在一起，尽管从概率上讲它们确实具有更高的因子靠近在一起的机会。

-

问题:

如果集合中有另一个节点，则在尽可能短的时间内找到距离它最近的节点。

这不是家庭作业问题，这是我需要解决的现实世界问题 - 但我从未参加过任何算法类(class)等，所以我不知道我应该研究哪种算法。

我可以在添加另一个节点之前为所有节点编制索引并收集每个节点之间的接近度数据，但由于没有将所有节点与新节点进行比较，我无法提出有效的解决方案。任何想法或帮助将不胜感激:)

Answer 1

因为您的“接近度”指标服从三角不等式，您应该能够使用 BK-Trees 的变体组织你的元素。使它们适应实数应该只是选择一个区间来量化你的数字，否则就使用标准的 Bk-Tree 过程。可能需要进行一些实验 - 例如，您可能希望在沿着树向下移动时增加量化的分辨率。