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

Question

我正在搜索一个长度为12的向量空间，其中包含条目0，1，2。

我有一千个好的向量，也有一千个坏的向量。，，

1. 。对于每个坏的向量，我需要找到最接近的好的向量。两个向量之间的距离就是不匹配的坐标数。好的向量并不是排列得特别好，它们“好”的原因在这里似乎没有什么帮助。我的首要任务是算法要快。

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

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

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

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

Answer 1

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

你能做的最基本的事情就是在好的向量上构建一个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   

最后一个优化可能是重新排序向量，以便在坏向量之间具有较高一致性的位置首先出现，并分担更多工作。

Answer 2

只是为了让事情保持正确，并确保你没有优化不必要的事情，在我的机器上，没有任何优化的蛮力方法需要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)定律：

​

​

Answer 3

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

如果您为该表中的每个条目分配一个32位字(这已经足够了)，那么该表将占用大约2MB空间，以换取几乎即时的“计算”。

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