4

我有 2 组节点 - 组 A 和组 B。每组的大小为 25,000。

我得到一个百分比（比如说 20%）。我需要找到最小距离，以使 Set A 中 20% 的节点在 Set B 中任何节点的距离内。

解决方案：

找到集合 A 中最接近集合 B 中任何节点的 20%。答案是那 20% 中离集合 B 中任何节点最远的节点。

蛮力解决方案：

        foreach (Node a in setA)
        {
            a.ShortestDistance = infinity;
            foreach (Node b in setB)
            {
                if (a.DistanceTo(b) < a.ShortestDistance)
                {
                    a.ShortestDistance = a.DistanceTo(b);
                }
            }
        }
        setA.SortByShortestDistance();
        return setA[setA.Size * 0.2];

这行得通，但它所花费的时间是疯狂的。（O（n^2 + 排序）我认为？）

我怎样才能加快速度？如果可能的话，我想打 O(n)。

4

2 回答 2

1

您可以选择两个集合中较小的一个，并从中构建一个结构来回答最近邻查询 - http://en.wikipedia.org/wiki/Cover_tree没有对基础指标做出很多假设，因此它应该与正弦/大圆。

完成此操作后，最简单的做法是获取较大集合中的每个成员，在较小集合中找到与其最近的邻居，然后对距离进行排序或http://en.wikipedia.org/wiki/Quickselect . 如果您修改了查找操作以提前返回而没有找到任何东西，如果最近的对象必须比阈值距离更远，并且您对距离有一个粗略的了解，您可能会节省一些时间。

您可以通过事先对两组中的随机样本执行相同的操作来获得一个粗略的想法。如果您的猜测有点太高，您只需再排序几个最近邻距离即可。如果您的猜测有点太低，您只需对最近邻操作提前返回而没有找到任何东西的那些点重复查找操作。

于 2014-06-25T05:29:15.510 回答
1

以下是可能提高速度的算法：-

  1. 将您的 (lat,long) 对转换为以地心为原点的笛卡尔坐标系 (x,y,z)
  2. 笛卡尔坐标中 (x,y,z) 之间的距离是球坐标中实际距离的下限。
  3. 构造以分离setA 和 setB 的3d 树。
  4. 对于 setA 中的每个节点 a，在 setB 的 3d 树中搜索最近的邻居，平均情况下为 O(logN)。
  5. 那么最近邻居的距离将是与最近邻居的距离。
  6. 然后像你所做的那样对 setA 进行排序。

时间复杂度：-

在平均情况下： O(n*logn)

在最坏的情况下： O(n^2)

于 2014-06-25T05:26:39.157 回答