近似最近点对算法

Question

我一直在思考最近点对问题的一个变体，该问题只提供已经计算出的距离集合作为可用信息（不允许按照x坐标对点进行排序）。

考虑4个点（A、B、C、D），以及以下距离：

dist(A,B) = 0.5
dist(A,C) = 5
dist(C,D) = 2

在此示例中，我不需要评估dist(B,C)或dist(A,D)，因为可以保证这些距离大于当前已知的最小距离。

1. 有可能使用这种信息将O(n²)减少到类似O(nlogn)吗？

2. 如果接受某种近似解决方案，有可能将成本降低到接近O(nlogn)吗？在这种情况下，我考虑基于强化学习的技术，只有当强化次数趋于无穷大时才会收敛到真实解决方案，但对于较小的n提供了极佳的近似。

3. 处理时间（通过大O符号衡量）并非唯一的问题。保留大量先前计算出的距离也可能成为问题。

4. 想象一下对于具有10⁸个点的集合的这个问题。

我该寻找什么样的解决方案？这种问题以前解决过吗？

这不是教室问题或相关问题。 我一直在思考这个问题。

- DanielTheRocketMan

---

鉴于 dist(A,B) = 0.5; dist(A,C) = 5，B 和 C 可能最接近的情况是当 A、B 和 C 共线，并且顺序为 A、B、C。这导致 dist(B,C) >= 4.5，这比当前最短路径更长，因此无需评估。 - Trojan

@PhamTrung 这取决于这10^8个点的分布情况。如果这些点非常密集分布，那么您可能是正确的。值得思考。 - Trojan

运行时间不仅取决于点的分布，还取决于您考虑（一对）它们的顺序，不幸的是，这意味着最坏情况下的运行时间将为O(n^2)，假设“从a到b的距离？”是我们允许的唯一查询。例如，如果您在（0,0）处有一个点，在（d,0）处有另一个点（其中d是接近0的某个小值），并且n-2个点均匀分布在半径为r且以（0,0）为中心的圆周上，其中r足够大，使得d小于圆上任意两点之间的距离，则... - j_random_hacker

最近邻对将是(0, 0)和(d, 0) - 但没有其他东西可以“告诉”我们提前考虑这一点，因此在最坏的情况下它将被最后考虑。在这种最坏情况下，我们需要首先考虑O(n^2)个其他点：圆上每个点与其对角线相反的点，然后与该点两侧的点进行比较，最终与其两侧的邻居进行比较。 - j_random_hacker

这不是一个证明，甚至不是一个草图，但我认为它可以作为一个起点。在维度等于点数的情况下，最坏情况下比较O(n^2)个点对的必要性更容易建立。 - j_random_hacker

Answer 1

我建议使用快速解决k最近邻搜索的思路。

M-Tree数据结构：（参见http://en.wikipedia.org/wiki/M-tree和http://www.vldb.org/conf/1997/P426.PDF）旨在减少执行“最近邻居”查找所需的距离比较次数。

个人而言，在线上找到的M-Tree实现都无法令我满意（请看我的关闭帖子Looking for a mature M-Tree implementation），所以我自己动手写了一个。

我的实现在这里：https://github.com/jon1van/MTreeMapRepo

基本上，这是一棵二叉树，其中每个叶节点包含一个HashMap，其中包含在您定义的某个度量空间中“接近”的键。

我建议使用我的代码（或其背后的思想）来实现以下解决方案：

1. 搜索每个叶节点的HashMap，并在该小子集中找到最接近的键对。
2. 仅考虑每个HashMap的“获胜者”时，返回最接近的键对。

这种解决方案的风格将是一种“分而治之”的方法，它返回一个近似解。

您应该知道，此代码有一个可调参数，用于管理可以放置在单个HashMap中的最大键数。减少此参数将增加搜索速度，但会增加正确解找不到的概率，因为一个键在HashMap A中，而另一个键在HashMap B中。

此外，每个HashMap都与一个“半径”相关联。根据您想要的精度，您可能只能搜索具有最大hashMap.size()/radius的HashMap（因为该HashMap包含最高密度的点，因此它是一个很好的搜索候选者）祝你好运！

- Ivan

---

这是一个非常简洁的数据结构。谢谢分享！ - Andy Jones

Answer 2

如果您只有样本距离，而没有平面上可以操作的原始点位置，那么我怀疑您的限制在O(E)。 具体来说，根据您的描述，任何有效的解决方案都需要检查每条边，以排除它对问题有什么有趣的贡献，同时检查每条边并取最小值可解决该问题。

平面版本绕过O(V^2)，通过使用平面距离推导出对一组边的限制，从而使我们避免需要查看大部分边权重。

- RichardPlunkett

---

抱歉，@RichardPlunkett，我没有很好地理解你的说法！你到底指的是什么是“边缘”？它们是先前计算的距离吗？我也不明白第二个说法！ - DanielTheRocketMan

他所说的是O(nlogn)解决方案仅适用于平面情况。在一般情况下，您有O(E)的输入。除非您完全读取输入（这需要O(E)时间），否则无法获得解决方案。 - ElKamina

Answer 3

使用与空间分割相同的思路。通过选择两个点并将集合分成两部分，将给定点集递归地分裂，靠近第一个点和靠近第二个点的点。这与通过两个选定点之间的线划分点相同。

这会产生（二进制）空间分割，可以使用标准最近邻搜索算法。

- Ante