一个计算最短距离的问题想请教大家

[IanHo]

有一个送货点 A 和三个仓库甲乙丙，四个点的坐标都是已知道的，那自然就能算出 A 到甲乙丙哪个仓库距离最近了。

那么现在有 N 个不同的送货点和 M 个仓库，怎么为这一批送货点选出各自最近的仓库呢？

目前我的方案比较蠢，一个一个地计算距离。所以想问下各位大佬，有没有这方面的算法或者优化方案之类的，可以减少计算量，提高效率。小弟在此谢过大家了！🙏🙏🙏

[opengps]

首先经纬度一定的值进行网格分类，粗略归类虽然有不足，但是起码都是小误差

[IanHo]

@opengps 你好，假设经纬度都是有的话，能具体说说怎么进行网格分类吗？感谢

[HuLiY]

R 树可以快速求最近邻

[zhzy]

有点像最近点对问题 跳过同类型的点只计算不同类型点对 但不清楚这是不是最优解法

[zhzy]

@zhzy @zhzy 看错了，以为只需要找到一个最近的。应该更像是运输问题，把运费和产量设成一个比较大的数字就可以了

[min]

供应链优化问题

[em70]

把一个城市画格子，6 格或者 9 格，每个格子里的送货点只由格子内的货仓送货，无需遍历全部货仓。比如[1,2,3,4]送货点由[a,b,c,d]负责送货，[4,5,6,7]送货点由[e,f,g,h]负责送货,这样计算量就大大下降了

[eason1874]

用 空间查询 Spatial query，好像很多数据库本身就支持这个功能。

[shiny]

最简单的办法：Geohash

[sengxian]

kd 树