穿越迷宮的最佳路線

給出了尺寸爲(m,n)的二維整數矩陣，允許一個人從(0,0)到(m-1,n-1)遍歷。有效的舉措是正確的或正在降低。我被要求找到到達目的地的最大總和路徑。這是因爲穿越迷宮的最佳路線

MaxPathSum(i,j) = Math.max(MaxPathSum(i,j-1),MaxPathSum(i-1,j)) + Matrix[i][j]

但是很簡單，如果有兩個人都被允許穿越從(0,0)到(m-1,n-1)。一旦這個單元被某人訪問過，一個單元的值將被設置爲零。考慮到這個約束條件，這兩條路徑的最大總和是多少？

任何提示表示讚賞。謝謝。

來源

2016-08-30 zqzwxec

原始問題的哪一部分表示單元在遍歷時變爲零？ –

你只有兩個選擇，正確和下降。如果右邊的單元格變爲零，那麼對方的唯一選項就會關閉。他們輪流輪流嗎？還是一個人在另一個之前完成了迷宮？ –

@ cricket_007：我發現也很困惑，但我相信第二段中會給出部分問題。 – LarsH

首先要注意的是，每個步驟總是將曼哈頓與原點（x + y）的距離增加1。這意味着，如果您一次向兩個路徑移動兩個標記，交替移動兩個標記，那麼如果路徑穿過計數器必須相互重疊：您不能讓一個標記達到一個正方形，而另一個則不能移動。

現在您可以將原始MaxPathSum（i，j）= ...計算爲狀態空間中動態程序，其中狀態是單個標記的位置。對於兩條路徑，一個顯而易見的事情就是在狀態空間中運行一個動態程序，其中狀態是兩個標記的位置。那麼你可以有MaxPathSum（i，j，k，l）= ...其中一個更復雜的表達式考慮兩個標記的四種可能的移動並且確保Matrix [i，j]不被計數兩次如果i == j & & k == l。由於我們上面已經弄清楚，我們只需要考慮這種形式的衝突，所以我們不必記住這些標記已經到達他們當前位置的路徑。

這看起來像它正方形狀態空間的大小。這很糟糕，但不是那麼糟糕，再次因爲曼哈頓的距離限制。您可以通過一系列步驟進行遞歸計算，每個步驟計算出距離原點的曼哈頓特定距離狀態的所有答案。你只需要考慮具有相同曼哈頓差異的狀態對。如果您有NxN陣列，則原始計算的成本爲O（N^2）。如果你想在步驟中做到這一點，每個步驟涵蓋所有具有特定曼哈頓距離的單元，那麼你有O（N）個步驟，每個步驟都覆蓋O（N）單元。如果您擔心兩條路徑，那麼您仍然有O（N）個步驟，但每個步驟都包含O（N^2）個單元對，因此總成本爲O（N^3） - 但輸入數據（矩陣）大小爲O（N^2），因此您可以同樣認爲這是O（N^1.5）或將原始成本提高到功率1.5。

來源

2016-08-31 04:46:32 mcdowella

如果值是非負值（> = 0），而不是一對不相互交叉的最大路徑。它可以通過施工檢查。

假設最大的路徑（A和B）相互交叉，如：

..B. 
.B.A 
AXA. 
.B..

比我們可以互換的路徑部分只是彼此接觸，其中總和是相同的。

..A. 
.A.B 
AXB. 
.B..

由於值是非負的，新的路徑之和> =其原始A的+ B

..A.  ..A. 
AA.B or .A.B 
ABB.  AAB. 
.B..  .BB.

在我看來，一些DP溶液應該存在，但我不能找到一個:-)

有一個貪婪的方法，找到相當好的解決方案。它使用兩個獨立的路徑可以通過上層操作來改進的屬性。算法如下：

find first maximal path 
set 0 to path elements 
find second maximal path 
improve paths with upper operations

不優選部分是在第一個路徑元素上設置的零。這些零強制第二條路徑不跨越第一條路徑。改進操作使用交叉點周圍的元素，因此改進會在結果中添加一些相鄰元素。它可用於將第一個路徑元素設置爲某個鄰居的值的值。現在，我不確定使用哪個鄰居，因爲有更多的組合，特別是如果交叉是較長的重疊。我認爲這個好的起點是將其設置爲最小可能的鄰居的價值。

來源

2016-09-05 08:54:22 Ante

穿越迷宮的最佳路線

回答

相關問題