c++ - 给定偶数个顶点，如何根据接近度找到最佳对集？

Question

问题:

• 我们在 3D 欧氏空间中有一组 n 个顶点，这些顶点的个数是偶数。

• 我们想根据它们的接近程度将它们配对。换句话说，我们希望能够找到一组顶点对，其中每对顶点中的顶点尽可能靠近。

• 在执行此操作时，我们希望尽可能减少牺牲任何其他对的顶点之间的接近度。

• 我不是在寻找最最优的解决方案(如果它严格存在/可以做到)，只是一个可以相对快速计算的合理的解决方案。

一种相对糟糕的蛮力方法涉及选择一个顶点并遍历其余顶点以找到其最近的邻居，然后重复直到没有剩余。当然，当我们接近列表的末尾时，最近的顶点可能离得很远，但这是唯一的选择，因此在上面的第三点上这可能会严重失败。

Answer 1

解决此类问题(尤其是当 n 很大时)的一种常见方法是预先计算空间索引结构，例如 kd tree或 octtree并搜索 nearest neighbors在它的帮助下。通过八叉树的节点，将可用的点放入箱子中，因此可以确定它们相互接近。您还可以最大限度地减少比较次数。

八叉树的实现草图:您需要一个存储其边界框的 Node 类。派生的 LeafNode 类存储少量的点，最多为最大值(例如 k = 20)，并添加了插入功能。派生的 NonLeafNode 类存储对 8 个子节点(可能是 Leaf 和 NonLeafNode)的引用。

树由一个根节点表示，所有的插入和查询都从这里开始。通过将前 k 个点插入 LeafNode 来构建树。如果插入第k+1个点，则边界框被分割成8个子框，并将包含的点排序到其中。当前的 LeafNode 被一个有 8 个子节点的 NonLeafNode 代替。这是迭代的，直到所有点都在树中。

对于最近邻搜索，通过与边界框进行比较，从根节点开始遍历树。如果查询点在节点的边界框内，则遍历进入该节点。请注意，如果找到最近的候选者，还需要检查八叉树中的相邻节点。

对于 kdtree 实现，请查看维基百科页面，看起来非常简单。