这是一个创建于 2077 天前的主题，其中的信息可能已经有所发展或是发生改变。
假设有 n 个数值 X1 到 Xk，如何求得一个数，使得每个数值减去该数的绝对值之和 最小。即求使得下面表达式最小的？值。 
该表达式等价于 
 |
1
shyrock 2019-02-27 16:13:56 +08:00
最小生成树？
|
 |
2
xqdoo00o OP 脑算了下，感觉应该是 中位数，但是不知道怎么证明😂
|
 |
3
Hypn0s 2019-02-27 16:22:21 +08:00  1
不就是 X1 到 Xk 的平均值吗
|
 |
4
eccstartup 2019-02-27 16:25:04 +08:00 via Android
奇数个为中位数，偶数个为中间两个值构成闭区间内的任意一个点。
|
|
6
xqdoo00o OP @eccstartup 嗯，我也是认为，就是不知道该怎么证明
|
 |
7
yoohwzy 2019-02-27 16:28:37 +08:00
记该数为 x，把第二个式子展开求导即可， 结果如三楼所说
|
 |
9
icct 2019-02-27 16:33:35 +08:00
两问题不等价
|
 |
11
wwg1994 2019-02-27 16:37:42 +08:00 1
有 2 个数，x、y，y>=x
求 1 数 z 使 |x-z| + |y-z| 最小 显然 只要 x<=z<=y 即可 映射到这个题目，求 z 将原数列排序 循环弹出数列首尾， 当数列长度=2 或者 1 时结束循环， 长度=2 时，z 的取值范围在这 2 个元素之间 长度=1 时，z 的值等于这个元素 |
|
12
yoohwzy 2019-02-27 16:38:26 +08:00
这两个式子不等价， 展开求导只针对第二个式子
|
 |
13
youngjjj 2019-02-27 16:39:28 +08:00 via iPhone
把点画到数轴上，可以看出只能选中位数上那个点才能使距离之和最短，选其他点都会多出一段长度。
|
|
14
yoohwzy 2019-02-27 16:39:43 +08:00
你把第一个式子平方之后就会发现， 第二个式子只是平方结果的一部分
|
|
15
wwg1994 2019-02-27 16:40:25 +08:00
弹出首尾的意思是，每次弹出 1 对数
z 的取值应该在这对数的区间内 |
 |
16
salinapper 2019-02-27 16:43:48 +08:00
@xqdoo00o #10 明显不等价啊，平方之后，大数的影响增大了。
比如 |100| == |-50| + |50| 然而 100^2 == 10000 > 5000 == (-50)^2 + (50)^2 |
 |
17
mixz 2019-02-27 16:53:58 +08:00
把点排列到数轴上，然后把点拆成很多组，如果是偶数，则两个为一组，如 3 5 7 9，则拆成两组，{3，9}，{5，7}。如果是奇数，如 1 3 5 7 9，则拆成{1，9}，{3，7}，{5}。现在只要找到一个点，使得这个点到每个组的距离为最短（组的距离即为到两点的距离之和），那么这个点就是所求的点，如到{3，9}距离最短的点，只需要在 3 和 9 的中间即可，依此类推，易求证。
|
|
18
xqdoo00o OP @salinapper 哦，是，忘了
|
 |
19
sosilver 2019-02-27 17:10:37 +08:00 via Android 1
|
 |
20
Michaelssss 2019-02-27 17:17:46 +08:00 1
画一张图，x 轴为 k，y 轴为 Xk 你说的就是图像上一根平行 x 轴的线，这根线是让所有点的距离最小。。那么显然，这根线应该穿过这堆点的中间
|
 |
21
talen666 2019-02-27 17:18:50 +08:00
这个怎么等价。。真要等价，不就是求抛物线的顶点-b/2a 了
|
 |
22
siyemiaokube 2019-02-27 20:09:09 +08:00 via iPhone
两个式子显然不等价，前者 trivial，后者似乎可以用半平面交来解决
|
 |
23
littleMaple 2019-02-27 21:02:40 +08:00 via iPhone
@siyemiaokube 感觉后者才是 trivial，平方之后整个函数变成处处连续平滑处处可导的“好函数”，可以轻易求导解决。前者一堆绝对值，整个函数到处分段且多处不可导，是个“坏函数”，没有优雅解析算法，只能暴力算。
|
 |
24
toml 2019-02-27 22:22:04 +08:00 via iPhone
中位数；不等价
|
 |
25
DnC 2019-02-28 08:42:52 +08:00
为什么我觉得两个求和表达式是等价的？
最终解设为 x，如果 x 对于表达式 1 是最优解，则 x 肯定是表达式 2 的最优解啊。这不是显然的事情吗？ 至于有人说表达式 2 是对表达式 1 的放大，这两个表达式只是为了求得 x，并没有要求表达之的值。 |
 |
26
yianing 2019-02-28 09:10:12 +08:00 via Android
算法导论的顺序统计量那一章的课后习题就有这个，邮局问题嘛，第一个就是中位数，具体证明可以用反证法，第二个其实更像是最小二乘法的简化形式，和第一个问题是不等价的，两个数的时候第一个问题是两个数中间的就行，而第二个是只有正中间才最小。
|
 |
27
abelmakihara 2019-02-28 09:16:12 +08:00
第二个应该是取对数后的中位数吧
咦？不还是中位数吗  纯脑算 |
|
28
abelmakihara 2019-02-28 09:30:52 +08:00
第二个=∑(x1^2+..+xn^2)+n*y^2-2(x1+...+xn)y
最小的情况就是 n*y^2-2(x1+...+xn)y 最小就行了 据抛物线 y=ax^2+bx+c 当 a>0 时，x=-b/2a y 有最小值 (4ac-b^2)/4a 那就是 2(x1+...+xn)/2n=(x1+...xn)/n 时最小 那不就还是平均数吗 |
|
29
abelmakihara 2019-02-28 09:31:38 +08:00
@abelmakihara #28 如果限定是原数组的一个数
那就是最离平均数最近的数 |
 |
30
dayoushen 2019-02-28 10:58:46 +08:00
绝对值和最小中位数，平方和最小平均数。平方和最小比较好理解，凸函数求导就得到了；绝对值最小，推导可以把数按照大小排列 X_1,X_2,X_n,假设最小的 x 位于 X_k<=x<X_k+1,那么绝对值最小就是(x-X_1) + ... (x - X_k) + (X_k+1 - x) + ... + (X_n - x)，上面式子中每一项都是正数，且 (x-X_k) + (X_k+1 -x) = X_k+1 -X_k，然后证明当 x 为中间数的时候最小（设配对后左或右还有 p 个剩余，然后列出和表达式，可证明 p 等于 0 时最小），即中位数绝对值和最小。
|
Select Language