[(x1,y1), (x2,y2), ...]
好了。[d1,d2,...]
。sum(d)
为最小值时,该点的坐标。感谢@icylogic ,让我找到了这个,就直译为 [几何中位数] 。
Geometric median - Wikipedia
至于纠结于聚餐具体细节的,拜托有点数学的情趣。
这个问题接近于商业/设施选址,物流提效,等等方面。
咱们好好玩数学游戏,不玩文字游戏哈。┑( ̄▽ ̄)┍
1
TimePPT 2019-01-18 13:21:08 +08:00 via iPhone 1
聚餐你还得考虑聚会地点环境,个人口味等等
|
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 |
3
Vegetable 2019-01-18 13:25:33 +08:00
穷举法可破
进价成通勤时间好像也没什么区别,只是多了找出两点最短时间这个任务吧. |
4
deletelazy 2019-01-18 13:26:14 +08:00 via iPhone
这不就是最小生成树问题吗
|
5
icylogic 2019-01-18 13:27:00 +08:00 via iPhone 1
|
6
LadyChunsKite 2019-01-18 13:28:12 +08:00
有点像商业选址。我有 N 个门店在市区(老同学),现在想要租一个大仓库(饭店),统筹货物调拨。
希望到各个门店的通勤时间之和最短。当然还要把租金,人力成本,道路限行等各种因素考虑进来。 |
7
zsdroid 2019-01-18 13:35:21 +08:00
万一算出来的最优坐标是个 wc 怎么办?
|
8
lance6716 2019-01-18 14:04:35 +08:00 via Android
上边好多的都在说什么…这不是解极小值吗,偏导等于零
|
9
geelaw 2019-01-18 14:06:46 +08:00 via iPhone
如果用曼哈顿距离那非常简单…就是横纵坐标都取中位数
|
10
JCZ2MkKb5S8ZX9pq OP @icylogic 通过你这个 wiki,我找到了一个好像完全一致的。
[Geometric median - Wikipedia]( https://en.m.wikipedia.org/wiki/Geometric_median) |
11
xiangyuecn 2019-01-18 14:58:20 +08:00
不会算法,想到一种极端
共 10 个人,9 个在学校,另一个在 1000 公里外,目测也就是选学校周边聚餐总距离最小,那个远的自己一个人要动,其他不用动。 虽然没有经过计算,但是可以得出这个极端例子的结论:哪人多就哪,哪怕偏移一公里都不是最优解,哈哈 大部分情况下距离和时间是正比的吧,但实际用时间的会复杂到无法想象吧,天气、堵车。。。 |
12
JCZ2MkKb5S8ZX9pq OP @geelaw 如果路都是四四方方的,那这个结果反而更准了吧。
|
13
lscho 2019-01-18 15:05:55 +08:00
服了各位。。。。这个根本不是算法能解决的啊,比如楼上所说,天气、出行方式、道路实际状况、参与者男女比例、个人喜好等等等
|
14
TomVista 2019-01-18 15:11:42 +08:00
人工智障.
|
15
otakustay 2019-01-18 16:46:18 +08:00
去找公安啥的要一份重大活动警力部署算法就好了
|
16
annielong 2019-01-18 17:08:59 +08:00
选城市还好说,一个城市内就不能简单选,最起码也要按地图上的道路导航还做选择
|
17
opengps 2019-01-18 17:10:42 +08:00
没人说车站是最合适的位置吗?
|
18
wysnylc 2019-01-18 17:12:31 +08:00
恭喜,你可以入职高德 /百度 /谷歌了
|
19
jinhan13789991 2019-01-18 17:39:00 +08:00 via Android
然后那个地点是块荒地。。
|
20
largecat 2019-01-18 18:09:02 +08:00 via Android
先简化一下原型
一个直线上有多个点,选一个点,使这个点和其他每个点距离的总和最小 |
21
largecat 2019-01-18 18:11:10 +08:00 via Android
直线简化,
x 轴投影,得到 x 轴的点 a y 轴投影,得到 y 轴的点 b 则(a,b) ? |
22
JCZ2MkKb5S8ZX9pq OP @largecat 直线的话就是平均值了
设平均值 a ``` sum(d) = (x1-a)+(x2-a)+...+(xn-a) = (x1+x2+...+xn) - a*n = sum(x) - sum(x) = 0 |
23
JCZ2MkKb5S8ZX9pq OP @largecat 慢,要补个绝对值。
|
24
largecat 2019-01-18 18:42:44 +08:00 via Android
|