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

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

  •  
  •   JCZ2MkKb5S8ZX9pq · 28 天前 · 2122 次点击

    背景

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

    需求

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

    进阶

    • 假设过程中,统计效率用的不是直线距离,而是通勤时间。难解嘛?
    第 1 条附言  ·  28 天前

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

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

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

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

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

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