9

我正在搜索长度为 12 的向量空间，条目为 0、1、2。例如，一个这样的向量是
001122001122。我有大约一千个好的向量和大约一千个坏向量。对于每个坏向量，我需要找到最接近的好向量。两个向量之间的距离只是不匹配的坐标数。好的向量排列得不是特别好，它们“好”的原因在这里似乎没有帮助。我的主要优先事项是算法要快。

如果我做一个简单的详尽搜索，我必须计算大约 1000*1000 的距离。这似乎很笨拙。

如果我首先使用好的向量应用 Dijkstra 算法，我可以计算空间中每个向量的最近向量和最小距离，因此每个坏向量都需要简单的查找。但是空间中有 3^12 = 531,441 个向量，因此预计算是一百万次距离计算。没有多少储蓄。

你能帮我想一个更好的方法吗？

编辑：因为人们认真地问是什么让他们“好”：每个向量代表六个等边三角形的六边形图片的描述，这是立方体 3D 排列的 2D 图像（想想广义 Q-bert）。等边三角形是立方体 (45-45-90) 面的一半，倾斜成透视图。其中六个坐标描述了三角形的性质（感知的地板、左墙、右墙），六个坐标描述了边的性质（感知的连续性，两种感知的不连续性）。1000 个好的向量是那些代表透视立方体时可以看到的六边形的向量。搜索的原因是对充满三角形的十六进制地图应用局部校正......

4

5 回答 5

4

只是为了让事情保持正确，并确保你没有优化不必要的事情，没有任何优化的蛮力方法在我的机器上需要 12 秒。

Mathematica 中的代码：

bad = Table[RandomInteger[5, 12], {1000}];
good = Table[RandomInteger[2, 12], {1000}];
distance[a_, b_] := Total[Sign@Abs[a - b]];

bestMatch = #[[2]] & /@ 
   Position[
    Table[Ordering@
      Table[distance[good[[j]], bad[[i]]], {j, Length@good}], {i, 
      Length@bad}], 1] // Timing

如您所料，时间遵循 O(n^2) 定律：

替代文字

于 2010-11-19T03:28:28.507 回答
1

这听起来很像拼写检查器必须做的事情。诀窍通常是滥用尝试。

您可以做的最基本的事情是在好的向量上构建一个 trie，然后对几乎不匹配的分支进行泛洪填充。当有附近的向量时，这将非常快，而当最近的向量很远时，这将退化为蛮力。不错。

但我认为你可以做得更好。共享相同前缀的坏向量将执行相同的初始分支工作，因此我们也可以尝试共享它。因此，我们还对坏向量构建了一个 trie，然后一次性完成它们。

不能保证这是正确的，因为算法和代码都在我的脑海中：

var goodTrie = new Trie(goodVectors)
var badTrie = new Trie(badVectors)
var result = new Map<Vector, Vector>()
var pq = new PriorityQueue(x => x.error)
pq.add(new {good: goodTrie, bad: badTrie, error: 0})
while pq.Count > 0
  var g,b,e = q.Dequeue()
  if b.Count == 0: 
      //all leafs of this path have been removed
      continue
  if b.IsLeaf:
      //we have found a mapping with minimum error for this bad item
      result[b.Item] = g.Item
      badTrie.remove(b) //prevent redundant results
  else:
      //We are zipping down the tries. Branch to all possibilities.
      q.EnqueueAll(from i in {0,1,2}
                   from j in {0,1,2}
                   select new {good: g[i], bad: b[j], error: e + i==j ? 0 : 1})

return result

最后的优化可能是对向量进行重新排序，以便在坏向量之间具有高度一致性的位置首先出现并共享更多工作。

于 2010-11-19T04:07:54.733 回答
1

3^12 不是一个很大的搜索空间。如果速度很重要而算法的通用性不是，您可以将每个向量映射到 0..531440 范围内的 int 并将其用作“最近良好向量”的预先计算表的索引。

如果您为该表中的每个条目提供一个 32 位字（这绰绰有余），您将看到大约 2 MB 的表，以换取几乎瞬时的“计算”。

编辑：这与问题建议的预计算没有太大区别，但我的观点是，根据应用程序，这样做不一定有任何问题，特别是如果您在应用程序运行之前进行所有预计算。

于 2010-11-19T14:27:42.403 回答
0

我的计算几何非常粗糙，但您似乎应该能够：

  1. 为你的一组好的向量计算Voronoi 图。
  2. 计算图表单元格的BSP 树。

Voronoi 图将为每个包含最接近该向量的所有点的好的向量提供一个 12 维凸包。

BSP 树将为您提供一种快速的方法来确定向量位于哪个单元格内，从而确定它最接近哪个好的向量。

编辑：我刚刚注意到您使用的是汉明距离而不是欧几里得距离。我不确定如何调整它以适应该约束。对不起。

于 2010-11-19T03:16:41.970 回答
0

假设向量的打包表示，一个距离计算（比较一个好的向量和一个坏的向量以产生距离）可以在大约 20 个时钟周期或更短的时间内完成。因此，可以在 2000 万个周期或（假设 2GHz cpu）0.01 秒内完成一百万次这样的距离计算。这些数字有帮助吗？

PS：- 20 个周期是保守的高估。

于 2010-11-19T17:26:38.053 回答