動的プログラミングについて知りたいが、尋ねるのが怖かったすべてのこと

ハブに動的プログラミング（以降、単にダイナミクスと呼びます）に関する記事がほとんどないことに非常に驚いた このパラダイムは、プログラミングオリンピックの枠を超えたものも含めて、非常に広まっているように思えました。 したがって、この記事でこのギャップを埋めようとします。

#        Python 

基本

おそらく、私が今まで聞いた中で、ダイナミクスの最高の説明を1つの文で書いたものです。

動的プログラミングとは、解決方法が明確ではないタスクがあり、それをより小さなタスクに分割することであり、これも解決方法が明確ではありません。 （c）A.クモック。

ダイナミクスによって問題を解決するには、次のものが必要です。
1）ダイナミクスの状態：サブタスクを一意に指定するパラメーター。
2）初期状態の値。
3）状態間の遷移：再計算式。
4）再集計の手順。
5）問題に対する答えの位置：これは時々合計、または、例えば、いくつかの状態の値の最大値です。

再計算手順

3つの変換オーダーがあります。
1）直接注文：
状態は、すでに計算された状態に基づいて順次再計算されます。



2）逆順：
現在の状態に応じて、すべてのステータスが更新されます。



3）レイジーダイナミクス：
ダイナミクスの再帰的メモ再計算機能。 これは、エッジがそれらの間の依存関係である非循環状態グラフでのディープサーチのようなものです。



基本例： フィボナッチ数 ステータス-番号。

直接注文：

 fib[1] = 1 #   fib[2] = 1 #   for i in range(3, n + 1): fib[i] = fib[i - 1] + fib[i - 2] #   i 

逆順：

 fib[1] = 1 #   for i in range(1, n): fib[i + 1] += fib[i] #   i + 1 fib[i + 2] += fib[i] #   i + 2 

レイジーダイナミクス：

 def get_fib(i): if (i <= 2): #   return 1 if (fib[i] != -1): #  return fib[i] fib[i] = get_fib(i - 1) + get_fib(i - 2) #  return fib[i] 

3つのオプションすべてに生命権があります。 それらはそれぞれ独自のスコープを持っていますが、多くの場合他のスコープと重複しています。

多次元ダイナミクス

1次元のダイナミクスの例は、上記の「変換の順序」で示されているため、すぐに多次元から始めます。 ご想像のとおり、1次元とは異なり、測定の数、つまり状態のパラメーターの数です。 これに基づく分類は通常、「1対2」スキームに基づいており、実際には特に基本的ではありません。

多次元ダイナミクスは1次元とそれほど変わりません。いくつかの例を見るとわかります。

例1：SMSの数

以前は、電話機にボタンがあった場合、キーボードは次のようになりました。



このようなキーボードのタップをk回以下使用して、複数のテキストメッセージをいくつ書くかを計算する必要があります。

例2：馬

チェスの馬は、サイズN x Mボード上のケージ(1, 1)に立っていますM セル(N, M)に到達する方法の数を4つのタイプのステップでカウントする必要があります。

ダイナミクスと遷移マトリックス

行列を乗算したことがないが、この見出しを理解したい場合は、少なくともwikiを読む必要があります 。

例えば、永遠のフィボナッチ数など、動的計画法によってすでに解決した問題があると仮定します。
少し作り直しましょう。 ベクトルがありますか ベクトルの取得元 。 数式を少し開いてみましょう。 。 あなたはベクトルからそれを見ることができます ベクトルを取得できます 最初のベクトルの折り畳まれた変数のみが最終ベクトルに表示されるため、何らかの種類の行列を乗算します。 このマトリックスは簡単に導き出せます。ここにあります： 。 これを遷移行列と呼びます。

これは、ベクトルを取る場合 遷移行列をn - 1回乗算すると、ベクトルが得られます 、 fib[n] -問題への答え。

