1

私は宿題の問題を抱えており、それをしばらくの間理解しようとしてきましたが、一生解決することはできません。

サイズ X*Y のシートと、それより小さいサイズのパターンのセットがあり、それらに価格値が関連付けられています。シートを水平または垂直にカットできます。シートから最大の利益を得るには、最適化されたカット パターンを見つける必要があります。

私が知る限り、(X*Y)(X+Y+#ofPatterns) 再帰操作が必要です。複雑さは指数関数的であると想定されています。誰かが理由を説明してもらえますか?

私が思いついた疑似コードは次のとおりです。

Optimize( w, h ) {
best_price = 0
    for(Pattern p :  all patterns) {
        if ( p fits into this piece of cloth && p’s price > best price) {best_price = p’s price}
    }
    for (i = 1…n){
       L= Optimize( i, h );
       R= Optimize( w-i, h);
       if (L_price + R_price > best_price) { update best_price}
    }
    for (i = 1…n){
        T= Optimize( w, i );
        B= Optimize( w, h-i);
        if (T_price + B_price > best_price) { update best_price}
    }
return best_price;
}
4

2 に答える 2

0

再帰的なケースは指数関数的です。最初に紙を 0 から最大幅インチまで、または 0 から最大高さインチまで切り取ってから、必要に応じて残りの部分を切り取ることができるからです (再帰)。

この問題は、2 つの次元が関係するため、このロッド切断問題のもう少し興味深いケースのように思えます。

http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html

良いガイドです。宿題に露骨に答えることなく、正しい軌道に乗るはずです。

再帰時に指数関数的である理由に関連する部分:

This recursive algorithm uses the formula above and is slow
Code
    -- price array p, length n
    Cut-Rod(p, n)
        if n = 0 then
            return 0
        end if
        q := MinInt
        for i in 1 .. n loop
            q = max(q, p(i) + Cut-Rod(p, n-i)
        end loop
        return q

Recursion tree (shows subproblems): 4/[3,2,1,0]//[2,1,0],[1,0],0//[1,0],0,0//0
Performance: Let T(n) = number of calls to Cut-Rod(x, n), for any x
T(0)=0
T(n)=1+∑i=1nT(n−i)=1+∑j=0n−1T(j)
Solution: T(n)=2n
于 2013-03-27T00:24:07.670 に答える
0

動的計画法アルゴリズムの複雑さを計算するとき、それを 2 つのサブ問題に分解できます。もう 1 つは、特定の下位問題を解決するための時間計算量を計算することです。

しかし、メモ化アプローチを使用しない場合、以前に計算した情報を再利用しないため、本質的に多項式の時間の複雑さを持つアルゴリズムが指数関数的な時間の複雑さに増加することは事実です。（動的プログラミングコースからこの部分を理解していると確信しています）

メモ化法またはボトムアップ アプローチのどちらを使用して動的計画法の問題を解決しても、時間の複雑さは変わりません。あなたが抱えている問題は、頭の中で関数呼び出しグラフを描こうとしていることにあると思います。代わりに、この方法で関数呼び出しの数を見積もってみましょう。

(X*Y)(X+Y+#ofPatterns) 再帰呼び出しがあると言っています。

はい、いいえ。

確かに、メモ化メソッドを使用すると、この数の再帰呼び出ししかありません。特定の Optimize(w0,h0) を呼び出して計算した場合、その値が保存され、次に別の関数 Optimize(w1,h1) が Optimize(w0,h0) を呼び出したときに、これらの冗長な作業が再び行われないためです。 . そして、それが時間の複雑さを多項式にするものです。

しかし、現在の実装では、1 つのサブ問題 Optimize(w0,h0) が多くの冗長な関数呼び出しを取得します。これは、アルゴリズムの再帰呼び出しの数がまったく多項式ではないことを意味します (単純な例として、再帰関数の呼び出しグラフを描画してみてください)フィボナッチ数アルゴリズム)。

于 2013-03-27T23:25:37.810 に答える