dynamic-programming - 動的計画法と分岐限定の違いは何ですか?

Question

分枝限定によって、解決策を得るために手順を削減できることだけは知っていますが、それは解決空間ツリーを持つ問題にのみ役立ちます。

Answer 1

動的プログラミングには、再帰構造 (別名、CRLS の最適部分構造) が必要です。つまり、特定の状態で、部分的なソリューションに基づいて最適な決定を特徴付けることができます。

分枝限定法はより一般的であり、解空間の暗黙的な列挙を介してより困難な問題を解決するために使用されます。