dynamic - 最適な下部構造の背後にある直感とは何ですか?

Question

この質問は、動的計画法、特にCLRS Pg 362のロッド切断問題に関連しています

全体の最適解には、関連する 2 つの部分問題に対する最適解が組み込まれています。

全体的な最適解は、個々の部分問題に対する最適解を見つけて、何らかの方法でそれらをクラブ化することによって得られます。直感と概念が理解できません。リンク、例はありますか？

ありがとう

Answer 1

動的計画法と貪欲なアプローチを比較できます。

最適部分構造とは、部分問題の最適解を見つけることによって最適解を見つけることができることを意味します。そうでない場合、部分問題の最適解の合計は、最適なグローバル ソリューションを提供しません。

たとえば、ダイクストラのアルゴリズムを考えてみましょう。ノード A からノード C への最短経路がわかれば、この情報を使用して別のノードへの最短経路も見つけることができます。

そうでない場合、貪欲なアプローチを使用するよりも、部分問題の最適解を構成してグローバルな最適解を得ることができません。たとえば、変更作成の問題を見てください。貪欲なアルゴリズムは局所的に最適な決定を行い、何らかの解を見つけますが、この解が最適であるとは限りません。