質問: 動的プログラミングアルゴリズムと実際の使用法 私は古典的なDP問題とアルゴリズム(コイン、最長増加サブシーケンス、最長共通サブシーケンスなど)を過去に研究しました。 私はこれらのアルゴリズムが実用的なアプリケーションを持っていることを知っています。私はこれらのアルゴリズムが入力のサイズが非常に大きく、問題が1台のマシンで解決できない最新のコンピュータサイエンスで実用的なアプリケーションを持っているかどうかです。 私の指摘は、これらのアルゴリズムは並列化が非常に難しいことです(つまり、並列動的プログラミング)、メモリ占有ほとんどの調合では二次的なので、合理的に大きな入力を処理することは困難です。 誰もがこれに関する実世界のユースケースを持っていますか?
回答: The **longest common subsequence** problem and **Longest common substring problem** are sometimes important for analyzing strings [analyzing genes sequence, for example]. And they can be solved efficiently using dynamic programming. **このアルゴリズムを並列化することができます**。対角線上の反復で[左から、右へ、上へ] - 合計で `2n-1` 回の反復を行います。すべての対角線では、各セルはこの対角線上の他のセルに依存しないため、ここで並列化を行うことができます。各スレッドはこの対角線内にセルブロックを持ちます。 この方法を使用したデータ同期も最小限であることに注意してください。各スレッドは、メモリが共有されていなくても実行できるように、「隣接スレッド」にデータを転送するだけでよい。 また、@ larsmansが指摘しているように、線形空間を使うこともできます。それぞれの点で、行列全体ではなく、現在の+2最後の対角線を「記憶」するだけです。 **Another common problem** that is solved using dynamic programming is **polynomial interpolation**. The interpolation can be effieciently done using Newton Interpolation, which first needs to calculate the divided differences - which is built using dynamic programming.