距離矩陣的近似估計

Question

我有一組N個對象，我想計算一個NxN距離矩陣。有時我的N個對象集非常大，我想通過計算距離比較的一個子集來計算NxN距離矩陣的近似值。

任何人都可以指出我計算近似矩陣的方向嗎？我有一些想法，但我想避免重新發明輪子。

編輯：算法類型的一個例子將利用如下事實：如果對象A和對象B之間的距離非常小，並且對象B和對象C之間的距離非常小，對象A和C之間的距離稍短。

Answer 1

老實說，我認爲這取決於你想要近似的距離以及你的子集有多大。如果您只想總體瞭解矩陣的外觀，您可以對隨機子集（包括最大和最小節點）進行簡單的線性插值，以獲得非常準確的結果。

我覺得這裏真正的關鍵是找出啓發式（線性，二次插值等）和子集大小。你也可以計算出不同子集的距離矩陣，然後用某種方法（線性，球形線性，立方）插入這些矩陣。

根據您的初始樣本，它幾乎是一個啓發式的試驗和錯誤，直到你去「哦，這足夠滿足我所需要的」。

Answer 2

您的「對象」是否在網絡上？如果對象位於網絡中，則可以使用this或this來生成全部最短路徑。如果不是的話，我想你幾乎堅持計算所有n×n的距離。

Answer 3

你需要是類似於我們在圖中看到普遍的解決方案，你可以使用All pair shortest path尋找的距離，你也可以看看johnson's algorithm