代码之家 › 专栏 › 技术社区 › Josephine

如何在{0,1,2}^12中反复查找最近的向量

dijkstra search math algorithm

Josephine · 技术社区 · 14 年前

我正在搜索一个长度为12的向量空间,其中有0,1,2个条目。例如,其中一个向量是
001122001122。我有一千个好的媒介,还有一千个坏的媒介。对于每个坏向量,我需要找到最近的好向量。两个向量之间的距离只是不匹配的坐标数。好的向量并没有特别好的排列,它们“好”的原因在这里似乎没有帮助。我的首要任务是算法要快。

如果我做一个简单的穷举搜索,我必须计算大约1000*1000的距离。这看起来很愚蠢。

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

你能帮我想出更好的办法吗?

编辑:既然人们认真地问他们“好”的原因是什么:每个矢量代表六个等边三角形的六边形图像的描述,这是三维立方体排列的二维图像(想想广义Q-bert)。等边三角形是立方体(45-45-90)面的一半,倾斜成透视图。六个坐标描述三角形的性质(感知地板、左墙、右墙),六个坐标描述边缘的性质(感知连续性、两种感知不连续性)。1000个好向量是那些表示六边形的向量,当在透视图中看到立方体时可以看到它们。搜索的原因是对充满三角形的十六进制映射应用局部校正。。。

5 回复 | 直到 14 年前

Craig Gidney Mihai 14 年前

这听起来很像拼写检查器要做的事情。诀窍通常是滥用 tries .

你能做的最基本的事情是在好的向量上建立一个trie,然后在很少不匹配的情况下对分支进行洪水填充优先级排序。当有一个附近的向量时,这将非常快;当最近的向量非常远时,这将退化为蛮力。不错。

但我认为你可以做得更好。共享相同前缀的错误向量将执行相同的初始分支工作,因此我们也可以尝试共享。所以我们也在坏向量上建立了一个trie,sortof同时完成它们。

没有人保证这是正确的,因为算法和代码都是在我的头脑之外:

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

最后一个优化可能是对向量重新排序,使坏向量之间高度一致的位置优先,并共享更多的工作。

Dr. belisarius 14 年前

为了保持正确的观点,并确保你没有优化不必要的东西,暴力的方法,没有任何优化需要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)定律:

alt text

mokus 14 年前

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

如果给表中的每个条目一个32位的单词(这已经足够了),那么您将看到表的大小约为2 MB,这就相当于瞬时的“计算”。

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

jtdubs 14 年前

我的计算几何很粗糙,但似乎你应该能够:

计算 Voronoi diagram 为了你的一组好向量。
计算 BSP tree 对于图表的单元格。

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

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

编辑:我刚刚注意到你用的是汉明距离而不是欧几里德距离。我不知道怎么才能适应这种限制。对不起的。

Axn 14 年前

假设向量的压缩表示,一个距离计算(比较一个好向量和一个坏向量以得出距离)可以在大约20个时钟周期或更少的时间内完成。因此,可以在2000万个周期或(假设为2GHz cpu)0.01秒内完成一百万个这样的距离计算。这些数字有帮助吗?

注:20个周期是保守的高估值。