V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
IanHo
V2EX  ›  算法

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

  •  
  •   IanHo · 2019-12-14 00:03:47 +08:00 · 3438 次点击
    这是一个创建于 1567 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    10 条回复    2019-12-14 09:26:11 +08:00
    opengps
        1
    opengps  
       2019-12-14 00:07:43 +08:00 via Android
    首先经纬度一定的值进行网格分类,粗略归类虽然有不足,但是起码都是小误差
    IanHo
        2
    IanHo  
    OP
       2019-12-14 00:09:48 +08:00
    @opengps 你好,假设经纬度都是有的话,能具体说说怎么进行网格分类吗?感谢
    HuLiY
        3
    HuLiY  
       2019-12-14 00:30:02 +08:00 via Android
    R 树可以快速求最近邻
    zhzy
        4
    zhzy  
       2019-12-14 00:31:58 +08:00 via iPhone
    有点像最近点对问题 跳过同类型的点只计算不同类型点对 但不清楚这是不是最优解法
    zhzy
        5
    zhzy  
       2019-12-14 00:41:28 +08:00 via iPhone
    @zhzy @zhzy 看错了,以为只需要找到一个最近的。应该更像是运输问题,把运费和产量设成一个比较大的数字就可以了
    min
        6
    min  
       2019-12-14 01:08:38 +08:00
    供应链优化问题
    em70
        7
    em70  
       2019-12-14 01:23:00 +08:00
    把一个城市画格子,6 格或者 9 格,每个格子里的送货点只由格子内的货仓送货,无需遍历全部货仓。比如[1,2,3,4]送货点由[a,b,c,d]负责送货,[4,5,6,7]送货点由[e,f,g,h]负责送货,这样计算量就大大下降了
    eason1874
        8
    eason1874  
       2019-12-14 01:30:41 +08:00
    用 空间查询 Spatial query,好像很多数据库本身就支持这个功能。
    shiny
        9
    shiny  
       2019-12-14 02:48:47 +08:00
    最简单的办法:Geohash
    sengxian
        10
    sengxian  
       2019-12-14 09:26:11 +08:00
    kd 树
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1018 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 19:24 · PVG 03:24 · LAX 12:24 · JFK 15:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.