3

私はこの問題の理解に取り組んでいます:

X と Y の寸法 (X と Y は正の整数) の長方形の布と、その布を使用して作成できる n 個の製品のリストが与えられます。[1,n] の各製品 i について、寸法 ai x bi の布の長方形が必要であり、製品の最終販売価格が ci であることを知っています。ai、bi、および ci はすべて正の整数であると仮定します。長方形の布を縦または横に 2 つに切断できる機械があります。X x Y の布を裁断して得られる布から作られた製品の販売価格の合計が最大になるようにするための最適な戦略を見つけるアルゴリズムを設計します。特定の製品のコピーを好きなだけ自由に作成できます。必要に応じてコピーを作成することもできません。

私は実際に動的計画法ソリューションをすでに適切に実装していますが、問題に対する単純なソリューションが指数時間で実行される理由を理解/証明するのに苦労しています。これは、そもそも指数アルゴリズムの理解が不足していることを示していると思いますが、今のところ、上記の場合に最も関心があります。

動的プログラミング ソリューションを使用すると、既に行った作業をメモ化することで作業を節約できることを理解しています。動的計画法の実行時間は、O((W*H)(n+w+h)) または O(n^3)/多項式であると想定されています。これは、布片の幅と高さをそれぞれ可能な限り試しているためです。そして、布片の可能な幅と高さごとに、可能な縦、横、およびピースサイズのカットをそれぞれ試します. （時間の複雑さで n が必要な理由についても少し混乱していますが、考えられるすべての水平および垂直カットを試してみると、可能なすべてのピースも試す必要があるためです）。

メモ化をオフにすると、力ずくの方法が得られ、ツリー全体を解決する必要があります。これは、多項式または O(2^n) であると想定されています。なんで？O(2^n) 時間の複雑さを持つアルゴリズムは、二分木で表現できるはずではありませんか? この問題に対する素朴な解決策はバイナリではないようです。

4

3 に答える 3

1

線形最適化

  • 1 つの変数に関する問題を解くには、線形計画法\最適化を使用します。

  • 時間: O(n)

  • スペース: O(1)

動的計画法

  • k 個の変数に関する問題を解くには、動的計画法\最適化を使用して実行できます。

  • 時間: O(Π{ Si } * T(Δ Ij) * c) for i: 1..k、Si は i 番目の可変ドメイン サイズ、Ij は j 番目の入力サイズ、c は計算回数の「定数」モデルで

  • スペース: O(Π{ Si }) 基本的に必要なストレージは |S| です。次元行列

討論：

〜基本的にあなたが言及したのは2変数の場合です.2変数の問題を解く単純な動的計画法の最適なバージョンは、計算時間の複雑さがO((W*H)(n+w+h))または通常 O(3^n) 「n に一般化された入力サイズ」

~ 隠れマルコフ モデル (3D 行列として保存) に対して確率的 N グラム max-min 関数を使用するビタビ動的計画法アルゴリズムを使用して、言語類似性ライブラリを作成したことがあります。

~ 興味のある方は Java で書かれています:ダウンロード

ソース:

于 2013-03-24T19:40:45.290 に答える
0

この問題は、ナップザック問題 (つまり、与えられたスペースからできるだけ多くの価値を得る) から派生したもののように思えます。それを念頭に置いて、ここを見てください。単純な解決策を説明する (そしてそれを二分木で表現する) セクションがあり、重複するサブ問題を示します。

あなたの質問がナップザックの問題とどのように同じであるかを理解していない場合は、そこから始めるべきです。

于 2013-03-24T18:19:07.003 に答える
0

なぜ 2^n (バイナリ ツリー) なのかを理解するために、考えられるカットを yes/no の決定と考えてください: ここでカットしますか? またはここですか？またはここですか？yes/no の各バイナリ決定は、調査する必要がある可能性のサブツリーになります。

この問題が二分木として表現されていないのは、葉だけに関心があるためです。具体的には、最適なリーフで。根からその葉への道は、最適なカットのソリューションです。ツリー自体が可能なソリューション スペースです。

于 2014-12-04T03:11:49.307 に答える