V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Doldrums
V2EX  ›  编程

代码陷入死胡同了 请哪位大佬指点一下_(:з」∠)_

  •  1
     
  •   Doldrums · 2019-08-29 21:04:33 +08:00 · 5778 次点击
    这是一个创建于 1673 天前的主题,其中的信息可能已经有所发展或是发生改变。
    需求:两列数组 [x0,x1,x2,...x100] & [y0,y1,y2,...y100] ,求解一个系数 k,
    使得 |k*x1-y1|+|k*x2-y2|+|k*x3-y3|+...+|k*x100-y100| 最小
    即 如何使两列数的差值的绝对值之和最小?
    5 条回复    2019-08-30 00:06:53 +08:00
    thedrwu
        1
    thedrwu  
       2019-08-29 21:28:23 +08:00 via Android
    线…性…规…划…消灭 L1-norm ?
    thedrwu
        2
    thedrwu  
       2019-08-29 21:58:53 +08:00 via Android
    需要代码和原理请 Google
    linear programming minimize l1 norm
    corvofeng
        3
    corvofeng  
       2019-08-29 22:10:21 +08:00
    这应该算是一个数学问题, 之前我在网易游戏面试的时候遇到过类似的数学问题.

    转变一下思路, 在几何上, 你这个问题应该是求所有点到某条直线上对应点的距离之和最小

    假设一条直线是 y=Ax+b, x1 在直线上对应的点坐标是 Ax1+b, 那么|Ax1+b - y1| 就是(x1,y1) 与这条直线上面相同横坐标的点的距离, 然后你应该考虑的是怎么让这个距离之和最短, 我也不太会算这个距离, 这是我找的相关讨论:

    https://bbs.csdn.net/topics/210003809

    你可以看下这个人的推演:

    https://bbs.csdn.net/topics/210003809?list=1887724
    momocraft
        4
    momocraft  
       2019-08-29 22:32:54 +08:00
    一个思路不一定对

    -----------------

    令那个绝对值之和为 z

    不失一般性 假设 y1/x1 <= y2/x2 <= ... y100/x100 且所有 x 均不为 0 (如果有 0 则那项是常数)

    则 (-无穷, y1/x1] 是 z(k) 的单调区间 (此区间内所有绝对值均有确定符号), [y1/x1, y2/x2] 也是. 以后每个都是.

    而且 z(-无穷) 和 z(+无穷) 要么是常数要么是+无穷. 常数 iff 所有 x 都是 0.

    所以 for k in y1/x1 , y2/x2 一个个试过去 使得 z 最小的那个 k 就是极值

    我好像领悟了为什么人们更喜欢用最小二乘法定义误差
    luckyx
        5
    luckyx  
       2019-08-30 00:06:53 +08:00 via iPhone
    企图用 y=kx 去拟合 y=f(x),但要求代价最小
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2885 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 15:19 · PVG 23:19 · LAX 08:19 · JFK 11:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.