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

scutan

想错了...

[ 本帖最后由 scutan 于 2009-1-10 09:32 编辑 ]

cjaizss

原帖由 贺兰云天 于 2009-1-8 21:22 发表
呵呵，我毕业时论文倒做过这个课题，智能交通系统的最近点查找，你这个可以抽象成一个最近邻居点问题

不一样吧,你这个是个图论问题,最近距离一定要在路上走,而不是直线距离.
lz的这个不是.

system888net

原帖由 cjaizss 于 2009-1-9 21:37 发表

不一样吧,你这个是个图论问题,最近距离一定要在路上走,而不是直线距离.
lz的这个不是.

同意,说到本质上了.

frog_skywalker

这类问题可以化为一个凸的混合整数非线性优化(MINLP)问题求解

看一下这篇文章,其实是一个ibm的研究报告
里面的slay,flay,clay都是类似的问题，具体可以看参考文献
Bonami, P.; Biegler, L. T.; et.al. An algorithmic framework for convex mixed integer nonlinear programs.
Discrete Optimization 2008, 5, (2), 186-204.

mingyanguo

不考虑太高深的算法的话，我觉得也许可以考虑把已有的所有点划分为N个区间，对每一个新遇到的点，首先判断该点在哪个区间，然后递归下去，最后一个区间只有一个点，就是所找的点。划分区间的方法也许可以类比一下，一维空间，一个区间是[x0, x1]，数轴表示的话是个线段；二维空间，可以用方格划分区间一个区间是一个正方形；三维空间，可以用正方体划分区间，一个区间是一个正方体；以此类推……
这样划分以后只需要考察点所落入的区间与相邻的区间即可。没详细画图推算，感觉上似乎可以一试。
直觉上说，我觉得这个问题应该有数学背景，不过我的数学停留在初中水平，不知道具体是什么背景，姑且一说。

duanjigang

原帖由 cjaizss 于 2009-1-9 21:37 发表

不一样吧,你这个是个图论问题,最近距离一定要在路上走,而不是直线距离.
lz的这个不是.

你理解错了或者是我没说对，我那个是直线距离的。。。。。。。。。。。
难道你看不出来 (X1-X2)^2+(Y1-Y2)^2这种函数和(X1-X2)^2+(Y1-Y2)^2+(Z1-Z2)^2+····
同属于两点之间的距离问题吗？？？
只是维数不同。。。物理意义却是相同的 都是距离问题
前者是二维空间的距离。。后者是N维空间的距离。

[ 本帖最后由 duanjigang 于 2009-1-10 19:22 编辑 ]

mwishes

恩, 各位分析很有意思, 引申到K-D tree, 到图论, 和数据挖掘中的 KNN 算法也有几分相似.

ljoo

嗯,看一下

[ 本帖最后由 ljoo 于 2009-1-12 15:00 编辑 ]

lenin

如果不是稀疏矩阵也没什么可优化的
这种东西，如果你用GPU，比如Nvidia的CUDA算会超级快

RobinHoo

KD-Tree是正解