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

Question

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

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

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

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

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

Answer 1

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