實現通過螺紋動態規劃ALGO緊固式

Question

說我有這非常常見DP問題（動態編程） -

鑑於成本矩陣成本[] []和一個位置（m，n）的成本[] []，寫一個函數，返回從（0，0）到（m，n）的最小代價路徑的代價。矩陣的每個單元代表穿過該單元的成本。達到的路徑的總成本（m，n）是該路徑上的所有成本（包括源和目標）的總和。 （i，j），（i，j + 1）和（i + 1，j + 1）中的單元格， j + 1）可以遍歷。你可以假設所有成本都是正整數。

PS：回答這個 - 8

現在，解決這個問題..以下問題後，在我腦海中跑了。

說我有1000 * 1000矩陣。和O（n^2）將需要一段時間（當然是在intel i5上1秒<）。 但我可以進一步減少它。說使用這種算法開始6-8線程，然後同步他們到最後得到答案？不會很快實現，甚至在邏輯上可以得到答案，或者我應該拋出這個心思都

Answer 1

一般來說，在這樣的小問題（如你所說< 1秒），並行計算比連續效率較低，由於協議開銷（線程啓動和同步）。另一個問題可能是，由於您要從輸入中「隨機」（非線性）選擇要操作的數據，因此您會增加高速緩存未命中率。但是，當涉及到更大的問題時，如果矩陣的條目數量是10倍，那麼肯定值得一想（或兩個）。

這是一個可能的解決方案。給定一個16x16的矩陣，我們將它切成4個相等的正方形。對於每個方塊，都有一個線索負責。每個小方塊中的數字表示在多少時間單位之後，可以計算該方塊的結果。

因此，總時間是33個單位（無論單位是什麼）。與具有64個單元的順序解決方案相比，它只是其中的一半。你可以相信，任何2^k x 2^k矩陣的運行時間是2 ^（2k - 1）+1。

但是，這只是我想到的第一個想法。我希望外面的世界有更快的並行解決方案。更重要的是，由於我在答覆開始時提到的原因，出於所有實際的目的，我的解決方案無法實現2的加速。

Answer 2

我會從算法改進開始。無需測試N 解決方案。

一個關鍵是您從哪個方向進入廣場。如果您通過向下移動來輸入它，則無需檢查右側的方格。同樣，如果您通過向右移動來輸入它，則不需要從那裏向下檢查路徑。直角轉彎的目的地總是可以通過對角線移動到達，而忽略一個正方形及其正面重量/成本。

就線程而言，我可以看到（至少）一些分解事情的方法。其中一個就是簡單地排隊請求，當你輸入一個正方形。即，而不是（例如）測試另一個方塊，它排隊請求測試其兩個或三個出口。 N個線程處理這些請求，這些請求會生成更多請求，直到所有請求都到達終點。

這有一個明顯的缺點，就是在序列碼可能放棄它們之後，你可能會繼續遍歷一些路由，因爲它們已經比迄今爲止的最短路由長。

另一種可能性是啓動兩個線程，一個向前移動，另一個向後移動。在每一箇中，你找到沿着對角線到任何給定點的最短路徑，然後你將剩下一個純粹的線性掃描，通過這些候選人找到最短的總和。