求到所有点的距离和最短, 求助# JobHunting - 待字闺中
e*l
1 楼
给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
(不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
求大牛提供思路, 谢谢
(不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
求大牛提供思路, 谢谢
d*c
2 楼
L家题。。。。
y*e
3 楼
找median吧
b*5
4 楼
我这道题， 面经都贴了二次了。。
【在 y*****e 的大作中提到】
: 找median吧
【在 y*****e 的大作中提到】
: 找median吧
a*m
5 楼
这题是真需要点几何知识了。。。。
准确解还是近似解？
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
准确解还是近似解？
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
e*l
6 楼
求贴一把链接
【在 b**********5 的大作中提到】
: 我这道题， 面经都贴了二次了。。
【在 b**********5 的大作中提到】
: 我这道题， 面经都贴了二次了。。
e*l
7 楼
可以网格化坐标, 比如坐标x, y 都是整数
【在 a********m 的大作中提到】
: 这题是真需要点几何知识了。。。。
: 准确解还是近似解？
【在 a********m 的大作中提到】
: 这题是真需要点几何知识了。。。。
: 准确解还是近似解？
r*g
8 楼
卧槽这种题我要用凸优化了
刚好刚才看那个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 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
刚好刚才看那个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
【在 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 的大作中提到】
: 可以网格化坐标, 比如坐标x, y 都是整数
e*l
11 楼
恩, 这个不解决问题. 继续求思路.
【在 a********m 的大作中提到】
: 赶脚帮助不大呀。。。。
【在 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问题 我觉得有更方便的方法
【在 a********m 的大作中提到】
: 你那个题目不一样。。。。。你的距离是|x1-x2|+|y1-y2|，结果简单的多了。
这个是weiszfeld问题, 用fixed point可迭代
另外那个street问题求教
我的做法|x - xi| = ri 然后
argmin sum(ri)
st. x - xi + ri >= 0
x - xi - ri <= 0
转化成LP问题 我觉得有更方便的方法
【在 a********m 的大作中提到】
: 你那个题目不一样。。。。。你的距离是|x1-x2|+|y1-y2|，结果简单的多了。
b*n
13 楼
Euclidean Distance? 不会做。。。
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
b*5
14 楼
http://weiminghome.mitbbs.com/article_t/JobHunting/32916137.htm
assuming u r talking about manhattan distance...
euclid就不知道了。。。
【在 e*****l 的大作中提到】
: 求贴一把链接
assuming u r talking about manhattan distance...
euclid就不知道了。。。
【在 e*****l 的大作中提到】
: 求贴一把链接
a*m
15 楼
street那个最后答案是media。方法是x，y单独考虑，从最外两个两个摘出去。不过这
题目不好，有点脑筋急转弯。
直线距离麻烦。:( 跌代的话看来还是近似解了。
【在 r*g 的大作中提到】
: right,
: 这个是weiszfeld问题, 用fixed point可迭代
: 另外那个street问题求教
: 我的做法|x - xi| = ri 然后
: argmin sum(ri)
: st. x - xi + ri >= 0
: x - xi - ri <= 0
: 转化成LP问题 我觉得有更方便的方法
题目不好，有点脑筋急转弯。
直线距离麻烦。:( 跌代的话看来还是近似解了。
【在 r*g 的大作中提到】
: right,
: 这个是weiszfeld问题, 用fixed point可迭代
: 另外那个street问题求教
: 我的做法|x - xi| = ri 然后
: argmin sum(ri)
: st. x - xi + ri >= 0
: x - xi - ri <= 0
: 转化成LP问题 我觉得有更方便的方法
p*r
16 楼
如果是欧式距离，这是一个比较难的问题，叫做Geometric median 基本方法就是迭代
，但是容易掉入局部最优，需要一些跳出局部最优的办法比如模拟退火
http://en.wikipedia.org/wiki/Geometric_median
我觉得如果是面试问道，应该是曼哈顿距离，相对容易一些
http://online-judge.uva.es/board/viewtopic.php?f=22&t=42620
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
，但是容易掉入局部最优，需要一些跳出局部最优的办法比如模拟退火
http://en.wikipedia.org/wiki/Geometric_median
我觉得如果是面试问道，应该是曼哈顿距离，相对容易一些
http://online-judge.uva.es/board/viewtopic.php?f=22&t=42620
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
e*l
17 楼
感谢!!
如果再加上有障碍物呢, 怎么破?
【在 b**********5 的大作中提到】
: http://weiminghome.mitbbs.com/article_t/JobHunting/32916137.htm
: assuming u r talking about manhattan distance...
: euclid就不知道了。。。
如果再加上有障碍物呢, 怎么破?
【在 b**********5 的大作中提到】
: http://weiminghome.mitbbs.com/article_t/JobHunting/32916137.htm
: assuming u r talking about manhattan distance...
: euclid就不知道了。。。
p*r
18 楼
加上障碍物就是DP的时候把当前点是否是障碍物加个判断啊
【在 e*****l 的大作中提到】
: 感谢!!
: 如果再加上有障碍物呢, 怎么破?
a*m
19 楼
障碍物是只能绕着走的？有木有其他信息？比如个数和大小限制？
【在 e*****l 的大作中提到】
: 感谢!!
: 如果再加上有障碍物呢, 怎么破?
【在 e*****l 的大作中提到】
: 感谢!!
: 如果再加上有障碍物呢, 怎么破?
e*l
20 楼
障碍物的话, 只能绕行. 大小个数应该没有限制吧, 只是能保证都有路径走到罢了
【在 a********m 的大作中提到】
: 障碍物是只能绕着走的？有木有其他信息？比如个数和大小限制？
【在 a********m 的大作中提到】
: 障碍物是只能绕着走的？有木有其他信息？比如个数和大小限制？
a*m
21 楼
满哈吨木有dp呀。
赶脚如果没限制只有暴力了。
【在 p*****r 的大作中提到】
:
: 加上障碍物就是DP的时候把当前点是否是障碍物加个判断啊
赶脚如果没限制只有暴力了。
【在 p*****r 的大作中提到】
:
: 加上障碍物就是DP的时候把当前点是否是障碍物加个判断啊
r*g
22 楼
这个问题convex的吧？为什么有局部最优？
对这个问题说数值解就good enough了
只为它没有封闭解
【在 p*****r 的大作中提到】
: 如果是欧式距离，这是一个比较难的问题，叫做Geometric median 基本方法就是迭代
: ，但是容易掉入局部最优，需要一些跳出局部最优的办法比如模拟退火
: http://en.wikipedia.org/wiki/Geometric_median
: 我觉得如果是面试问道，应该是曼哈顿距离，相对容易一些
: http://online-judge.uva.es/board/viewtopic.php?f=22&t=42620
T*0
23 楼
这是地理专业空间分析里的Median Center问题，原来CS面试也会问啊？
我了解的方法就是迭代,先假定一个点P(i)为Median Center，然后通过迭代公式求解下
一个点P(i+1)，直到P(i)和P(i+1)的距离小于一个Threshold（比如0.001），那么P(i+
1)就是Median Center了。为了提高效率，通常第一个假定的点会选择Mean Center（把
所有点的X，Y分别求均值），因为一般情况下Median Center和Mean Center的位置比较
接近。
Median Center只能无限逼近，不可能得到最准确的Median Center。
参考连接，各种Center都给你介绍一遍：
http://www.spatialanalysisonline.com/HTML/?centroids_and_center
我了解的方法就是迭代,先假定一个点P(i)为Median Center，然后通过迭代公式求解下
一个点P(i+1)，直到P(i)和P(i+1)的距离小于一个Threshold（比如0.001），那么P(i+
1)就是Median Center了。为了提高效率，通常第一个假定的点会选择Mean Center（把
所有点的X，Y分别求均值），因为一般情况下Median Center和Mean Center的位置比较
接近。
Median Center只能无限逼近，不可能得到最准确的Median Center。
参考连接，各种Center都给你介绍一遍：
http://www.spatialanalysisonline.com/HTML/?centroids_and_center
d*n
24 楼
median吧。两个方向。
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
Z*0
25 楼
DS的Machine Learning题目?
是曼哈顿距离，还是Euclidean Distance？
coursera的matrix coding课程，可能有相关的解法。
是曼哈顿距离，还是Euclidean Distance？
coursera的matrix coding课程，可能有相关的解法。
相关阅读
youtube, twitter 选offer[帮问] 8/13 收到材料，可是现在OPT还没动静还是initial review好人做不了manager。暗示被拒的三句话讨论一个很现实的问题现在algorithm trading的公司还有搞头嚒码工堕落的一天 (转载)有人了解Google Adsense for Search 组么？帮推荐湾区做视频的公司Ooyala的big data职位Re: 温JB的四万亿哪去了？有贪官家中被搜出20亿人民币！ (转载)烂校cs master应该来加州吗有人了解Linkedin的Monetization Team (Marketing Solutions)吗……求pinterest和dropbox内推请教个title选offer的问题大家对pinterest怎么看？大家应该多想想怎么自己搞startup电面被LinkedIn拒，多久可以重新申请呢roth 401k,roth IRA, 401k到底什么区别？年薪多少的人该入哪个new grad亚麻选组 + 职业发展求教Job opportunity