如何在網格上找到最小總和路徑

當我必須從網格的左上角到右下角，並且所有數字的總和最小時，我遇到此問題。如何在網格上找到最小總和路徑

示例格

131, 673, 234, 103,18 
201, 96, 342, 965, 150 
630, 803, 746, 422, 111 
599, 720, 497, 121, 200 
342, 456, 744, 37, 331

的出把本應2297.

我不知道如何開始這個問題。

感謝

來源

2015-05-01 Ruth Shapiro

你可以看看這個 - http://en.wikipedia.org/wiki/Shortest_path_problem –

好吧，我不打算寫了所有的代碼，你，但我將有兩個單獨的函數，一個會列出所有可能的路線，然後第二個會被越來越評估每條路線該路線的總和。

暫時認爲只有兩個選項方向明智，下來或權利。所以第一條路徑是D，D，D，D，R，R，R，R，下一條路徑可能是D，D，D，R，D，R，R，R。等等等等。

對於每條路徑都有一個將這些數字相加的方法，無論哪條路徑最低都將是答案。

來源

2015-05-01 15:23:27

它也許值得閱讀http://heyes-jones.com/astar.php –

謝謝這是一個好的開始。 –

這是解決問題的不切實際的方法。路徑的數量隨着網格的大小呈指數增長。在花費一生的時間來枚舉所有路徑之前，它並沒有太大的意義。 –

@ArupRaksit是正確的：這是一個直截了當的最短路徑問題。

把它看作是一個有向網絡，每個數字代表一個節點。如果你能爲向右和向下移動對角線爲好，電弧會131->673，131->96，131->201，673->234，673->342，673->96， 200-> 331 , 37-> 331`。如果您只能向右或向下移動，請排除對角線對。

每條圓弧的長度爲f->t（「from」 - >「to」）爲f的值。例如，201->96的長度是201。或者，可以將每個弧的長度設置爲「到」節點t的值。它沒有區別，因爲所有路徑都包含始發地和目的地的節點，131和331。

然後，使用最短路徑算法（請參閱Wiki Arup參考資料），簡單計算從131到331的最短路徑。即使對於巨大的電網，也不需要任何時間來解決。

來源

2015-05-01 20:16:59

如何在網格上找到最小總和路徑

回答

相關問題