4

问题：

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

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

  • 在此过程中，我们希望尽可能减少牺牲任何其他对的顶点之间的接近度。

  • 我不是在寻找最佳解决方案（如果它甚至严格存在/可以完成），只是一个可以相对快速计算的合理解决方案。

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

4

2 回答 2

4

解决这类问题（尤其是当 n 很大时）的常用方法是预先计算空间索引结构，例如kd 树或八叉树，并在它的帮助下执行最近邻搜索。通过八叉树的节点，可用点被放入bins，所以你可以确定它们是相互靠近的。您还可以最大限度地减少比较次数。

带有八叉树的实现草图：您需要一个 Node 类来存储其边界框。派生的 LeafNode 类最多存储少量点（例如 k = 20），这些点是通过插入函数添加的。派生的 NonLeafNode 类存储对 8 个子节点（可能是 Leaf 和 NonLeafNodes）的引用。

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

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

对于 kdtree 实现，请查看 wikipedia 页面，看起来非常简单。

于 2012-09-17T08:12:16.957 回答
4

由于您不是在寻找最佳解决方案，因此您可以考虑以下启发式方法。

对于每个点 p 计算两个点：分别离 p 最近和最远的最近邻和最远邻。现在让 q 是具有最大最远邻居的点（q 是输入中的极值点）。将 q 与其最近的邻居匹配，删除它们并递归计算剩余点的匹配。

这当然不是最优的，但它似乎在小输入集上做得相当好。如果您需要最佳解决方案，您应该阅读欧几里得匹配问题。

于 2012-09-17T03:56:18.877 回答