查找路徑的動態編程

鑑於成本成本矩陣成本[] []和一個位置（m，n）的[] []，寫返回最小成本的成本函數從（0，0）到達（m，n）的路徑。查找路徑的動態編程
矩陣的每個單元格表示穿過該單元格的成本。達到的路徑的總成本（m，n）是該路徑（包括源和目標）上上所有成本的總和。（i，j），單元格（i + 1，j），（i，j + 1）和單元格單元格中的單元格只能從一個向下，右對角，（i + 1，j + 1）可以遍歷。
您可能會認爲所有成本都是正整數。

我能找到的最低成本和這篇文章被證明是非常有幫助的：

http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/

dp http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/dp2.png

但它並不能說明實際路徑（0,0） - >（0,1） - >（1,2） - >（2,2）時必須遵循的。如何找到路徑？

來源

2013-12-22 Vijender

只要跟蹤哪個單元格是父級... –

您可以接受正確的答案;說明問題已經解決。 –

當你要搜索的路徑，也保持跟蹤你正在做的，即當你選擇在這個聲明中最小的決定（取自你引用的文章）：

return cost[m][n] + min(minCost(cost, m-1, n-1), 
          minCost(cost, m-1, n), 
          minCost(cost, m, n-1));

您還需要跟蹤哪個元素是最小的（例如，在具有方向（左，上，左上）的單獨矩陣中）。然後，您可以從矩陣的最後一個元素中回溯並重建路徑。

這基本上是具有反向跟蹤的Levenshtein距離，您可以找到一個僞代碼實現，例如， here

來源

2013-12-22 10:39:56

'分鐘（minCost（成本，M-1，N-1）， minCost（成本，M-1，N）， minCost（成本，M，N-1））;' 使用上述式I會發現許多最小元素（每三個中有一個），但這並不意味着它們都將成爲最終路徑的一部分。你能分享一些僞代碼嗎？ – Vijender

看到我編輯的答案，希望我澄清這一點。 –

由於我們在使用輔助數組的最大常見子序列問題中使用箭頭保持軌跡，因此同樣在這裏我們可以跟蹤哪個元素返回最小值。然後從單元格（m，n）開始按照您存儲的箭頭回溯。

來源

2014-04-25 08:39:24 user3552407

這不提供問題的答案。要批評或要求作者澄清，在他們的帖子下留下評論 - 你可以隨時評論你自己的帖子，一旦你有足夠的[聲譽]（http：// stackoverflow。com/help/whats-reputation）你將能夠[對任何帖子發表評論]（http://stackoverflow.com/help/privileges/comment）。 – StarsSky

@StarsSky這確實提供了一個答案，如果我沒有弄錯。這是我的解決方案：http：//ideone.com/i3AtVG – user3552407

查找路徑的動態編程

回答

相關問題