在数字列表中查找数字对最接近匹配的算法

Question

我有一个具有非常特定算法需求的程序。我需要搜索数字列表以找到列表中与一对搜索数字最匹配的位置。我将“最佳对齐”定义为该对齐处差异的总和。

例如，如果我有以下数字列表:

12  18 -20  45  11  34   6  -8

...并且我正在搜索44 13对，那么算法应该返回3，因为这种对齐方式是最好的(总差值只有5)，而3是对齐开始位置的索引

index:             0   1   2   3   4   5   6   7
list:             12  18 -20  45  11  34   6  -8
search alignment: --  --  --  43  14  --  --  -- 
difference:       --  --  --   2   3  --  --  -- 

我目前正在使用一种明显的蛮力方法 - 只需找到每个对齐的差异并记住最好的。但是，这对我的程序来说是一个瓶颈，因此任何改进都会有所帮助。

我提出的唯一优化有点微不足道:如果对于对齐来说，对中第一个数字的差异超过当前最佳总差异，则跳到下一个对齐，而不必检查对中的第二个数字。有帮助，但效果不大。

如果相关，列表会被多次搜索，因此如果有某种初始排序可以加快 future 的搜索速度，我会很感兴趣。

我很感激任何人的任何想法，即使它只是相关算法的维基百科页面的链接。谢谢!

Answer 1

您可以将此问题重新定义为 2D 中的最近邻搜索。获取所有数字对并将它们视为 2D 平面上的点。您的距离函数称为 1-范数(绝对差之和)。通过您的查询对，您正在寻找最近的点。

因此，您正在寻找一种使用 1 范数距离进行二维最近邻搜索的快速解决方案。众所周知，在需要 O(N) 存储(构建 Voronoi 图)的 O(N.Log(N)) 预处理之后，所有查询都可以在 O(Log(N)) 时间内得到答复。

或者(为了更简单的实现)，您可以使用 2D 树(2D 维度的 kD 树)。 http://en.wikipedia.org/wiki/Kd-tree

如果您能负担得起存储空间，也可以使用网格解决方案:在您的点上绘制一个方形网格，并将它们按图 block 分组。对于查询对，在网格中找到它，并从该图 block 开始探索相邻图 block 的同心“圆圈”，并与它们包含的点进行详尽的比较。