V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
xqdoo00o
V2EX  ›  问与答

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

  •  
  •   xqdoo00o · 2019-02-27 16:08:06 +08:00 · 3378 次点击
    这是一个创建于 1856 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    该表达式等价于

    30 条回复    2019-02-28 10:58:46 +08:00
    shyrock
        1
    shyrock  
       2019-02-27 16:13:56 +08:00
    最小生成树?
    xqdoo00o
        2
    xqdoo00o  
    OP
       2019-02-27 16:21:32 +08:00
    脑算了下,感觉应该是 中位数,但是不知道怎么证明😂
    Hypn0s
        3
    Hypn0s  
       2019-02-27 16:22:21 +08:00   ❤️ 1
    不就是 X1 到 Xk 的平均值吗
    eccstartup
        4
    eccstartup  
       2019-02-27 16:25:04 +08:00 via Android
    奇数个为中位数,偶数个为中间两个值构成闭区间内的任意一个点。
    xqdoo00o
        5
    xqdoo00o  
    OP
       2019-02-27 16:25:35 +08:00
    @Hypn0s 并不是,反例:1,9,11。平均数 7,但 9 是对的。
    xqdoo00o
        6
    xqdoo00o  
    OP
       2019-02-27 16:27:01 +08:00
    @eccstartup 嗯,我也是认为,就是不知道该怎么证明
    yoohwzy
        7
    yoohwzy  
       2019-02-27 16:28:37 +08:00
    记该数为 x,把第二个式子展开求导即可, 结果如三楼所说
    Hypn0s
        8
    Hypn0s  
       2019-02-27 16:29:37 +08:00
    @xqdoo00o #5 emmmmmmmmm,想了下是欠考虑了,应该是中位数,归纳法可证
    icct
        9
    icct  
       2019-02-27 16:33:35 +08:00
    两问题不等价
    xqdoo00o
        10
    xqdoo00o  
    OP
       2019-02-27 16:37:10 +08:00
    @icct 感觉应该等价啊,求解。
    wwg1994
        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 的值等于这个元素
    yoohwzy
        12
    yoohwzy  
       2019-02-27 16:38:26 +08:00
    这两个式子不等价, 展开求导只针对第二个式子
    youngjjj
        13
    youngjjj  
       2019-02-27 16:39:28 +08:00 via iPhone
    把点画到数轴上,可以看出只能选中位数上那个点才能使距离之和最短,选其他点都会多出一段长度。
    yoohwzy
        14
    yoohwzy  
       2019-02-27 16:39:43 +08:00
    你把第一个式子平方之后就会发现, 第二个式子只是平方结果的一部分
    wwg1994
        15
    wwg1994  
       2019-02-27 16:40:25 +08:00
    弹出首尾的意思是,每次弹出 1 对数
    z 的取值应该在这对数的区间内
    salinapper
        16
    salinapper  
       2019-02-27 16:43:48 +08:00
    @xqdoo00o #10 明显不等价啊,平方之后,大数的影响增大了。
    比如 |100| == |-50| + |50|
    然而 100^2 == 10000 > 5000 == (-50)^2 + (50)^2
    mixz
        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 的中间即可,依此类推,易求证。
    xqdoo00o
        18
    xqdoo00o  
    OP
       2019-02-27 17:00:48 +08:00
    @salinapper 哦,是,忘了
    sosilver
        19
    sosilver  
       2019-02-27 17:10:37 +08:00 via Android   ❤️ 1
    Michaelssss
        20
    Michaelssss  
       2019-02-27 17:17:46 +08:00   ❤️ 1
    画一张图,x 轴为 k,y 轴为 Xk 你说的就是图像上一根平行 x 轴的线,这根线是让所有点的距离最小。。那么显然,这根线应该穿过这堆点的中间
    talen666
        21
    talen666  
       2019-02-27 17:18:50 +08:00
    这个怎么等价。。真要等价,不就是求抛物线的顶点-b/2a 了
    siyemiaokube
        22
    siyemiaokube  
       2019-02-27 20:09:09 +08:00 via iPhone
    两个式子显然不等价,前者 trivial,后者似乎可以用半平面交来解决
    littleMaple
        23
    littleMaple  
       2019-02-27 21:02:40 +08:00 via iPhone
    @siyemiaokube 感觉后者才是 trivial,平方之后整个函数变成处处连续平滑处处可导的“好函数”,可以轻易求导解决。前者一堆绝对值,整个函数到处分段且多处不可导,是个“坏函数”,没有优雅解析算法,只能暴力算。
    toml
        24
    toml  
       2019-02-27 22:22:04 +08:00 via iPhone
    中位数;不等价
    DnC
        25
    DnC  
       2019-02-28 08:42:52 +08:00
    为什么我觉得两个求和表达式是等价的?
    最终解设为 x,如果 x 对于表达式 1 是最优解,则 x 肯定是表达式 2 的最优解啊。这不是显然的事情吗?
    至于有人说表达式 2 是对表达式 1 的放大,这两个表达式只是为了求得 x,并没有要求表达之的值。
    yianing
        26
    yianing  
       2019-02-28 09:10:12 +08:00 via Android
    算法导论的顺序统计量那一章的课后习题就有这个,邮局问题嘛,第一个就是中位数,具体证明可以用反证法,第二个其实更像是最小二乘法的简化形式,和第一个问题是不等价的,两个数的时候第一个问题是两个数中间的就行,而第二个是只有正中间才最小。
    abelmakihara
        27
    abelmakihara  
       2019-02-28 09:16:12 +08:00
    第二个应该是取对数后的中位数吧
    咦?不还是中位数吗
    纯脑算
    abelmakihara
        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 时最小
    那不就还是平均数吗
    abelmakihara
        29
    abelmakihara  
       2019-02-28 09:31:38 +08:00
    @abelmakihara #28 如果限定是原数组的一个数
    那就是最离平均数最近的数
    dayoushen
        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 时最小),即中位数绝对值和最小。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3246 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:15 · PVG 20:15 · LAX 05:15 · JFK 08:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.