有向無環圖的最短路徑

Question

所以基本上，我有一個n乘m的浮點值數組，我試圖找到任何第1行值和第m行值之間的最短路徑。圖中的節點(i, j)對於任何不處於邊緣(0 < i < n-1)且不在最後一行(j < m-1)的節點都有子節點{(i, j+1), (i-1, j+1), i+1, j+1)}。我正在尋找一種算法來及時解決這個特定的問題。我目前的思路圍繞A *搜索展開，但讓我知道您的想法。

Answer 1

• 列表項

動態的解決方案是O（NM）或O-（M^2）。而且它不能在這下 - 這是任何更好的解決方案的反例。假設您想要在第一行的最左邊的元素和最後一行的最左邊的元素之間找到路徑。讓我們來看看這種形式的矩陣：

10000000000000 
11000000000000 
11100000000000 
11110000000000 
11111000000000 
11111100000000 
11111110000000 
11111111000000 
11111110000000 
11111100000000 
11111000000000 
11110000000000 
11100000000000 
11000000000000 
10000000000000 

「1s」是您可能在從源到目標元素的路徑上經過的元素。 「0」是你無法通過的元素。 O（NM）（實際上，Min（NM，M^2），見下文）。「1」的數目是NM/4次序。因此，讀取矩陣中每個1的算法將具有> = O（NM）的複雜性。

另一方面，不讀取所有「1」的算法將不正確。

證明：讓矩陣中的數字爲權重。選擇一個「1」算法不會讀取。將該1更改爲0.5。該算法對於此輸入失敗，因爲最佳路徑現在通過它從不讀取的元素（因爲它第一次讀取的元素沒有改變，所以這次也讀取相同的元素，除非它是非確定性的，在這種情況下，它是一個隨機的機會是否會起作用，這也使得它不正確）。

但是，良好的O（NM）解決方案應該適用於1000x1000矩陣（不到一秒）。如果您只擊中了必須擊中的元素（例如，在我的示例矩陣中，如果寬度增加到10000000，則無需讀取添加的元素），您可以將其優化爲Min（M^2，MN） ）。同樣，如果高度增加到10000000，則沒有M^2順序讀取，因爲您沒有超出矩陣的邊界。然而，正如你所說，這兩個維度都非常大，我猜這沒什麼幫助。