卧槽这种题我要用凸优化了 刚好刚才看那个machine learning的题库中也有类似的题 a city has only horizontal and vertical streets people are standing on different cross points now they decide to meet find a cross point that people need least movement
【在 e*****l 的大作中提到】 : 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短. : (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案) : 求大牛提供思路, 谢谢
a*m
9 楼
你那个题目不一样。。。。。你的距离是|x1-x2|+|y1-y2|,结果简单的多了。
【在 r*g 的大作中提到】 : 卧槽这种题我要用凸优化了 : 刚好刚才看那个machine learning的题库中也有类似的题 : a city has only horizontal and vertical streets : people are standing on different cross points : now they decide to meet : find a cross point that people need least movement
a*m
10 楼
赶脚帮助不大呀。。。。
【在 e*****l 的大作中提到】 : 可以网格化坐标, 比如坐标x, y 都是整数
e*l
11 楼
恩, 这个不解决问题. 继续求思路.
【在 a********m 的大作中提到】 : 赶脚帮助不大呀。。。。
r*g
12 楼
right, 这个是weiszfeld问题, 用fixed point可迭代 另外那个street问题求教 我的做法|x - xi| = ri 然后 argmin sum(ri) st. x - xi + ri >= 0 x - xi - ri <= 0 转化成LP问题 我觉得有更方便的方法