背景
- 年底老同学要聚餐了。
- 组织者定了一个离他近，但偏离市中心的点。
需求
- 已知参加各人的坐标，就当是
[(x1,y1), (x2,y2), ...]好了。 - 假设聚会在某一个点，该点到各人坐标的距离
[d1,d2,...]。 - 求
sum(d)为最小值时，该点的坐标。 - 也就是在哪里聚，社群的总通勤距离最小。
进阶
- 假设过程中，统计效率用的不是直线距离，而是通勤时间。难解嘛？
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2853 days ago, the information mentioned may be changed or developed.
Supplement 1 · Jan 18, 2019
感谢@icylogic ，让我找到了这个，就直译为 [几何中位数] 。
Geometric median - Wikipedia
至于纠结于聚餐具体细节的，拜托有点数学的情趣。
这个问题接近于商业/设施选址，物流提效，等等方面。
咱们好好玩数学游戏，不玩文字游戏哈。┑(￣▽￣)┍
 |
1
聚餐你还得考虑聚会地点环境，个人口味等等
|
1 |
LadyChunsKiteJan 18, 2019
2
根据路网数据计算出每个人的 service area，再叠加一下得到最小的区域。
http://desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/service-area.htm |
 |
VegetableJan 18, 2019
3
穷举法可破
进价成通勤时间好像也没什么区别,只是多了找出两点最短时间这个任务吧. |
 |
deletelazyJan 18, 2019 via iPhone
4
这不就是最小生成树问题吗
|
 |
5
|
|
LadyChunsKiteJan 18, 2019
6
有点像商业选址。我有 N 个门店在市区（老同学），现在想要租一个大仓库（饭店），统筹货物调拨。
希望到各个门店的通勤时间之和最短。当然还要把租金，人力成本，道路限行等各种因素考虑进来。 |
 |
zsdroidJan 18, 2019
7
万一算出来的最优坐标是个 wc 怎么办？
|
 |
lance6716Jan 18, 2019 via Android
8
上边好多的都在说什么…这不是解极小值吗，偏导等于零
|
 |
geelawJan 18, 2019 via iPhone
9
如果用曼哈顿距离那非常简单…就是横纵坐标都取中位数
|
 |
10
@icylogic 通过你这个 wiki，我找到了一个好像完全一致的。
[Geometric median - Wikipedia]( https://en.m.wikipedia.org/wiki/Geometric_median) |
 |
xiangyuecnJan 18, 2019
11
不会算法，想到一种极端
共 10 个人，9 个在学校，另一个在 1000 公里外，目测也就是选学校周边聚餐总距离最小，那个远的自己一个人要动，其他不用动。 虽然没有经过计算，但是可以得出这个极端例子的结论：哪人多就哪，哪怕偏移一公里都不是最优解，哈哈 大部分情况下距离和时间是正比的吧，但实际用时间的会复杂到无法想象吧，天气、堵车。。。 |
|
12
@geelaw 如果路都是四四方方的，那这个结果反而更准了吧。
|
 |
lschoJan 18, 2019
13
服了各位。。。。这个根本不是算法能解决的啊，比如楼上所说，天气、出行方式、道路实际状况、参与者男女比例、个人喜好等等等
|
 |
TomVistaJan 18, 2019
14
人工智障.
|
 |
otakustayJan 18, 2019
15
去找公安啥的要一份重大活动警力部署算法就好了
|
 |
annielongJan 18, 2019
16
选城市还好说，一个城市内就不能简单选，最起码也要按地图上的道路导航还做选择
|
 |
opengpsJan 18, 2019
17
没人说车站是最合适的位置吗？
|
 |
wysnylcJan 18, 2019
18
恭喜,你可以入职高德 /百度 /谷歌了
|
 |
jinhan13789991Jan 18, 2019 via Android
19
然后那个地点是块荒地。。
|
 |
largecatJan 18, 2019 via Android
20
先简化一下原型
一个直线上有多个点，选一个点，使这个点和其他每个点距离的总和最小 |
|
largecatJan 18, 2019 via Android
21
直线简化，
x 轴投影，得到 x 轴的点 a y 轴投影，得到 y 轴的点 b 则(a,b) ？ |
|
22
@largecat 直线的话就是平均值了
设平均值 a ``` sum(d) = (x1-a)+(x2-a)+...+(xn-a) = (x1+x2+...+xn) - a*n = sum(x) - sum(x) = 0 |
|
23
@largecat 慢，要补个绝对值。
|
|
largecatJan 18, 2019 via Android
24
|
Select Language