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 |
