代码之家 › 专栏 › 技术社区 › James Thompson

距离矩阵的近似估计

approximation heuristics distance algorithm

James Thompson · 技术社区 · 15 年前

我有一组n个物体,我想计算一个nxn距离矩阵。有时我的n个对象集非常大,我想通过只计算距离比较的一个子集来计算nxn距离矩阵的近似值。

有人能给我指出一个计算全距离矩阵近似值的方向吗?我有一些想法,但我想避免重新发明轮子。

编辑:算法类型的一个例子可以利用这样一个事实:如果对象A和对象B之间的距离很小,而对象B和对象C之间的距离很小,则对象A和对象C之间的距离必须稍短。

4 回复 | 直到 15 年前

Community CDub 8 年前

老实说,我认为这取决于你希望你的近似值有多接近,以及你的子集有多大。如果您只想了解矩阵的整体外观,可以对随机子集(包括最大和最小节点)进行简单的线性插值,获得相当准确的(tm)结果。

我认为真正的诀窍是找出启发式(线性、二次等插值)和子集大小。您还可以计算出各种子集的距离矩阵,然后用某种方法(线性、球面线性、立方)对这些矩阵进行插值。

根据你最初的样本,这几乎是一个启发式的尝试和错误,直到你去“哦,那对我所需要的足够好了”。

如果你想了解矩阵的整体外观,你可以在一个随机子集上做简单的线性插值(包括最大和最小节点),得到相当精确的(tm)结果。

$linear interpolation$

根据你最初的样本,这几乎是一个启发式的尝试和错误,直到你去“哦,这足够好,我需要的”。

Grembo 15 年前

你的“对象”在网络上吗?如果对象在网络中,则可以使用 this 或 this 从而得到所有对的最短路径。如果不是的话,我想你很难计算出所有的n x n距离。

Chaitanya 15 年前

您需要的解决方案与我们在图中常见的类似,您可以使用 All pair shortest path 为了找到距离,你也可以看看 johnson's algorithm

Babamots 6 年前

我也有同样的问题,最后为它编写了python代码:

readme.md解释了如何使用三角形不等式更新每个距离的上限和下限。

只需在二维空间中以脚本的形式运行python文件即可。绘制的线是实际计算的唯一距离。

在我的版本中,节省的时间不在于拥有大量对象。正如我写的,这是一个O(n^4)算法,所以它实际上比计算所有距离(如果对象数量很大)更糟糕。但是我的方法会节省时间,当你有一个适度的对象数量和距离函数是非常昂贵的计算。它假设多个O(n^2)操作比单个距离测量更快。

如果n是大的,您可以寻找更便宜的方法来决定下一步要计算的距离(不包括带有n^2个距离边界矩阵条目的算术)。每次执行此代码时,也可能不需要更新所有2*n^2边界。