以小於k步驟計算從節點i移動到i的方法的最佳方法

Question

我有一個n * n無向圖。我必須找到一種方法，以小於k的步幅從某個節點移動到相同節點。我需要比k * n^3更快的方法。

Answer 1

我會從開始節點回到自己做一個A *的修改版本。你所要做的就是改變最終條件。

所以，一旦你到達目標節點，你只能在達到k步時結束。您將以i-> i開始，成本爲零，然後根據A *展開子節點。在所有這些後續步驟中，如果您達到目標，請記錄路徑;如果您仍處於k個步驟的限制範圍內，請繼續展開節點並在到達i時打印路徑。

一旦達到k個步驟的限制，就結束循環。

編輯：我想我沒有解釋爲什麼我會用A *去。如果您不熟悉A *（you can read more here），那麼這是一種最佳優先搜索算法。這意味着它將選擇可用節點集合中的最佳節點來構建路徑（最好意味着到目標的最短距離）。這是基於訪問節點的已知成本，以及對目標距離多遠（通常是用歐幾里得距離）的猜測。

我認爲A *對於這個問題會很好的原因是因爲你已經知道你在追求目標，所以它本質上是爲你工作，尋找下一個最好的路徑，直到你告訴它停止或它展開圖中的所有節點。