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

由聚餐想到的一个距离算法问题

  •  
  •   JCZ2MkKb5S8ZX9pq · 2019-01-18 13:17:17 +08:00 · 3432 次点击
    这是一个创建于 2126 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背景

    • 年底老同学要聚餐了。
    • 组织者定了一个离他近,但偏离市中心的点。

    需求

    • 已知参加各人的坐标,就当是[(x1,y1), (x2,y2), ...]好了。
    • 假设聚会在某一个点,该点到各人坐标的距离[d1,d2,...]
    • sum(d)为最小值时,该点的坐标。
    • 也就是在哪里聚,社群的总通勤距离最小。

    进阶

    • 假设过程中,统计效率用的不是直线距离,而是通勤时间。难解嘛?
    第 1 条附言  ·  2019-01-18 15:18:36 +08:00

    感谢@icylogic ,让我找到了这个,就直译为 [几何中位数] 。
    Geometric median - Wikipedia

    至于纠结于聚餐具体细节的,拜托有点数学的情趣。
    这个问题接近于商业/设施选址,物流提效,等等方面。
    咱们好好玩数学游戏,不玩文字游戏哈。┑( ̄▽ ̄)┍

    24 条回复    2019-01-18 18:42:44 +08:00
    TimePPT
        1
    TimePPT  
       2019-01-18 13:21:08 +08:00 via iPhone   ❤️ 1
    聚餐你还得考虑聚会地点环境,个人口味等等
    LadyChunsKite
        2
    LadyChunsKite  
       2019-01-18 13:24:31 +08:00
    根据路网数据计算出每个人的 service area,再叠加一下得到最小的区域。
    http://desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/service-area.htm
    Vegetable
        3
    Vegetable  
       2019-01-18 13:25:33 +08:00
    穷举法可破
    进价成通勤时间好像也没什么区别,只是多了找出两点最短时间这个任务吧.
    deletelazy
        4
    deletelazy  
       2019-01-18 13:26:14 +08:00 via iPhone
    这不就是最小生成树问题吗
    icylogic
        5
    icylogic  
       2019-01-18 13:27:00 +08:00 via iPhone   ❤️ 1
    一个典型的最优化问题。

    https://en.m.wikipedia.org/wiki/1-center_problem
    LadyChunsKite
        6
    LadyChunsKite  
       2019-01-18 13:28:12 +08:00
    有点像商业选址。我有 N 个门店在市区(老同学),现在想要租一个大仓库(饭店),统筹货物调拨。
    希望到各个门店的通勤时间之和最短。当然还要把租金,人力成本,道路限行等各种因素考虑进来。
    zsdroid
        7
    zsdroid  
       2019-01-18 13:35:21 +08:00
    万一算出来的最优坐标是个 wc 怎么办?
    lance6716
        8
    lance6716  
       2019-01-18 14:04:35 +08:00 via Android
    上边好多的都在说什么…这不是解极小值吗,偏导等于零
    geelaw
        9
    geelaw  
       2019-01-18 14:06:46 +08:00 via iPhone
    如果用曼哈顿距离那非常简单…就是横纵坐标都取中位数
    JCZ2MkKb5S8ZX9pq
        10
    JCZ2MkKb5S8ZX9pq  
    OP
       2019-01-18 14:43:20 +08:00
    @icylogic 通过你这个 wiki,我找到了一个好像完全一致的。
    [Geometric median - Wikipedia]( https://en.m.wikipedia.org/wiki/Geometric_median)
    xiangyuecn
        11
    xiangyuecn  
       2019-01-18 14:58:20 +08:00
    不会算法,想到一种极端

    共 10 个人,9 个在学校,另一个在 1000 公里外,目测也就是选学校周边聚餐总距离最小,那个远的自己一个人要动,其他不用动。
    虽然没有经过计算,但是可以得出这个极端例子的结论:哪人多就哪,哪怕偏移一公里都不是最优解,哈哈

    大部分情况下距离和时间是正比的吧,但实际用时间的会复杂到无法想象吧,天气、堵车。。。
    JCZ2MkKb5S8ZX9pq
        12
    JCZ2MkKb5S8ZX9pq  
    OP
       2019-01-18 15:03:15 +08:00
    @geelaw 如果路都是四四方方的,那这个结果反而更准了吧。
    lscho
        13
    lscho  
       2019-01-18 15:05:55 +08:00
    服了各位。。。。这个根本不是算法能解决的啊,比如楼上所说,天气、出行方式、道路实际状况、参与者男女比例、个人喜好等等等
    TomVista
        14
    TomVista  
       2019-01-18 15:11:42 +08:00
    人工智障.
    otakustay
        15
    otakustay  
       2019-01-18 16:46:18 +08:00
    去找公安啥的要一份重大活动警力部署算法就好了
    annielong
        16
    annielong  
       2019-01-18 17:08:59 +08:00
    选城市还好说,一个城市内就不能简单选,最起码也要按地图上的道路导航还做选择
    opengps
        17
    opengps  
       2019-01-18 17:10:42 +08:00
    没人说车站是最合适的位置吗?
    wysnylc
        18
    wysnylc  
       2019-01-18 17:12:31 +08:00
    恭喜,你可以入职高德 /百度 /谷歌了
    jinhan13789991
        19
    jinhan13789991  
       2019-01-18 17:39:00 +08:00 via Android
    然后那个地点是块荒地。。
    largecat
        20
    largecat  
       2019-01-18 18:09:02 +08:00 via Android
    先简化一下原型
    一个直线上有多个点,选一个点,使这个点和其他每个点距离的总和最小
    largecat
        21
    largecat  
       2019-01-18 18:11:10 +08:00 via Android
    直线简化,
    x 轴投影,得到 x 轴的点 a
    y 轴投影,得到 y 轴的点 b
    则(a,b)
    JCZ2MkKb5S8ZX9pq
        22
    JCZ2MkKb5S8ZX9pq  
    OP
       2019-01-18 18:31:48 +08:00
    @largecat 直线的话就是平均值了
    设平均值 a
    ```
    sum(d)
    = (x1-a)+(x2-a)+...+(xn-a)
    = (x1+x2+...+xn) - a*n
    = sum(x) - sum(x)
    = 0
    JCZ2MkKb5S8ZX9pq
        23
    JCZ2MkKb5S8ZX9pq  
    OP
       2019-01-18 18:34:20 +08:00
    @largecat 慢,要补个绝对值。
    largecat
        24
    largecat  
       2019-01-18 18:42:44 +08:00 via Android
    @JCZ2MkKb5S8ZX9pq 我没仔细想这个,靠直觉回复的,没有推理,
    我觉得应该没这么简单,
    稍后学习一下
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5467 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 07:03 · PVG 15:03 · LAX 23:03 · JFK 02:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.