Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords

algorithm動的プログラミング


前書き

ダイナミクスプログラミングは広く使われているコンセプトであり、しばしば最適化に使用されます。これは、複雑な問題を単純なサブ問題に再帰的に分割することによって、複雑な問題を単純化することを指します。通常、ボトムアップアプローチです。動的プログラミングを「最適な基礎構造」および「重複するサブ問題」に適用するためには、問題が持つべき2つの重要な属性があります。最適化を達成するために、ダイナミクスプログラミングでは、記憶

備考

ダイナミックプログラミングはブルートフォースの改良です。ブルートフォースからどのようにダイナミックプログラミングソリューションを得ることができるかを理解するこの例を参照してください。

動的プログラミングソリューションには2つの主な要件があります。

  1. 重複問題

  2. 最適な下部構造

問題が重複しているということは、元の問題の解決策に到達するために、問題のより小さなバージョンの結果が複数回再利用されることを意味します

最適部分構造とは、そのサブ問題から問題を計算する方法があることを意味します。

動的プログラミングソリューションには、2つの主要コンポーネント、 状態遷移があります

国家は、元の問題のサブ問題を指す。

遷移は、問題をそのサブ問題に基づいて解決する方法です

ダイナミックプログラミングソリューションによる時間は、[状態数] No. of States * Transition Timeとして計算できます。したがって、解がN^2状態を持ち、遷移がO(N)ならば、解はおおよそO(N^3)時間かかるだろう。

動的プログラミング 関連する例