2

有人可以建议一种算法来找出最短距离的一对未排序的共线点吗？

我有一个解决方案可以在 O(nlogn) 中做到这一点，只需在 2D 中做最近的一对点并应用于该线。但是，这可以更有效地完成吗？

4

4 回答 4

3

恐怕你必须对点进行排序，这至少需要 O(n*log(n)) 时间（除非你可以使用桶排序），所以我怀疑你是否找到了更快的算法。

于 2011-08-09T16:20:08.060 回答
2

请注意，您始终可以通过执行旋转变换将 2D 情况简化为 1D 情况。

不幸的是，在一般情况下，我认为你不能比 O(nlogn) 做得更好。您最好的选择是对它们进行排序，然后遍历列表。

于 2011-08-09T16:21:50.793 回答
1

这是平面中最近点对的预期 O(n) 时间算法。
它来自 Kleinberg 和 Tardos 的算法设计书。

这是一个类似 Python 的伪代码

def Bucket(point, buck_size):
  return int(point[0] / buck_size, int(point[1] / buck_size)

def InsertPoint(grid, point, buck_size):
  bucket = Bucket(point, buck_size)
  grid[buck_size].append(point)

def Rehash(points, limit, buck_size):
  grid = collections.defaultdict(list)
  for first limit point in points:
    InsertPoint(grid, point, buck_size)
  return grid

# return new distance if point is closer than buck_size to any point in grid,
# otherwise return inf
def Probe(grid, point, buck_size):
  orig_bucket = Bucket(point)
  for delta_x in [-1, 0, 1]:
    for delta_y in [-1, 0, 1]:
      next_bucket = (orig_bucket[0] + delta_x, orig_bucket[1] + delta_y)
      for cand_point in grid[next_bucket]:  
        # there at most 2 points in any cell, otherwise we rehash 
        # and make smaller cells.
        if distance(cand_point, point) < buck_size):
          return distance(cand_point, point)
  return inf

def ClosestPair(points):
   random_shuffle(points)
   min_dist = distance(points[0], points[1])
   grid = Rehash(points, 2, min_dist)
   for i = 3 to n
     new_dist = Probe(points, i, grid)
     if new_dist != inf:
        # The key to the algorithm is this happens rarely when i is close to n,
        # and it's cheap when i is close to 0.
        grid = Rehash(points, i, new_dist)
        min_dist = new_dist
     else:
        InsertPoint(point, grid, new_dist)
   return min_dist

每个邻居候选搜索都是 O(1)，用几个哈希完成。该算法预计会进行 O(log(n)) 次重新哈希，但每次都需要与 i 成正比的时间。需要重新散列的概率是 2/i（== 这个特定点是迄今为止最近对的概率是多少？），在检查 i 个点之后，这个点在最近的对中的概率。因此，预期成本为

sum_i=2^n Prob[Rehash at step i] * Cost(rehash at i) + O(1) =

sum_i=2^n 2/i * i + O(1) =

sum_i=2^n 2 + O(1) =

在）

于 2011-08-09T16:30:47.820 回答
0

我只会为您有一个有限范围内的数字列表的情况提出一个解决方案。

如果所有数字都在 O(ba) < O(nlog(n)) 的范围 [a,b] 内，则可以在 O(max(ba,n)) 中进行。

创建一个大小为 ba 的数组。您可以将其全部初始化为 0（在 O(1) 中有一个算法可以做到这一点）

查看您的列表，对于每个值 x，将“1”放入单元格中的位置 xa。

然后检查您的新数组，并计算具有值的单元格之间的距离。

通过这种方式，您可以找到最小距离，并通过它们在新数组中的索引获取实际值。

于 2011-08-09T16:14:48.143 回答