在數字列表中查找數字對最接近匹配的算法

Question

我有一個具有非常特定算法需求的程序。我需要搜索一個數字列表來查找列表中與一對搜索數字最匹配的位置。我將「最佳排列」定義爲該排列的差異總和。

舉例來說，如果我有一個數字的下面的列表：

12 18 -20 45 11 34 6 -8 

...和我在尋找一對，則算法應該返回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 -- -- -- 

索引 - 簡單地找到用於每個對準的差和記住最好。但是，這對我的程序來說是一個瓶頸，所以任何改進都會有所幫助。

我提出的唯一優化有點微不足道：如果對於對中的第一個數字的差異超過當前最佳總差異，則跳到下一個對齊而不打擾檢查第二個數字對。它有幫助，但不是很多。

如果相關，列表會被多次搜索，所以如果有某種初始排序會加速未來的搜索，我會很感興趣。

我很感激任何人的想法，即使它只是一個鏈接到維基百科頁面的相關算法。謝謝！

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

如果您可以負擔得起存儲，也可以使用網格解決方案：在點上繪製方形網格並將它們分組。對於查詢對，請在網格中找到它，並從相鄰瓦片的同心「圓圈」中探索此瓦片，並與它們包含的點進行徹底比較。

Answer 2

您可以保留一個輔助數組，您在中點01​​和寬度w加上列表中的原始索引描述對(l, u)。對該數組進行排序並使用二進制搜索來查找最接近的中心點匹配。那麼你最好的陣容應該在那場比賽的附近。

你的標準

d = abs(l1 - l2) + abs(u1 - u2) 

將隨即成爲

d = abs(dm - dw/2) + abs(dm + dw/2), dm = m1 - m2, dw = w1 - w2 

剩下的你應該如何接近比賽由二進制搜索發現看這個問題。你可以從那裏開始，在列表中向前和向後工作，直到中間點之間的差異大於你的最佳距離。

Answer 3

正如@Yves_Daoust所說，你可以在列表中表示成對的二維點。 然後，您可以將它們放在四叉樹http://en.wikipedia.org/wiki/Quadtree中。搜索最近的任意點在這個結構中以O（lg（n））時間執行。