算法问题请教
表达式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为求绝对值
∑ 为求和
那位知道用什么算法
请教 因为 ∑ abs（Ri ） >= 0，而当 a = b = 0 时，∑ abs（Ri ） = 0，所以，
a = 0，b = 0
就是答案。
建议 LZ，还是改用最小二乘法吧 估计要添加$a^2+b^2=1$的条件.
不过使用绝对值的表达式很难用最小二乘法来算极值 我们可以记$U_i={X_i-X_0}/{{C_i}/{C_0}},V_i={Y_i-Y_0}/{{C_i}/{C_0}}$
我们相当于要找一个方向,使得所有的点$(U_i,V_i)$在这个方向的投影的绝对值之和最小 嗯,这个问题是一个$O(n\log(n))$的问题了.
首先将所有的$(U_i,V_i)$根据其幅角进行排序,这个需要$O(n\log(n))$的时间.
然后将所有角度分成若干个区间,在每个区间里面和函数$\sum_i|R_i|$连续可导,计算其导数(而在不同的区间,每一项的导数最多改变一个符号,而对于相邻的区间,通常只有一项的符号发生变化.
我们只要对于每种情况,分别判断其导数在对应的区间里面是否可以取零就可以找到所有的极值点.然后在加上边界点上的取值,所有这些值中的最小值就是所要的答案
页:
[1]