最小のスタック数で効率的に箱を積み重ねますか？

Question

私はこの問題をオンラインでのコーディングの課題に抱いています。

長さと幅（l、h）のボックスのリストが与えられている場合、長さと幅が次の値より小さい場合は、他の箱。

私は多項式時間解法を思いつく方法を理解できません。私はすべての可能なスタック配置を再帰的に作成するブルートフォース・ソリューションを構築しました（Nスタックで始まり、各スタックについてはスタックの上に置いてから、新しいスタック配置ではすべてのスタックの可能性を再帰的に生成します）必要なスタックの最小数を返します。

私はいくつかの最適化とそれをスピードアップしました：あなたはボックスBとボックスCの上にボックスAをスタックすることができ、あなたはボックスCの上にボックスBを積み重ねることができた場合は、次にやる、

• ：ここでは、このソリューションのためのPythonコードだ、箱Cに
• Memoizeスタックの手配をボックスAを積み重ねるだけスタック

の底部と頂部のレベルを考慮し検討していません210

入力

17 
9 15 
64 20 
26 46 
30 51 
74 76 
53 20 
66 92 
90 71 
31 93 
75 59 
24 39 
99 40 
13 56 
95 50 
3 82 
43 68 
2 50 

出力：

33.7288980484 
6 

アルゴリズムは、数秒（1-3）で16箱の問題、〜30秒で17箱の問題を解決します。私はこれが指数関数的な時間だと確信しています。 （スタック配列の指数関数的な数があるので）。

私は確かに多項式時間解があると確信していますが、それは何か分かりません。問題の1つは、メモの作成は現在のスタック配置に依存するということです。これは、より多くの計算を行う必要があることを意味します。

Answer 1

AをBの上に積み重ねることができる場合、各ボックスに頂点があり、ボックスAからボックスBのエッジがあるグラフを作成しましょう。このグラフは非循環です（「can stack on on」は推移的な関係と箱の上に積み重ねることはできません）。

ここで、このグラフの最小パスカバーを見つける必要があります。それは、標準的な問題だとこのように解決しています：

1. はのは、（元のグラフの各頂点が左と右の部分に二つの「コピー」を取得します）二部グラフを構築してみましょう。元のグラフの各A->Bエッジの場合、Aの左コピーとBの右コピーの間にエッジがあります。

2. 答えは、ボックスの数から2つのグラフの最大一致のサイズを引いたものです。

O(n)頂点とO(n^2)エッジとして二部グラフ。たとえば、Kuhnのアルゴリズムを使用して一致を見つけると、合計時間の複雑さはO(n^3)であり、nはボックスの数です。

Answer 2

これは最初は単純に見えましたが、可能性を考えれば、すぐに厳しいものになりました。しかし、私は非常に自信を持って感じるJSで私のアルゴリズムを実装することができました。さらに、JSは、この特定のケースで私を非常に助けた参照型のオブジェクトなどの専門知識を持っています。

まず、ボックスをx軸の長辺に合わせることができるという前提から始めます。次に、指定された17個のボックスは、クロムで4〜10ミリ秒の間に行われ、FFでは15〜25ミリ秒のように、合計で5個のボックスにはすべて17個が含まれます。

さらに、50 boxes caseランダムな寸法は1〜100）。したがって、50個のボックスケースは、どのようにフィットできるかによって、ChromeとFFの両方で250〜15000 msecの間に解決されます。私は70が本当に退屈になる前にこの仕事の限界だと思います。

コードは速度の点でさらに向上することができますが、今のところこれがそうです。私は一日か二日にコードの詳細な記述をしてみようと思います。

function insertBoxes(data){ 
 
    if (data.length <= 1) return data[0] ? [data] : data; 
 

 
    function flatMap(o){ 
 
    return o.inside.length ? o.inside.reduce((p,b) => p.concat(flatMap(b).map(f => f.concat(o.id))),[]) 
 
          : [[o.id]]; 
 
    } 
 

 
    function getBest(arr, r = []){ 
 
    var i = arr.findIndex(a => a.every(i => !used[i])),len,tgt,bests,best; 
 
    if (i === -1) return r; 
 
     len = arr[i].length; 
 
     tgt = arr.slice(i); 
 
    bests = tgt.filter(a => a.length === len && a.every(x => !used[x])); 
 
    best = bests.map((a,i) => [a.reduceRight((p,c) => p + boxes[c].x + boxes[c].y, 0), i]) 
 
       .reduce((p,c) => c[0] < p[0] ? c : p,[Infinity,-1]); 
 
    bests[best[1]].forEach(i => used[i] = true); 
 
    r.push(bests[best[1]]); 
 
    return getBest(tgt,r); 
 
    } 
 

 
    var boxes = data.map((e,i) => ({id:i, x:Math.max(e[0],e[1]), y:Math.min(e[0],e[1]), inside:[]})), 
 
     used = Array(data.length).fill(false), 
 
    interim = boxes.map((b,_,a) => { a.forEach(box => (b.x > box.x && b.y > box.y) && b.inside.push(box)); 
 
            return b; 
 
            }) 
 
        .map(b => flatMap(b)) 
 
        .reduce((p,c) => p.concat(c)) 
 
        .sort((a,b) => b.length-a.length); 
 
    return getBest(interim).map(b => b.map(i => data[i])) 
 
         .concat(insertBoxes(data.reduce((p,c,i) => used[i] ? p : (p.push(c),p) ,[]))); 
 
} 
 

 
var input = [[9, 15], [64, 20], [26, 46], [30, 51], [74, 76], [53, 20], [66, 92], [90, 71], [31, 93], [75, 59], [24, 39], [99, 40], [13, 56], [95, 50], [3, 82], [43, 68], [2, 50]]; 
 
    result = [], 
 
     ps = 0, 
 
     pe = 0, 
 
