请教, 谁对求欧氏距离最小值有研究

scutan

对于一组数据[x1 x2 x3 x4 x5 x6 x7] 每个数据为 float型, 有很多个文件, 在每个文件中有很多组这样的数据. 每个float在0-100之间
现在得到一组参考数据[y1 y2 y3 y4 y5 y6 y7], 在那些文件中去找到一组数据使得
(y1-x1)^2 + (y2-x2)^2 + ... + (y7-x7)^2的值最小.

若采用遍历的方式去查找不能满足性能上的要求, 那么想请教一下, 该怎样对这些数据进行排序, 以使得能以最快的速度找到?
谢谢.

mwishes

原帖由 marco_hxj 于 2009-1-8 21:30 发表

蚂蚁算法？

分析了下题目,我的直觉和15楼一样, 启发式搜索? 但是, 蚁群也好,遗传也好,模拟煺火也好, 归根在于产生一个能约束在题设中的收敛序列. 但是, 就题目本身而言:  N个文件, 每个文件Si个数据项.  如果遍历的话, 算法复杂度是 O( 求和Si(i 属于 1,...,N));
问题本身就是线性的. 而这个时候启发式搜索反而在使问题变复杂. 可以做如下假设:
对于任意文件看成一个部落. 我可以这么理解问题,  为了简化计算(x和y的Euler距离), 对于文件中的记录, 每两两组对,如果可以只计算x和配对的组中一个组员euler距离的话, 计算规模减少1/2.  但是为了达到这个目的,可以让这 S/2个组对进行遗传演化, 让所有组对成员之间euler距离之和最小... 而这个演化过程将远远超出减少的1/2规模. 也就是说问题反而变复杂了. 启发式搜索是为了求取一个NPC问题的局部最优解而有效...
因此,从算法本身上来看. 遍历似乎已经是最优的解决办法了,尚且不能满足需求的话, 或者真的只能从架构上想办法了, 比如试试 map-reduce ?

[ 本帖最后由 mwishes 于 2009-1-9 00:23 编辑 ]

r2r4

大手笔～
30
mk，期待

ljoo

差的绝对值和最小?
不懂,看看.

reiase

不用欧氏距离能快很多...然后争取构造个结构，作二分查找吧
考虑下1范距离与无穷范距离

[ 本帖最后由 reiase 于 2009-1-8 20:12 编辑 ]

scutan

原帖由 reiase 于 2009-1-8 20:10 发表
不用欧氏距离能快很多...然后争取构造个结构，作二分查找吧
考虑下1范距离与无穷范距离

不是很明白呢.

reiase

欧氏距离需要计算n次乘法，n－1次加法，一次开方；1范 距离需要n－1次加法；无穷范距离需要n－1次比较大小；三种范数距离不相等，但是对大多数应用，三者效果差不多，但是计算量上差很多

scutan

实际上我这儿主要就是相减求平方, 经过测试, 计算时间是很短的. 关键是数据量太大, 怎样对那些文件中的数据进行合理地组织是个问题.

bbmmzz

我想到的是把数据按照公式(y1-x1)^2 + (y2-x2)^2 + ... + (y7-x7)^2转换成矩阵相乘的形式，可能有数值计算的方法减少运算量

reiase

计算时间短不是不优化的理由阿，如果程序80%以上的时间在计算欧拉距离，优化距离计算还是有必要的。俺只是指距离计算这一点上的问题，数据组织没背景不好讲