動的プログラミングアルゴリズムと現実の利用

Question

私はこれまで、古典的なDP問題とアルゴリズム（コイン、最長増加サブシーケンス、最長共通サブシーケンスなど）を研究しました。

私はこれらのアルゴリズムが実用的なアプリケーションを持っていることを知っています。私はこれらのアルゴリズムが入力のサイズが非常に大きく、問題が1台のマシンで解決できない最新のコンピュータサイエンスで実用的なアプリケーションを持っているかどうかです。

これらのアルゴリズムは並列化が非常に難しく（つまり、Parallel Dynamic Programming）、メモリ占有率はほとんどのフォーミュレイションでは2次であり、かなり大きな入力を処理することが難しいということです。

誰でもこれについて実際の使用例がありますか？

Answer 1

実用アプリケーション：diff。これは、DPアルゴリズムを使用してlongest common subsequence問題を解決することによって、2つのファイルの違いを見つける必須のLinuxユーティリティです。

DPアルゴリズムが使用されるのは、多くの場合、実際の唯一の解決策であるためです。それに加えて、彼らには何も間違っていません。

メモリ使用量：多くの場合、スライディングウィンドウを使用してメモリ使用量を大幅に減らすことができます。フィボナッチは、ナイーブなボトムアップDPを使用して解決されると、O（n）メモリを必要とします。スライディングウィンドウはこれをO（1）メモリに改善します（私はmagical constant time solutionを知っていますが、それはそのポイントの横です）。

パラレル化：トップダウンDPは、しばしば並列化が容易です。ボトムアップはそうかもしれないし、そうでないかもしれない。 @ amitの例（並列化最長共通部分列）は良いものです。与えられた対角のタイルは、前の対角線が分かっている限り独立して解くことができます。

Answer 2

The longest common subsequence問題およびLongest common substring problemは、[遺伝子配列の分析などの]文字列解析に重要なことがあります。ダイナミックプログラミングを使用して効率的に解決できます。

注あなたは、このアルゴリズムを並列化することができます：[アップ、右下、左から]あなたは、対角線上の反復でそれを行う - そう2n-1反復の合計。すべての対角線では、各セルはこの対角線上の他のセルに依存しないため、ここで並列化を行うことができます。各スレッドはこの対角線内にセルブロックを持ちます。

この方法を使用したデータ同期も最小限であることに注意してください。各スレッドは、メモリが共有されていなくても実行できるように、「隣接スレッド」にデータを転送するだけでよい。

@larsmansにも言及されているように、線形空間を使うことができます。それぞれの点で、現在の+2最後の対角線を「記憶」するだけで、マトリックス全体を記憶する必要はありません。

動的プログラミングを使用して解決される別のよくある問題はpolynomial interpolationです。補間はNewton Interpolationを使用して効率的に行うことができます。最初に動的プログラミングを使用して構築されたdivided differencesを計算する必要があります。