检查大量 numpy 矩阵中的三角不等式

Question

我有一个非负浮点数的对称 NumPy 矩阵 D。第 i 行和 j 列中的数字表示对象 i 和 j 之间的距离，无论它们是什么。矩阵很大 (~10,000 rows/columns)。我想检查矩阵中的所有距离是否都服从三角不等式，即：D[i,j]<=D[i,k]+D[k,j] for all i, j, k.

这个问题可以通过使用三重嵌套循环来解决，但效率很低。但是是否有更快的矢量化解决方案？

Answer 1

你当然可以很容易地向量化最里面的循环（未经测试）：

for i in range(N):
    for j in range(i):
        assert all(D[i,j] <= D[i,:] + D[:,j])

对于双向量化，您可以循环遍历 k（也未测试）：

for k in range(N):
    row = D[k,:].reshape(1, N)
    col = D[:,k].reshape(N, 1)
    assert (D <= row + col).all()

(row + col 生成与 D 大小相同的方阵)

检查大量 numpy 矩阵中的三角不等式

Checking triangle inequality in a massive numpy matrix

python

algorithm

numpy

distance