問題タブ [dynamic-programming]

動的プログラミングは、ほぼ定義上、暗黙的な DAG で最短/最長のパスを見つけることです。すべての DP アルゴリズムはこれを行うだけです。

ホログラフィック アルゴリズムは、暗黙的な平面グラフの完全な一致をカウントするものとして大まかに説明できます。

だから、私の質問は、かなりのスピードアップを達成するために暗黙的なグラフでよく知られているアルゴリズムを使用するアルゴリズムの他のファミリーはありますか?

このアルゴリズムをどのように設計するのが最善かについて混乱しています。船には x 人の海賊がいて、j^番目の海賊の年齢は a _jで、j^番目の海賊の体重は w _jです。私は、すべての海賊の 25 パーセンタイルから 75 パーセンタイルの重みを持つ最年長の海賊を見つける動的計画法アルゴリズムを考えています。しかし、私はどのように進めるかについて無知です。

2 つの非常に大きな文字列があり、それらのLongest Common Substringを見つけようとしています。

1 つはサフィックス ツリーを使用する方法(複雑な実装ですが、非常に複雑であると想定されます) であり、もう 1 つは動的プログラミング方法です(どちらも上記のリンク先の Wikipedia ページで言及されています)。

動的計画法の使用

問題は、動的計画法の実行時間が非常に長いことです (複雑さはO(n*m)で、nとmは 2 つの文字列の長さです)。

私が知りたいこと (接尾辞ツリーの実装にジャンプする前に):共通部分文字列の長さだけを知りたい場合 (共通部分文字列自体ではなく)、アルゴリズムを高速化することは可能ですか?

私はこのプログラムを持っています

動的計画法を使用して高速化することは可能ですか?

この関数は O(2^n) で実行されることがわかりました

動的計画法で実行時間を短縮することになっているのですが、概念がわかりません。

正しい方向へのナッジを求めるだけです。

動的計画法でドットゲームの変種を解こうとしています。

通常のドットゲームは、ドットのラインでプレイされます。各プレーヤーは、ラインのそれぞれの端で1つまたは2つのドットを取り、ドットがないままになっている人が勝ちます。

このバージョンのゲームでは、各ドットの値が異なります。各プレイヤーは交互にターンし、ラインの両端でいずれかのドットを取ります。動的計画法を使用して、最初のプレーヤーが勝つことが保証されている最大量を見つける方法を考え出したいです。

私はこれについて頭を抱えて、解決策の繰り返しを書き込もうとして問題を抱えています。どんな助けでもありがたいです、ありがとう！

シーケンスが与えられた場合、たとえば 222 隣接する各ペアの間に「+」または「*」を配置する必要があります。「*」は「+」よりも優先されます

評価が最小値につながる文字列を o/p する必要があります。O/p が複数ある場合、辞書式に最小でなければなりません。

inp:222

o/p: 2*2+2

説明:

2+2+2=6

2+2*2=6

2*2+2=6

この 3 番目の は、辞書編集的に最小です。

このためのDPソリューションを構築する方法を考えていました。

ステレオマッチング問題の動的計画法アルゴリズムを実装することになっています。私は 2 つの研究論文を読みましたが、そのための独自の C++ プログラムを作成する方法についてはまだ理解していません。

実際にコーディングを開始する方法についてのアイデアを得るために使用できる本やリソースはありますか?

インターネット検索では、動的プログラミングに関するジャーナルと会議論文のみが表示されますが、アルゴリズムを段階的に実装する方法は表示されません。

ありがとう

ヴァルン

次の MATLAB コードをベクトル化したいと考えています。私はそれが単純でなければならないと思いますが、それでも混乱しています。

このコードは、別のスコア テーブルCから動的計画法アルゴリズムのスコア テーブルSを計算します。対角合計は、 C を生成するために使用されるデータの個々の部分のスコアを生成することです。

ご回答ありがとうございます。これが明らかな場合は申し訳ありません...

私の eye(r) は非常に小さい ( 5 <= r <= 20 ) ため、組み込みのconv2
は convnfft よりも高速であることが判明しました。convnfft.m は、メリットが現れるには r > 20 である必要があると述べています。

連鎖行列の乗算とは何か、通常の乗算​​とはどのように違うのかを理解しようとしています。私はいくつかの情報源をチェックしましたが、すべてが私が理解できるように非常に学術的に説明されているようです。

最適化された方法で操作を実現するのは動的計画法アルゴリズムの一種だと思いますが、それ以上は進みませんでした。

ありがとう

同じ数の行とさまざまな数の列 (20 x 〜 200) を持つ約 5,000 の行列があります。これらの各行列は、動的計画法のアルゴリズムで互いに比較する必要があります。

この質問では、比較をすばやく実行する方法を尋ねたところ、2D 畳み込みに関する優れた回答が得られました。その方法を順番に、繰り返し適用して、

データの小さなサブセットでは高速です (たとえば、9 つの行列の場合、9*9 - 9 = 72 回の呼び出しが ~1 秒で行われ、870 回の呼び出しが ~2.5 秒で行われます)。
ただし、すべてのデータを操作するには、約 2,500 万回の呼び出しが必要です。
また、deal() を使用して、データ内の次の要素だけで構成されるセル配列を作成しようとしたので、単一のループで cellfun() を使用できました。

残念ながら、これは実際にはそれほど高速ではありません。これらのコード例は両方とも、並列化には適していないようです。変数をスライスする方法がわかりません。
compare() は完全にベクトル化されています。行列の乗算と conv2() のみを使用します (cellfun() を含むこれらの操作はすべて、MATLAB でマルチスレッド化する必要があるという印象を受けました)。

(明示的に) 並列化された解決策または問題のより良いベクトル化を見た人はいますか?

私の例は両方とも非効率的であることに注意
してください.1つ目は三角形のセル配列を計算すると2倍速くなり、2つ目はまだ自己比較を計算しています。しかし、優れた並列化による時間の節約は、16 倍 (全員のマシンに MATLAB をインストールした場合は 72 倍) です。

余談
メモリの問題もあります。いくつかの eval を使用して、H の各列を H1、H2 などの名前でファイルに追加し、H _iをクリアしました。残念ながら、保存は非常に遅いです...