algorithm - 距离矩阵的近似估计

Question

我有一组 N 个对象，我想计算一个 NxN 距离矩阵。有时我的 N 个对象集非常大，我想通过仅计算距离比较的一个子集来计算 NxN 距离矩阵的近似值。

任何人都可以指出计算全距离矩阵近似值的方向吗？我有一些想法，但我想避免重新发明轮子。

编辑:算法类型的示例将利用以下事实:如果对象 A 和对象 B 之间的距离非常小，并且对象 B 和对象 C 之间的距离非常小，则必须对象 A 和 C 之间的距离要短一些。

Answer 1

我有同样的问题并最终为它编写了 Python 代码:

https://github.com/jpeterbaker/lazyDistance

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

只需将 Python 文件作为二维空间示例的脚本运行即可。绘制的线是实际计算的唯一距离。

在我的版本中，节省时间与拥有大量对象无关。正如我所写的那样，它是一个 O(n^4) 算法，所以如果对象数量很大，它实际上比只计算所有距离更糟糕。但是，当对象数量不多且距离函数的计算成本很高时，我的方法会节省时间。它假设执行多个 O(n^2) 操作比执行单个距离测量更快。

如果 n 很大，您可以寻找更便宜的方法来决定接下来要计算哪个距离(不涉及具有 n^2 个距离边界矩阵条目的算术)。您也可能不需要每次执行此代码时都更新所有 2*n^2 边界。