そして今、なぜこれがすべて必要なのか。 行列の乗算には結合性の特性があります。 （しかし、これには可換性がありません。これは私の意見では驚くべきことです）。 このプロパティは、これを行う権利を与えます。 。

これは、高速累乗法を適用できるためです。 。 合計で、算術演算の対数のNフィボナッチ数を計算することができました。

そして今、例はより深刻です：

例3：ノコギリシーケンス

長さNのこぎり波シーケンスを、極端でない各要素に対して条件が満たされるシーケンスとして示します。それは、その2つの近傍よりも小さいか、それ以上です。 長さNの数字の鋸歯状シーケンスの数を計算する必要がありますN 次のようになります。

サブセグメントダイナミクス

これは、状態が配列のサブセグメントの境界であるダイナミクスクラスです。 一番下の行は、配列のすべての可能なサブセグメントに基づいてサブタスクの回答を計算することです。 通常、それらは長さの増加順にソートされ、計算はそれぞれ短いセグメントに基づいています。

例4：文字列のパック

これが展開された状態です。 簡単にもう一度言います。

圧縮された行を定義します。
1）文字のみで構成される文字列は、圧縮された文字列です。 彼女は自分自身を開きます。
2）2つの圧縮された文字列AとB連結した文字列 展開された行AとBを連結するために展開されますB
3）文字列D(X) 、ここでDは1より大きい整数、 Xは圧縮された文字列です。 Xから圧縮解除されたD文字列の連結に圧縮解除されますX
例： “3(2(A)2(B))C” “AABBAABBAABBC”展開されます。

行s展開される最短の圧縮行の長さs見つける必要があります。

例5： オークス

サブツリーダイナミクス

サブツリーに沿ったダイナミクスの状態のパラメーターは、通常、この頂点がルートであるサブツリーを示す頂点です。 現在の状態の値を取得するには、通常、すべての子供の結果を知る必要があります。 ほとんどの場合、彼らはそれを遅延的に実装します-彼らは単に木の根から深さで検索を書きます。

例6：論理ツリー

中断されたツリーが与えられた場合、そのリーフにはシングルビット番号0または1が含まれます。 数値はすべての内部頂点にも書き込まれますが、次のルールに従って、各頂点に対して論理演算の1つが選択されます：「AND」または「OR」。 「AND」の場合、ピークの値はそのすべての子の値の論理「AND」です。 「OR」の場合、頂点の値はそのすべての子の値の論理「OR」です。



ルートの値が変更されるか、不可能であることを通知するように、内部頂点での論理演算の最小変更数を見つける必要があります。

サブセットダイナミクス

サブセット上のダイナミクスでは、特定のセットのマスクが通常状態になります。 それらは、このマスクのユニット数が増加する順序で最も頻繁に選択され、包含の小さい状態からそれぞれ再カウントされます。 回避策を特に考えないように、通常は怠dynamicなダイナミクスが使用されますが、これは完全に些細なことではありません。

例7：最小重量のハミルトニアンサイクル、または巡回セールスマン問題

サイズN重み付き（エッジの重みが負でない）グラフG与えられた場合 最小重みのハミルトニアンサイクル （自己交差なしですべての頂点を通過するサイクル）を見つけます。

プロファイルダイナミクス

プロファイルに沿ったダイナミクスによって解決される古典的な問題は、いくつかの数字でフィールドを並べるタスクです。 さらに、たとえば、タイリングの方法の数、または最小数の数字でタイリングするなど、さまざまなことが求められる場合があります。

これらのタスクは、 ここでaは1つのセルのタイリングのバリアントの数です。 プロファイルに沿ったダイナミクスは、いずれかの次元の時間を線形に最適化し、係数のみを指数関数的に残します。 次のようなものが得られます。 。

プロファイルはk列（多くの場合1列）で、既にタイル化されている部分とまだタイル化されていない部分との境界です。 この境界は部分的にしか塗りつぶされていません。 非常に多くの場合、ダイナミクスの状態の一部です。



