如何以某種方式繪製設備的物理位置，以便我可以找到給定設備附近的所有設備？

Question

下面是一個例子佈局：

A 
B  C 

D 
    G F 
E 
      H 
K  I 
    J 

每個字母代表一個物理設備。在這個例子中，你可以看到，A附近既B和C。 B附近既A，D和可能C。

我想將每個設備到一個數據庫和配對所有可能的關係。例如：

device | siblings 
-------+--------- 
A  | B,C 
-------+--------- 
B  | A,D,C 
-------+--------- 
D  | B,G,E 

這樣，當我需要查找附近設備D我可以這樣做：

SELECT siblings FROM devices WHERE device = 'D'; 

siblings = siblings.split(',') 

for sibling in siblings: 
    # do something with each sibling device 

我不知道是否有一個更好的辦法。考慮到可能有大量的設備，我覺得這種方法可能會變得混亂，並且可能是錯誤（跟蹤命令分隔的兄弟姐妹列表的人爲錯誤）。

有什麼建議嗎？

Answer 1

你應該檢查出Nearest-Neighbour Search維基百科的文章更多的想法，但最好的答案很可能取決於你將要共事的設備數量。

KD-Trees和R-Trees即使在大量的設備上也會給你很好的性能，但是它們需要很多編程/調試（如果你必須自己做，至少 - 它們是相當知名的數據結構，所以你可能在某處找到一個庫）。

如果你只有少量的設備（「小」取決於各種各樣的東西，真的），跳過一個特殊的數據結構的複雜性可能會更快，只是通過所有設備進行線性搜索您的設備。如果你只是偶爾執行這樣的查詢，那麼緩慢的線性搜索可能仍然值得使用簡潔明瞭的代碼。

最後：以上所有選項假設所有設備都「連接」到另一個。如果只有一些設備相互連接，請嘗試使用Adjacency List來存儲這些連接，並按距離排序 - 這應該比上述任何一項都快。

希望這會有所幫助！