我有N个移动设备/节点（例如100K），并定期获取其位置（纬度，经度）值。
一些设备“逻辑连接”到大约M个其他设备（例如10）。我的程序会定期比较每个设备与其逻辑连接的设备之间的距离，并确定该距离是否在阈值之内（例如100米）。
我需要一个健壮的算法来计算到逻辑连接设备的距离。
暴力破解方法的复杂度顺序为N * M或Θ（N2）
程序每3秒执行一次此操作（所有设备都在移动状态），因此每3秒进行100K * 10 = 3M的计算是不好的。
此操作有任何好的/经典算法吗？
（为简化说明，我省略了有关每个设备仅在逻辑上连接到M〜= 10个其他设备的详细信息。）
在空间上划分设备位置。如果您只对间隔小于100米的设备感兴趣，请考虑以下两种算法。
对于i = 1..N，j = 1..N，i！= j，计算设备i和j之间的距离。
对于i = 1..N，计算设备i所在的经度和纬度所在的网格单元，其中网格单元为100米见方。现在，对于所有非空网格单元，仅将该单元中的设备与同一单元或八个相邻单元之一中的设备进行比较。
该方法的数据结构基本上是从网格单元索引（s，t）到该网格单元中的设备列表的映射M。
第一种方法是幼稚的，将花费Θ（N 2）。假设存在一些“恒定的最大设备密度”，第二种方法在实践中将更接近Θ（N）。100米半径是相当小的。
第二种方法的伪代码如下所示。
M = {}
for i = 1..N
(s,t) = compute_grid_cell(i)
if ((s,t) not in M)
M[(s,t)] = []
M[(s,t)].push(i)
for i = 1..N
(s,t) = compute_grid_cell(i)
for s' in [s-1, s, s+1]
for t' in [t-1, t, t+1]
if (s',t') in M
for j in M[(s',t')]
if i != j and distance(i, j) < 100
report (i,j) as a pair of devices that are "close"
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句