我一直在考虑 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)
,因为可以保证这些距离是大于当前已知的最小距离。
是否可以使用此类信息将 O(n²) 减少到 O(nlogn) 之类的东西?
如果我接受一种近似解,是否有可能将成本降低到接近 O(nlogn) 的程度?在这种情况下,我正在考虑一些基于强化学习的技术,该技术仅在强化数量达到无穷大时收敛到实际解决方案,但为小 n 提供了很好的近似值。
处理时间(用大 O 表示法衡量)并不是唯一的问题。保留大量先前计算的距离也可能是一个问题。
将这个问题想象成一个有 10⁸ 个点的集合。
我应该寻找什么样的解决方案?以前解决过这种问题吗?
这不是类问题或相关问题。我一直在想这个问题。
最佳答案
我建议使用源自快速解决 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,这些键在您定义的某个度量空间中“接近”。
我建议使用我的代码(或其背后的想法)来实现一个解决方案,您可以:
- 搜索每个叶节点的 HashMap 并在该小子集中找到最接近的键对。
- 在只考虑每个 HashMap 的“赢家”时,返回最接近的一对 Key。
这种解决方案是一种“分而治之”的方法,返回一个近似解决方案。
您应该知道这段代码有一个可调整的参数,该参数控制可以放置在单个 HashMap 中的键的最大数量。减小此参数会提高搜索速度,但会增加找不到正确解决方案的可能性,因为一个 Key 在 HashMap A 中,而第二个 Key 在 HashMap B 中。
此外,每个 HashMap 都关联一个“半径”。根据您希望结果的准确程度,您也许可以只搜索具有最大 hashMap.size()/radius 的 HashMap(因为此 HashMap 包含最高密度的点,因此它是一个很好的搜索候选者) 祝你好运
关于algorithm - 近似最近对算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20794090/