3

我一直在考虑最近对问题的一个变体，其中唯一可用的信息是已经计算的距离集（我们不允许根据它们的 x 坐标对点进行排序）。

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

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

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

  1. 是否可以使用这种信息将 O(n²) 减少到 O(nlogn) 之类的东西？

  2. 如果我接受一种近似解决方案，是否可以将成本降低到接近 O(nlogn) 的程度？在这种情况下，我正在考虑一些基于强化学习的技术，该技术仅在强化数量达到无限时收敛到真实解决方案，但为小 n 提供了很好的近似值。

  3. 处理时间（用大 O 表示法衡量）不是唯一的问题。保留大量先前计算的距离也可能是一个问题。

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

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

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

4

3 回答 3

2

如果您只有样本距离，而不是可以操作的平面中的原始点位置，那么我怀疑您的界限为 O(E)。具体来说，从您的描述看来，任何有效的解决方案都需要检查每条边以排除它有有趣的说法，同时，检查每条边并取最小的边可以解决问题。

平面版本绕过 O(V^2)，通过使用平面距离来推断边缘集的限制，使我们能够避免需要查看大多数边缘权重。

于 2013-12-27T04:01:40.213 回答
2

我建议使用从快速解决 k-最近邻搜索中得出的想法。

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

就个人而言，我在网上找不到我满意的 M-Tree 实现（请参阅我的封闭线程寻找成熟的 M-Tree 实现），所以我推出了自己的。

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

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

我建议使用我的代码（或它背后的想法）来实现一个解决方案，您可以在其中：

  1. 搜索每个叶节点的 HashMap 并在该小子集中找到最接近的 Key 对。
  2. 当只考虑每个 HashMap 的“赢家”时，返回最接近的 Key 对。

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

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

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

于 2013-12-31T01:22:09.390 回答
1

使用与空间分区相同的想法。通过选择两个点并将集合分成两部分，递归地拆分给定的点集，靠近第一个点的点和靠近第二个点的点。这与通过在两个选定点之间穿过的线分割点相同。

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

于 2013-12-30T23:01:20.750 回答