l*********b 发帖数: 1541 | 1 最近似乎G的面筋的不多,俺报一下,今天下午面的。面完大概一小时候后接到他们的
电话要约2面。我正好下周要去那出差2个月,问可不可以直接onsite,还在等答复。
一开始就是问做的项目,聊了大概15分钟。对我写的一个database特干兴趣。然后做题:
一个matrix上, 有n个人,这n个人要找一个地方开会,问哪个地方让大家移动的距离
最近。 |
w****x 发帖数: 2483 | 2
题:
G的题真是被问烂了, 区二维的median吧
【在 l*********b 的大作中提到】 : 最近似乎G的面筋的不多,俺报一下,今天下午面的。面完大概一小时候后接到他们的 : 电话要约2面。我正好下周要去那出差2个月,问可不可以直接onsite,还在等答复。 : 一开始就是问做的项目,聊了大概15分钟。对我写的一个database特干兴趣。然后做题: : 一个matrix上, 有n个人,这n个人要找一个地方开会,问哪个地方让大家移动的距离 : 最近。
|
g**e 发帖数: 6127 | 3 geometric median? 只能近似吧
们的
距离
【在 w****x 的大作中提到】 : : 题: : G的题真是被问烂了, 区二维的median吧
|
f*****e 发帖数: 2992 | 4 min sum_i (|x_i-x|+|y_i-y|)
over(x,y)
先找 min_y sum_i(|y_i-y|)
再找 min_x sum_i(|x_i-x|)
目标函数好像都是凸的,找斜率接近0的,在median上,一半xi小于x,一半xi大于x
加起来斜率正好为0。
题:
【在 l*********b 的大作中提到】 : 最近似乎G的面筋的不多,俺报一下,今天下午面的。面完大概一小时候后接到他们的 : 电话要约2面。我正好下周要去那出差2个月,问可不可以直接onsite,还在等答复。 : 一开始就是问做的项目,聊了大概15分钟。对我写的一个database特干兴趣。然后做题: : 一个matrix上, 有n个人,这n个人要找一个地方开会,问哪个地方让大家移动的距离 : 最近。
|
i***h 发帖数: 12655 | 5 怎么证明这个总距离最近?
比如所有坐标求平均好象也行?
【在 w****x 的大作中提到】 : : 题: : G的题真是被问烂了, 区二维的median吧
|
i***h 发帖数: 12655 | 6 如果N=2的话,
连线上任意一点的移动距离都是一样的, 就是线段长度, 对不对?
题:
【在 l*********b 的大作中提到】 : 最近似乎G的面筋的不多,俺报一下,今天下午面的。面完大概一小时候后接到他们的 : 电话要约2面。我正好下周要去那出差2个月,问可不可以直接onsite,还在等答复。 : 一开始就是问做的项目,聊了大概15分钟。对我写的一个database特干兴趣。然后做题: : 一个matrix上, 有n个人,这n个人要找一个地方开会,问哪个地方让大家移动的距离 : 最近。
|
c********s 发帖数: 817 | 7 Can we directly take the derivative of sum_i(|y_i-y|) and sum_i(|x_i-x|),
set them to zero and find the corresponding y and x? |
c********s 发帖数: 817 | 8 The matrix is a discretized space. Results from continuos optimization may
not be directly applied. |
x*****o 发帖数: 33 | 9 这个是对的,可是这个问题相当于一个多边形求中间哪点到所有顶点和最近,which我
不知道怎么做。
【在 i***h 的大作中提到】 : 如果N=2的话, : 连线上任意一点的移动距离都是一样的, 就是线段长度, 对不对? : : 题:
|
g**e 发帖数: 6127 | 10 http://en.wikipedia.org/wiki/Geometric_median
【在 f*****e 的大作中提到】 : min sum_i (|x_i-x|+|y_i-y|) : over(x,y) : 先找 min_y sum_i(|y_i-y|) : 再找 min_x sum_i(|x_i-x|) : 目标函数好像都是凸的,找斜率接近0的,在median上,一半xi小于x,一半xi大于x : 加起来斜率正好为0。 : : 题:
|
|
|
w****x 发帖数: 2483 | 11
G给的距离公式因该是|x2 - x1| + |y2 - y1|吧
【在 i***h 的大作中提到】 : 怎么证明这个总距离最近? : 比如所有坐标求平均好象也行?
|
f*****e 发帖数: 2992 | 12 知道,boyd那本书上有这题。最简单的方法就是分段看斜率,一开始斜率为负,后来斜
率为正。就是一个拔河的过程。其实看到|xi-x|是凸的,n个凸函数的和任然是凸函数
,心里就有谱了。
【在 g**e 的大作中提到】 : http://en.wikipedia.org/wiki/Geometric_median
|
g**e 发帖数: 6127 | 13 大牛,你数学太nb了
【在 f*****e 的大作中提到】 : 知道,boyd那本书上有这题。最简单的方法就是分段看斜率,一开始斜率为负,后来斜 : 率为正。就是一个拔河的过程。其实看到|xi-x|是凸的,n个凸函数的和任然是凸函数 : ,心里就有谱了。
|
g**e 发帖数: 6127 | 14 原来是曼哈顿距离,我真土
【在 w****x 的大作中提到】 : : G给的距离公式因该是|x2 - x1| + |y2 - y1|吧
|
i***h 发帖数: 12655 | 15 OK, 然后怎么做?
【在 w****x 的大作中提到】 : : G给的距离公式因该是|x2 - x1| + |y2 - y1|吧
|
w****x 发帖数: 2483 | 16
median
【在 i***h 的大作中提到】 : OK, 然后怎么做?
|
T******o 发帖数: 244 | 17 可以证明,N个点中,存在一个点,这个点做为开会点,结果=最优解。 分x,y轴分
别sort所有的点(NlogN)。 找出各自维上的最优点(O(N)可做),然后x, y 座标组合起
来,就是最后结果。 |
N**n 发帖数: 832 | 18 大牛你在哪儿找的800道题啊,能分享一下么
【在 w****x 的大作中提到】 : : median
|
r*****e 发帖数: 264 | |
r*****e 发帖数: 264 | 20 sorry,是ST的特殊情况,median的做法是对的。可以理解为linear programming问题
,因为函数convex,最优解确实在boundary(即x-median和y-median的交点)。 |
|
|
g*******n 发帖数: 214 | 21 请问是分别找x和y的median么?是有什么证明么?为什么不是平均数?(虽然感觉应该
是median)
谢谢!
【在 w****x 的大作中提到】 : : median
|
r*****e 发帖数: 264 | 22 Median number minimizes \sum |x_i-x|
since the solution space is convex, the optimal solution is at the boundary,
i.e. the intersection of x-median and y-median. |
c********t 发帖数: 5706 | 23 这题与算法有关系吗?为什么G要考数学呢?
题:
【在 l*********b 的大作中提到】 : 最近似乎G的面筋的不多,俺报一下,今天下午面的。面完大概一小时候后接到他们的 : 电话要约2面。我正好下周要去那出差2个月,问可不可以直接onsite,还在等答复。 : 一开始就是问做的项目,聊了大概15分钟。对我写的一个database特干兴趣。然后做题: : 一个matrix上, 有n个人,这n个人要找一个地方开会,问哪个地方让大家移动的距离 : 最近。
|
l****c 发帖数: 782 | 24 我在想如果说问题是问必须在这些点里面找一个点开会,怎么做。 |
l****c 发帖数: 782 | 25 还有就是,请教这种题的sort,输入应该是不能改的,采用怎样的sort方式呢 |
i****y 发帖数: 58 | 26 这题是否就变成了find the kth element in two unsorted array. k = (n-1)/2 |