ほとんどの場合、状態はプロファイルであり、このプロファイルの場所です。 そして、移行により、この場所が1つ増えます。 プロファイルサイズに比例した時間で、あるプロファイルから別のプロファイルに切り替えることができるかどうかを確認できます。 これは再カウント中に毎回確認できますが、カウントすることもできます。 2次元配列can[mask][next_mask]をカウントします。複数の図形を配置して、プロファイルの位置を1つずつ増やすことで、あるマスクから別のマスクに移動できます。 カウントすると、実行時間が短くなり、メモリが増えます。

例8：ドミノの支配

1 x 2および2 x 1寸法のドミノを使用して、テーブルN x Mをブリッジする方法の数を見つけます。

壊れたプロファイルダイナミクス

これは、プロファイルのダイナミクスの非常に強力な最適化です。 ここでは、プロファイルはマスクだけでなく、骨折部位でもあります。 次のようになります。



これで、プロファイルにキンクを追加した後、キンクの左のセルをカバーする1つの図のみを追加して、次の状態に進むことができます。 つまり、状態数をN倍に増やすことで（ブレークがどこにあるかを覚えておく必要があります）、1つの状態から別の状態への遷移の数を減らします。 前に 。 漸近性の改善 前に 。

ドミノのタイル張りの問題の例（例8）による、破損したプロファイルに沿ったダイナミクスの遷移：

回答の回復

ベストアンサーの特性を知るだけでは不十分な場合があります。 たとえば、「文字列のパッキング」タスク（例4）では、圧縮された最短の文字列の長さだけで終わりますが、ほとんどの場合、その長さではなく、文字列自体が必要です。 この場合、答えを復元する必要があります。

各タスクには答えを復元する独自の方法がありますが、最も一般的な方法は次のとおりです。

• ダイナミクス状態の値の横に、サブタスクへの完全な応答を保持します。 答えが大きい場合、必要なメモリが多すぎる可能性があります。そのため、別の方法を使用できる場合、通常はそうします。
• 与えられた条件の祖先を知って、答えを復元します。 多くの場合、受け取った方法だけを知って、答えを復元できます。 同じ「ラインパッキング」で、答えを復元するために、最後のアクションのフォームとそれが受信された状態のみを保存できます。
• 追加のメモリをまったく使用しない方法があります-ダイナミクスを再計算した後、最後から最適なパスに進み、道に沿って答えを書きます。

マイナーな最適化

記憶

多くの場合、ダイナミクスでは、状態がカウントされる他の状態を非常に多く必要としないという問題に対処できます。 たとえば、フィボナッチ数を計算するとき、最後の2つだけを使用し、前の数に戻ることはありません。 したがって、それらについては忘れることができます。つまり、メモリに保存しないでください。 これにより、漸近的メモリ推定が改善される場合があります。 この手法は、例1、2、3（遷移マトリックスなしのソリューション）、7、8で使用できます。 確かに、バイパスの順序が遅延ダイナミクスの場合、これはまったく機能しません。

時間

ある種のデータ構造を使用して漸近時間を改善できる場合があります。 たとえば、 ダイクストラのアルゴリズムでは、 優先度キューを使用して漸近時間を変更できます。

状態の置換

決定において、ダイナミクスには常に状態が含まれます。これは、サブタスクを一意に指定するパラメーターですが、必ずしもこの状態が唯一の状態ではありません。場合によっては、他のパラメータを思いついて、漸近的な時間または記憶の減少という形でこの恩恵を受けることができます。

例9：数値の分解

数Nをさまざまな用語に分解する数を見つける必要があります。たとえば、の場合N = 7、そのような展開5：

• 7
• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

おわりに

主な情報源は校長で、情報はサマーコンピュータースクール（児童向け）での講義、アンドレイスタンケビッチのサークル、ミハイルドヴォルキン（darnley）の特別コースから得られました。

ご清聴ありがとうございました。この記事が誰かに役立つことを願っています！私は便利になりましたが、記事を書くことはすべてを覚える良い方法であることがわかりました。