algorithm - 查询最近的范围

Question

我有两个集合，A 和 B。这些集合由 N 个维度点组成并有序（N<10）。我需要找到 B 到 A 的最近部分。假设最近的部分是 B1。B1 中的点数应与 A 相同，且 B1 中所有点到 A 的距离之和应最小。

我检查了kd树。它只有助于在集合中找到最近的点。那么有没有一种算法可以快速找到最近的范围？

谢谢。

Answer 1

我相信你在这里只需要一个n最近邻搜索算法，它是最近邻算法的简单扩展。对集合 A 中的每个点运行此操作并最小化总和。

该算法在本文（“关于 kd-trees 的入门教程”）中有所提及。对多个最近邻的扩展只是简要提及，但应该非常清楚。这是我成功实现修改算法的文章。

可以在此处访问 C# 中的参考实现，该实现带有注释并包含相关的单元测试。它应该很容易适应您选择的命令式语言。