動的計画法を問題に適用するには、次のことが必要です。
私。サブ問題の最適な構造:
つまり、問題をより小さな単位に分割する場合、最適なソリューションを得るには、それらのより小さな単位もさらに小さな単位に分割する必要があります。たとえば、マージソートでは、数値の配列を2つのサブ配列に分割し、それらを並べ替えて結合すると、数値の配列を並べ替えることができます。これらの2つのサブ配列をソートしながら、前の文で行ったのと同じプロセスを繰り返します。したがって、そのサブ問題の最適な解決策を見つけると、最適な解決策(並べ替えられた配列)が得られます(サブ配列を並べ替えて結合します)。この要件は、マージソートで満たされます。また、サブ問題は、それらが最適な構造に従うために独立している必要があります。サブ問題のソリューションは互いのソリューションの影響を受けないため、これはマージソートによっても実現されます。例えば、
ii。重複するサブ問題:
これは、解を解く間、定式化するサブ問題が繰り返されるため、一度だけ解く必要があることを意味します。マージソートの場合、この要件が通常の場合に満たされることはめったにありません。2 1 3 4 9 4 2 1 3 1 9 4のような数値の配列は、マージソートのサブ問題を重複させるのに適した候補です。この場合、サブ問題sort(2 1 3)の解は、計算中に2回呼び出されるため、再利用するためにテーブルに格納できます。しかし、ご覧のとおり、ランダムな数の配列がこの種の繰り返しの工夫をする可能性は非常に低いです。したがって、マージソートなどのアルゴリズムにメモ化などの動的計画法を使用した場合にのみ非効率になります。
はい。ダイクストラのアルゴリズムは、コメントで@Alanが述べているように動的計画法を使用しています。リンク
はい。ここでウィキペディアを引用すると、「動的計画法は、配列アラインメント、タンパク質フォールディング、RNA構造予測、タンパク質-DNA結合などのタスクのためにバイオインフォマティクスで広く使用されています。」1
1 https://en.wikipedia.org/wiki/Dynamic_programming