一道看似简单的数学题求解。

2019-02-27 16:08:06 +08:00
 xqdoo00o

假设有 n 个数值 X1 到 Xk,如何求得一个数,使得每个数值减去该数的绝对值之和 最小。即求使得下面表达式最小的?值。

该表达式等价于

3646 次点击
所在节点    问与答
30 条回复
talen666
2019-02-27 17:18:50 +08:00
这个怎么等价。。真要等价,不就是求抛物线的顶点-b/2a 了
siyemiaokube
2019-02-27 20:09:09 +08:00
两个式子显然不等价,前者 trivial,后者似乎可以用半平面交来解决
littleMaple
2019-02-27 21:02:40 +08:00
@siyemiaokube 感觉后者才是 trivial,平方之后整个函数变成处处连续平滑处处可导的“好函数”,可以轻易求导解决。前者一堆绝对值,整个函数到处分段且多处不可导,是个“坏函数”,没有优雅解析算法,只能暴力算。
toml
2019-02-27 22:22:04 +08:00
中位数;不等价
DnC
2019-02-28 08:42:52 +08:00
为什么我觉得两个求和表达式是等价的?
最终解设为 x,如果 x 对于表达式 1 是最优解,则 x 肯定是表达式 2 的最优解啊。这不是显然的事情吗?
至于有人说表达式 2 是对表达式 1 的放大,这两个表达式只是为了求得 x,并没有要求表达之的值。
yianing
2019-02-28 09:10:12 +08:00
算法导论的顺序统计量那一章的课后习题就有这个,邮局问题嘛,第一个就是中位数,具体证明可以用反证法,第二个其实更像是最小二乘法的简化形式,和第一个问题是不等价的,两个数的时候第一个问题是两个数中间的就行,而第二个是只有正中间才最小。
abelmakihara
2019-02-28 09:16:12 +08:00
第二个应该是取对数后的中位数吧
咦?不还是中位数吗
纯脑算
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 时最小
那不就还是平均数吗
abelmakihara
2019-02-28 09:31:38 +08:00
@abelmakihara #28 如果限定是原数组的一个数
那就是最离平均数最近的数
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 时最小),即中位数绝对值和最小。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/539295

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX