算法问题请教

arachide · 发表于 2009-4-5 11:06:27

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

表达式 Ri=( (a*Xi+b*Yi)-(a*X0+b*Y0) )/(Ci/C0) Xi,Yi,Ci,X0,Y0,C0 都是已知的浮点数 x0,y0,c0 x1,y1,c1 x2,y2,c2 ... xi,yi,ci ... xn,yn,cn ∑ abs（Ri ）有最小值时的a，b的值 abs为求绝对值 ∑ 为求和那位知道用什么算法请教

sunwukong · 发表于 2009-4-8 22:50:47

因为 ∑ abs（Ri ） >= 0，而当 a = b = 0 时，∑ abs（Ri ） = 0，所以， a = 0，b = 0 就是答案。建议 LZ，还是改用最小二乘法吧

zed · 发表于 2009-4-9 12:01:10

估计要添加$a^2+b^2=1$的条件. 不过使用绝对值的表达式很难用最小二乘法来算极值

zed · 发表于 2009-4-9 12:04:15

我们可以记$U_i={X_i-X_0}/{{C_i}/{C_0}},V_i={Y_i-Y_0}/{{C_i}/{C_0}}$ 我们相当于要找一个方向,使得所有的点$(U_i,V_i)$在这个方向的投影的绝对值之和最小

mathe · 发表于 2009-4-9 13:10:35

嗯,这个问题是一个$O(n\log(n))$的问题了. 首先将所有的$(U_i,V_i)$根据其幅角进行排序,这个需要$O(n\log(n))$的时间. 然后将所有角度分成若干个区间,在每个区间里面和函数$\sum_i|R_i|$连续可导,计算其导数(而在不同的区间,每一项的导数最多改变一个符号,而对于相邻的区间,通常只有一项的符号发生变化. 我们只要对于每种情况,分别判断其导数在对应的区间里面是否可以取零就可以找到所有的极值点.然后在加上边界点上的取值,所有这些值中的最小值就是所要的答案

账号		自动登录	找回密码
密码			欢迎注册

[原创] 算法问题请教

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。