什麼是直覺behing的最優子？

Question

這個問題是從CLRS PG 362

整體最佳的解決方案結合了兩個相關的子問題的最佳解決方案相關的動態規劃和具體杆切削的問題。

整體最佳解決方案是通過尋找最佳的解決方案，以個別子問題，然後以某種方式俱樂部他們。我無法理解直覺和概念。任何鏈接，例子？

感謝

Answer 1

您可以比較動態規劃和貪婪的方法。

最優子意味着，最優解可以通過尋找最佳解決方案，以子問題被發現。如果不是這種情況下，除子問題的最優解的總和並沒有給我們最佳的全球性解決方案。

例如，考慮Dijkstra算法。如果我們知道從節點A到節點C比，我們可以利用這些信息來找到最短路徑到另一個節點，以及最短路徑。

如果不是這種情況，就不能構成最優解子問題，並得到全局最優解，不是我們可以用貪婪的方法。例如，看看change making problem。貪婪算法做出局部最優決策並找到一些解決方案，但這種解決方案不能保證是最優的。