1

コーメンらによるアルゴリズム入門の動的計画法の章を読んでいます。私はサブ問題の空間を特徴づける方法を理解しようとしています。彼らは動的計画法の2つの例を示しました。これら2つの問題は両方ともサイズnの入力があります

  1. ロッドの切断問題（サイズnのロッドを最適に切断する）
  2. 行列の括弧の問題（行列の積A1。A2 .A 3 ... A nを最適に並列化して、スカラー乗法の数を最小にします ）

最初の問題では、長さkのカットを作成する形式のサブ問題を選択します。これは、カットの結果として生じる左側のサブ問題をこれ以上カットできず、右側のサブ問題をさらにカットできるため 、単一のサブ問題が発生することを前提としています。サイズ（nk）の。

ただし、タイプA i ... Ajのサブ問題を選択する2番目の問題の場合、1 <= i <= j <=nです。なぜ彼らはこの問題のために両端を開いたままにすることを選んだのですか？片方の端を閉じて、サイズ（nk）のサブ問題について考えてみませんか？単一のk分割ではなく、なぜここでiとjの両方が必要なのですか？

4

2 に答える 2

3

それは芸術です。動的計画法の問題には多くの種類があり、サブ問題を解決したい空間の次元を決定する1つの方法を定義するのは簡単ではありません。

これは、サブ問題がどのように相互作用するか、および空間の各次元のサイズに大きく依存します。

動的計画法は、より大きな問題をより効率的に解決するためのサブ問題のキャッシュまたはメモ化を説明する一般的な用語です。しかし、動的計画法によって解決できる問題は非常に多く、解決する必要のある特定の動的計画問題がない限り、すべてを説明することはできません。

私が提案できるのは、問題を解決するときに試すことだけです。

  • 1つの問題を解決する方法を知っている場合は、同様の問題に対して同様の手法を使用できます。
  • さまざまなアプローチを試して、各ディメンションの入力サイズの観点から複雑さの順序（時間とメモリ）を見積もり、各ディメンションのサイズを指定して、十分に高速に実行され、メモリ制限内であるかどうかを確認します。

動的計画法として説明できるいくつかのアルゴリズムには、次のものがあります。

于 2012-09-05T10:01:18.797 に答える
2

動的計画法に関するVaziraniのテクニカルノート http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf には、入力を指定してサブ問題を作成するための便利な方法がいくつかあります。以下のリストに他の方法をいくつか追加しました。

  1. x_1、x_2、..x_nを入力します。サブ問題はx_1...x_iです。

  2. x_1、x_2....x_nを入力します。サブ問題はx_i、...x_jです。

  3. x_1、x_2 ... x_nおよびy_1、y_2..y_mを入力します。サブ問題はx_1、x_2、.. x_iおよびy_1、y_2、..y_jです。

  4. 入力はルートツリーです。サブ問題はルート化されたサブツリーです。

  5. 入力は行列です。サブ問題は、元のマトリックスとコーナーを共有するさまざまな長さのサブマトリックスです。

  6. 入力は行列です。サブ問題は、考えられるすべてのサブマトリックスです。

通常使用するサブ問題は、問題によって異なります。これらの既知のバリエーションを試して、どれがニーズに最も適しているかを確認してください。

于 2013-04-24T07:45:03.243 に答える