l********r
发帖数: 140 | 1 Many persons on a 2D map, their locations are known. How to find a meeting
spot so that the sum of distance is minimized for everyone? | l****c
发帖数: 782 | | t****a
发帖数: 1212 | 3 这是个数学题诶
假定用XY = {[x1,y1],...,[xi,yi],...[xn,yn]} 表示各个人的位置
求[x0,y0] = argmin{\sum(f(x0,yo))} = argmin{\sum(dist([xi,yi],[x0,y0]))}
目标函数是关于x0,y0的二次函数，可以对它求关于x0,y0的偏导数，最小值发生在两个
偏导数都等于0
解这个方程组可以得到x0, y0的取值 | t****a
发帖数: 1212 | 4 刚求了一下，偏导数方程为
-2*sum(x[i]-x0) = 0
-2*sum(y[i]-y0) = 0
所以结果为
x0 = mean(x[i]); y0 = mean(y[i])
【在 t****a 的大作中提到】
: 这是个数学题诶
: 假定用XY = {[x1,y1],...,[xi,yi],...[xn,yn]} 表示各个人的位置
: 求[x0,y0] = argmin{\sum(f(x0,yo))} = argmin{\sum(dist([xi,yi],[x0,y0]))}
: 目标函数是关于x0,y0的二次函数，可以对它求关于x0,y0的偏导数，最小值发生在两个
: 偏导数都等于0
: 解这个方程组可以得到x0, y0的取值
| t****a
发帖数: 1212 | 5 不好意思，之前的方程写错了，少写了开根号
修改以后的偏导数方程组为
-sum((x[i]-x0)/f(x0,y0)) = 0
-sum((y[i]-y0)/f(x0,y0)) = 0
我不会求解这个方程组，无法给出解析解
只好用梯度下降方法来迭代求解数值解。
这一题好像是某一年google code jam某一轮列出的题目之一。我记得当时那道题目也
只要求精度若干的数值解。
【在 t****a 的大作中提到】
: 刚求了一下，偏导数方程为
: -2*sum(x[i]-x0) = 0
: -2*sum(y[i]-y0) = 0
: 所以结果为
: x0 = mean(x[i]); y0 = mean(y[i])
| c********t
发帖数: 5706 | 6 数学白痴是这么想的
如果想
Sum(sqrt((xi-x0)^2+(yi-y0)^2)) 最小
那么就要 Sum(sqrt(abs(xi-x0)+abs(yi-y0)))最小
就要 Sum(abs(xi-x0)+abs(yi-y0))最小
就要Sum(abs(xi-x0))最小 Sum(abs(yi-y0))最小
就是mean(x) mean(y)吧
【在 t****a 的大作中提到】
: 这是个数学题诶
: 假定用XY = {[x1,y1],...,[xi,yi],...[xn,yn]} 表示各个人的位置
: 求[x0,y0] = argmin{\sum(f(x0,yo))} = argmin{\sum(dist([xi,yi],[x0,y0]))}
: 目标函数是关于x0,y0的二次函数，可以对它求关于x0,y0的偏导数，最小值发生在两个
: 偏导数都等于0
: 解这个方程组可以得到x0, y0的取值
| t****a
发帖数: 1212 | 7 1. Sum(sqrt((xi-x0)^2+(yi-y0)^2)) 最小
2. 那么就要 Sum(sqrt(abs(xi-x0)+abs(yi-y0)))最小
3. 就要 Sum(abs(xi-x0)+abs(yi-y0))最小
4. 就要Sum(abs(xi-x0))最小 Sum(abs(yi-y0))最小
1->2, 2->3的逻辑我不懂，能给个解释么？ | c********t
发帖数: 5706 | 8 1->2: (a^2 < b^2) => (abs(a) < abs(b))
2->3: 对于正整数 sqrt(a) < sqrt(b) => a
【在 t****a 的大作中提到】
: 1. Sum(sqrt((xi-x0)^2+(yi-y0)^2)) 最小
: 2. 那么就要 Sum(sqrt(abs(xi-x0)+abs(yi-y0)))最小
: 3. 就要 Sum(abs(xi-x0)+abs(yi-y0))最小
: 4. 就要Sum(abs(xi-x0))最小 Sum(abs(yi-y0))最小
: 1->2, 2->3的逻辑我不懂，能给个解释么？
| e******o
发帖数: 757 | 9 两个median.
目标函数是convex的。左边导数小于0，右边大于0
【在 c********t 的大作中提到】
: 1->2: (a^2 < b^2) => (abs(a) < abs(b))
: 2->3: 对于正整数 sqrt(a) < sqrt(b) => a
| t****a
发帖数: 1212 | 10 我想这个推理是错的。
原题要求的是欧式距离，你的式子里变成了曼哈顿距离。两者不等价。
【在 c********t 的大作中提到】
: 1->2: (a^2 < b^2) => (abs(a) < abs(b))
: 2->3: 对于正整数 sqrt(a) < sqrt(b) => a
|
|