ps = performance.now(); 
 
result = insertBoxes(input); 
 
pe = performance.now(); 
 
console.log("boxing", input.length, "boxes done in:", pe-ps,"msecs and all boxes fit in just", result.length,"boxes"); 
 
console.log(JSON.stringify(result));

注：上記のコードはまだ下のアプローチへの再帰トップを使用しています私は、動的計画法のアプローチを下から上にはこの問題の真の解決策になることを考え始めています。

私はダイナミックプログラミングアプローチの結果がずっと速い解決策だと思っています。私は上記を削除していないが、それを無視してください。

次のコードは、1ms未満で17個のボックスの配列を解決し、1000msのボックスを100ms未満で解決します。

function boxBoxes(d){ 
 
    return d.sort((a,b) => b[0]*b[1] - a[0]*a[1]) 
 
      .map(b => b[0] < b[1] ? b : [b[1],b[0]]) 
 
      .map(function(b,i,a){ 
 
       b.c = i ? a.slice(0,i) 
 
          .filter(f => f[0] > b[0] && f[1] > b[1]).length || Infinity 
 
         : Infinity; 
 
       return [b]; 
 
       }) 
 
      .sort((a,b) => b[0].c - a[0].c) 
 
      .reduceRight(function(p,c,i,a){ 
 
         var r = a.filter(f => f[f.length-1][0] > c[0][0] && 
 
               f[f.length-1][1] > c[0][1]); 
 
         r.length && r[0].push(...a.splice(i,1)[0]); 
 
         return a; 
 
         },void 0); 
 
} 
 

 
var data = [[9, 15], [64, 20], [26, 46], [30, 51], [74, 76], [53, 20], [66, 92], [90, 71], [31, 93], [75, 59], [24, 39], [99, 40], [13, 56], [95, 50], [3, 82], [43, 68], [2, 50]]; 
 
    result = boxBoxes(data); 
 
console.log(result.length,"boxes:",JSON.stringify(result));

Answer 3

私も最近、この問題に出くわしました。次のO（NlogN）ソリューションを提案します。

1）現在使用中のすべてのボックススタックの最上部のボックスのリストAllStkTopsを維持します。空のリストに初期化されます。

2）ボックスを長さの小さい順に並べ替えます。 （長さが等しい場合は、で増加する（はい、減少しない）の順に並べ替えます）。

3）ボックスをピックアップして（最も長いものから）、現在のスタックの1つに配置します。最初のボックスにはスタックがないので、最初のボックススタックの基礎になります。 2番目のボックスは、最初のボックスの先頭に移動するか、2番目のスタックのベースになります。このプロセスを続けると、手元にあるボックスの長さは、すべてのスタックの一番上のボックスよりも小さくなるか、または等しくなることがわかります。したがって、我々は幅を心配する必要があります。最初のスタックから現在のすべてのスタックの上端を確認し、スタックの最上部に配置します。これは、現在のボックスの長さと幅が厳密に大きく、ii）最適性のために）。このボックスに対応できないスタックがない場合は、このボックスをベースにして新しいスタックを作成します。

すべてのスタックトップの幅は、その時点ですべてのスタックトップよりもボックスの幅が大きくなった場合に新しいスタックを作成するだけなので、増加する順序になります。 （同じ長さのボックスの場合は、並べ替えの間に幅の広い順に並べていました）。したがって、バイナリサーチプロシージャを使用して、十分に大きな幅を有する最も狭いスタックトップを見つけることができる。しかし、その長さが指定されたボックスの長さよりも厳密に（そしてそれと同等ではない）確実になるようにする必要があります。しかし、私は、トップの長さは決して問題ではないと主張します。
i）ボックスは長さの小さい順に選択されるので、上の長さは厳密にはそれほど少なくないことがあります。 ii）等しい長さのボックスを並べ替えたので、前のボックスを持っているスタックはこのスタックトップの左側にある必要があります。

したがって、バイナリ検索手順を使用して、現在のボックスの最適なスタックトップを見つけることができます。

すべてのボックスをスタックに配置するまで、上記の手順を繰り返すことができます。最後に、スタックの数をAllStkTopsに数えます。

ソートにはO（NlogN）時間がかかっており、すべてのボックスのバイナリ検索にはO（logN）時間がかかりますので、これはO（NlogN）の複雑さです。

誰かが私のアルゴリズムで見つけた疑問や欠点を抱きたいです。

乾杯！