e*****l
发帖数: 12 | 1 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
(不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
求大牛提供思路, 谢谢 |
d*****c
发帖数: 605 | |
y*****e
发帖数: 712 | |
b**********5
发帖数: 7881 | 4 我这道题， 面经都贴了二次了。。
【在 y*****e 的大作中提到】
: 找median吧
|
a********m
发帖数: 15480 | 5 这题是真需要点几何知识了。。。。
准确解还是近似解？
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
|
e*****l
发帖数: 12 | 6 求贴一把链接
【在 b**********5 的大作中提到】
: 我这道题， 面经都贴了二次了。。
|
e*****l
发帖数: 12 | 7 可以网格化坐标, 比如坐标x, y 都是整数
【在 a********m 的大作中提到】
: 这题是真需要点几何知识了。。。。
: 准确解还是近似解？
|
r*g
发帖数: 186 | 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 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
|
a********m
发帖数: 15480 | 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
发帖数: 15480 | 10 赶脚帮助不大呀。。。。
【在 e*****l 的大作中提到】
: 可以网格化坐标, 比如坐标x, y 都是整数
|
|
|
e*****l
发帖数: 12 | 11 恩, 这个不解决问题. 继续求思路.
【在 a********m 的大作中提到】
: 赶脚帮助不大呀。。。。
|
r*g
发帖数: 186 | 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|，结果简单的多了。
|
b*****n
发帖数: 618 | 13 Euclidean Distance? 不会做。。。
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
|
b**********5
发帖数: 7881 | 14 http://weiminghome.mitbbs.com/article_t/JobHunting/32916137.htm
assuming u r talking about manhattan distance...
euclid就不知道了。。。
【在 e*****l 的大作中提到】
: 求贴一把链接
|
a********m
发帖数: 15480 | 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问题 我觉得有更方便的方法
|
p*****r
发帖数: 1883 | 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 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
|
e*****l
发帖数: 12 | 17 感谢!!
如果再加上有障碍物呢, 怎么破?
【在 b**********5 的大作中提到】
: http://weiminghome.mitbbs.com/article_t/JobHunting/32916137.htm
: assuming u r talking about manhattan distance...
: euclid就不知道了。。。
|
p*****r
发帖数: 1883 | 18
加上障碍物就是DP的时候把当前点是否是障碍物加个判断啊
【在 e*****l 的大作中提到】
: 感谢!!
: 如果再加上有障碍物呢, 怎么破?
|
a********m
发帖数: 15480 | 19 障碍物是只能绕着走的？有木有其他信息？比如个数和大小限制？
【在 e*****l 的大作中提到】
: 感谢!!
: 如果再加上有障碍物呢, 怎么破?
|
e*****l
发帖数: 12 | 20 障碍物的话, 只能绕行. 大小个数应该没有限制吧, 只是能保证都有路径走到罢了
【在 a********m 的大作中提到】
: 障碍物是只能绕着走的？有木有其他信息？比如个数和大小限制？
|
|
|
a********m
发帖数: 15480 | 21 满哈吨木有dp呀。
赶脚如果没限制只有暴力了。
【在 p*****r 的大作中提到】
:
: 加上障碍物就是DP的时候把当前点是否是障碍物加个判断啊
|
r*g
发帖数: 186 | 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
发帖数: 1372 | 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 |
d****n
发帖数: 397 | 24 median吧。两个方向。
【在 e*****l 的大作中提到】
: 给定 n 个平面上的点, 需要找到一个点, 使其与所有给定点的距离和最短.
: (不是从给定的 n 个点中找答案, 而是从平面上任意位置找答案)
: 求大牛提供思路, 谢谢
|
Z**0
发帖数: 1119 | 25 DS的Machine Learning题目?
是曼哈顿距离，还是Euclidean Distance？
coursera的matrix coding课程，可能有相关的解法。 |
