3

一般的な動的計画法の問題の目的関数は、目的関数がすべての段階でのアクションと状態の項目の合計であるwiki の動的計画法のように常に定式化できるのでしょうか? それとも、それは単なる特殊なケースであり、一般的な定式化は何ですか?

編集：

「動的計画問題」とは、動的計画法で解ける問題のことです。このような問題は、最適問題と最適構造の性質を持っています。

しかし、少なくとも私にとっては、そのような問題を特定するのは簡単ではない場合があります。おそらく、そのような言葉による説明に慣れていないためです。ベルマン方程式の WIKI ページに出くわしたとき、コスト関数の数学的定式化が何らかの形で役立つと感じました。全体的なコスト/ゲイン関数は、すべての段階からのコスト/ゲインの累積として常に表すことができると思いますか? 蓄積は加算的または乗算的またはその他の可能性がありますか？

私が質問を投稿したとき、数学的最適化を重視した場所で動的計画法について議論する方が適切であることに気付きました。しかし、Stackoverflow.com では、コンピューター アルゴリズムに関する非常に多くの議論が行われています。ですから、ここで質問するのも不当だとは思いませんでした。

4

3 に答える 3

2

それは私が任意の最適化問題（または動的計画法アルゴリズム）を特徴づける方法ではありません。特に、係数βtは、プログラマーが通常は望んでいない電気工学のハックのように見えます。もっと微妙に、与えられた問題に対して関数Fが何であるかが常に明らかであるとは限らないようです。

しかし、はい、βを1に設定すると、任意の目的関数をそのように定式化できます。一般に、目的関数は、初期状態と実行されるすべてのアクションの任意の関数です。そのような関数が与えられれば、その式にプラグインする関数Fを定義するのは簡単です。

それが役に立つかどうかは問題次第だと思います。

于 2010-02-13T17:21:44.613 に答える
2

コンピューター サイエンスでは、動的計画法は、この再帰的展開で同じ部分問題が何度も現れる場合に、部分問題に再帰的に分割するという観点からアルゴリズムを構築することを意味します。簡単な本の例では、フィボナッチ数は動的計画法を使用して計算できます。

一般的な再帰 F(n) = F(n-1) + F(n-2) から、次のアルゴリズムを実装できます。

int fibonacci(n):
  if (n < 2): return 1
  else: return fibonacci(n-1) + fibonacci(n-2)

もちろん、これはまったく効率的ではありません。膨大な数の再帰呼び出しが作成されるためです。

F(8) = F(7) + F(6) = [F(6) + F(5)] + [F(5) + F(4)] = ...

したがって、ここではすでに fibonacci(5) が実装によって 2 回計算されていることがわかります。動的プログラミングのパラダイムは、次のように結果を「メモ化」または「キャッシュ」することです。

integer_map store;
int memofibo(n):
  if (n < 2) : return 1
  else if (store.find_key(n)): return store.find_value(n)
  else:
    int f = memofibo(n-1) + memofibo(n-2)
    store.set(n, f)
    return f

この実装により、n のすべての引数値に対して再帰ステップが最大 1 回実行されることが保証されるため、連想配列 'store '。

したがって、コンピューターサイエンスの観点から、あなたが提供したリンクは同じアイデアのオペレーションズリサーチ/最適化問題バージョン（問題をサブ問題に分割する）ですが、アイデアは実際には一般的なコンピューターのドメインでこの再帰+メモ化パターンに抽象化されています理科。これが雲の一部を取り除くのに役立つことを願っています.

于 2010-02-13T18:23:35.993 に答える
1

皆さん、

ここにはオペレーションズ リサーチの質問に集中した新しい (っぽい) Web サイトがありますが、トラフィック量が少ないため、適切な回答がすぐには得られない可能性があります。

ソープボックス時間:

スタック オーバーフローに適したものについて議論したい人のために、アルゴリズムはアルゴリズムであり、誰がその分野の一部であると主張しているのかに関係なく、注意してください。シンプレックス法、ジクストラ法、分枝限定法、ラグランジアン緩和法はすべて、特定のタイプの問題を解決するアルゴリズムまたは方法です。これらの多くは両方の分野で教えられ適用されるため、この分野では OR と CS の境界はかなりあいまいです。

たとえば (非常に強力な例です) MIT のアルゴリズムの学部課程には、次のすべてが含まれます - ランダム化競合アルゴリズム、動的プログラミング、貪欲アルゴリズム、最小スパニング ツリー、最短パス、ダイクストラのアルゴリズム、ベルマンフォード、線形計画法、深さ優先検索、トポロジカル ソート、全ペア最短パスなどのトピックがあります。この場合、MIT に任せます。

私がスタック オーバーフローを好むのは、多くのプログラマーが最適化の問題に遭遇したときにそれを認識しているためです。ただし、多くの場合、問題を定式化する方法や、問題の名前を何と呼ぶか​​を決定する際に、ちょっとした助けが必要なだけです。

于 2010-02-17T20:18:20.733 に答える