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

Question

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

通过使用三重嵌套循环可以非常低效地解决该问题。但有没有更快的矢量化解决方案？

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）