algorithm - 近似最近对算法

Question

我一直在考虑 closest pair problem 的变体其中唯一可用的信息是已经计算出的一组距离(我们不允许根据 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⁸ 个点的集合。

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

这不是类问题或相关问题。我一直在想这个问题。

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 的“赢家”时，返回最接近的一对 Key。

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

您应该知道这段代码有一个可调整的参数，该参数控制可以放置在单个 HashMap 中的键的最大数量。减小此参数会提高搜索速度，但会增加找不到正确解决方案的可能性，因为一个 Key 在 HashMap A 中，而第二个 Key 在 HashMap B 中。

此外，每个 HashMap 都关联一个“半径”。根据您希望结果的准确程度，您也许可以只搜索具有最大 hashMap.size()/radius 的 HashMap(因为此 HashMap 包含最高密度的点，因此它是一个很好的搜索候选者)祝你好运