如何在{0,1,2} ^ 12中一遍又一遍地找到最近的向量

Question

我正在搜索长度为12的向量空间,条目为0,1,2.例如,一个这样的向量是
001122001122.我有大约一千个好的向量,以及大约一千个坏向量.对于每个坏矢量,我需要找到最接近的好矢量.两个向量之间的距离就是不匹配的坐标数.好的载体并没有特别好地排列,它们"好"的原因似乎没有帮助.我的主要优先事项是算法很快.

如果我进行简单的穷举搜索,我必须计算大约1000*1000的距离.这似乎很头脑.

如果我首先使用好的向量应用Dijkstra算法,我可以计算空间中每个向量的最近向量和最小距离,这样每个坏向量都需要一个简单的查找.但是空间中有3 ^ 12 = 531,441个向量,因此预计算是50万个距离计算.节省不多.

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

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

Answer 1

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

您可以做的最基本的事情是在好的向量上构建一个特里树，然后进行洪水填充，优先考虑几乎没有不匹配的分支。当附近有一个向量时，这会非常快，而当最近的向量很远时，就会退化为暴力。不错。

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

不能保证这是正确的，因为算法和代码都超出了我的想象：

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   

最终的优化可能是对向量重新排序，以便不良向量之间高度一致的位置排在第一位并分担更多工作。