長方形のオブジェクトが多数あり、それらを可能な限り小さなスペースに詰め込む必要があります (このスペースの寸法は 2 の累乗である必要があります)。
アイテムを指定されたスペースに可能な限り詰め込むさまざまなパッキング アルゴリズムがあることは知っていますが、この場合、そのスペースがどのくらいの大きさであるべきかを計算するアルゴリズムも必要です。
例えば、次のような長方形があるとします
- 128*32
- 128*64
- 64*32
- 64*32
128×128のスペースに収納可能
_________________ |128*32 | |________________| |128*64 | | | | | |________________| |64*32 |64*32 | |_______|________|
しかし、160*32と64*64もあったら、256*128のスペースが必要になる。
________________________________ |128*32 |64*64 |64*32 | |________________| |_______| |128*64 | |64*32 | | |_______|_______| | | | |___|___| |160*32 | | |____________________|___________|
多数の長方形をパックし、コンテナーに必要なサイズ (2 の累乗で、各次元の指定された最大サイズ内) を決定できるアルゴリズムにはどのようなものがありますか?
ベストアンサー1
見るARCプロジェクトのこのページソリューションの調査では、実装の複雑さ/時間と最適性の間にトレードオフがありますが、選択できるアルゴリズムの範囲は広くなります。
アルゴリズムの抜粋は次のとおりです。
ファーストフィット減少高さ (FFDH) アルゴリズム
FFDH は、次のアイテム R (非増加高さ) を、R が収まる最初のレベルにパックします。R を収容できるレベルがない場合は、新しいレベルが作成されます。FFDH
の時間計算量: O(n·log n)。
近似比: FFDH(I)<=(17/10)·OPT(I)+1; 17/10 の漸近境界は厳密です。Next-Fit Decreasing Height (NFDH) アルゴリズム
NFDH は、R が適合する場合、次のアイテム R (非増加高さ) を現在のレベルにパックします。そうでない場合、現在のレベルは「閉じられ」、新しいレベルが作成されます。
時間の計算量: O(n·log n)。
近似比: NFDH(I) <= 2·OPT(I)+1。2 の漸近境界は厳密です。最適減少高さ (BFDH) アルゴリズム
BFDH は、R を収容できるレベルのうち、残りの水平スペースが最小となるレベルに、次のアイテム R (高さが増加しない) をパックします。R を収容できるレベルがない場合は、新しいレベルが作成されます。ボトム レフト (BL) アルゴリズム
BL は、まずアイテムを非増加幅で順序付けます。BL は、次のアイテムをできるだけ下部に詰め込み、次に詰め込まれたアイテムと重ならないようにできるだけ左側に詰め込みます。BL はレベル指向の詰め込みアルゴリズムではないことに注意してください。
時間の計算量: O(n^2)。
近似比: BL(I) <= 3·OPT(I)。ベイカーのアップダウン (UD) アルゴリズム
UD は、BL と NFDH の一般化の組み合わせを使用します。ストリップの幅とアイテムは、ストリップが単位幅になるように正規化されます。 UD は、アイテムを非増加幅で順序付けし、アイテムを 5 つのグループに分割します。各グループの幅は、(1/2, 1]、(1/3, 1/2]、(1/4, 1/3]、(1/5, 1/4]、(0, 1/5] の範囲です。ストリップは、5 つの領域 R1、··· 、R5 にも分割されます。基本的に、(1/i+1、1/i]、1 <= i <= 4 の範囲にある一部の幅のアイテムは、BL によって領域 Ri にパックされます。BL はストリップの右側に上から下に向かって幅が増加するスペースを残すため、UD はこの利点を活かして、最初にアイテムを上から下に向かって j = 1、··· 、4 (順) に Rj にパックします。そのようなスペースがない場合、アイテムは BL によって Ri にパックされます。最後に、最大で 1/5 のサイズのアイテムは、(一般化された) NFDH アルゴリズム。これらの領域にスペースがない場合も、アイテムは NFDH を使用して R5 にパックされます。
近似比: UD(I) <= (5/4) · OPT(I)+(53/8)H、ここで H はアイテムの最大の高さです。5/4 の漸近境界は厳密です。リバース フィット (RF) アルゴリズム
RF は、ストリップの幅とアイテムも正規化して、ストリップが単位幅になるようにします。RF は最初に、幅が 1/2 より大きいすべてのアイテムをスタックします。残りのアイテムは、高さが増加しない順にソートされ、1/2 より大きいアイテムが到達する高さ H0 より上にパックされます。次に、RF は次のプロセスを繰り返します。大まかに言うと、RF は、スペースがなくなるまで、アイテムを高さ H0 の線に沿って左から右にパックします。次に、アイテムを右から左、上から下に (逆レベルと呼ばれる) パックし、合計幅が少なくとも 1/2 になるまでパックします。次に、逆レベルは、(少なくとも) 1 つのアイテムが下のアイテムに接触するまでドロップダウンされます。ドロップダウンは何らかの方法で繰り返されます。
近似比: RF(I) <= 2·OPT(I)。Steinberg のアルゴリズム
Steinberg のアルゴリズム (論文では M と表記) は、すべてのアイテムを詰め込むために必要な高さ H の上限を推定し、入力アイテムを幅 W、高さ H の長方形に詰め込むことができることを証明します。次に、7 つの手順 (7 つの条件付き) を定義し、それぞれが問題を 2 つの小さな問題に分割して再帰的に解決します。扱いやすい問題はすべて、7 つの条件のいずれかを満たすことが示されています。
近似比: M(I) <= 2·OPT(I)。Split-Fit アルゴリズム (SF) SF は、アイテムを 2 つのグループ (幅が 1/2 より大きい L1 と最大 1/2 の L2) に分割します。L1 のすべてのアイテムは、最初に FFDH によってパックされます。次に、幅が 2/3 より大きいすべてのアイテムが、幅が最大 2/3 のアイテムの下になるように配置されます。これにより、幅 1/3 の長方形 R の空間が作成されます。次に、L2 の残りのアイテムは、FFDH を使用して R と、その上の空間に L1 でパックされたアイテムにパックされます。R で作成されたレベルは、L1 のパックの上に作成されたレベルより下にあると見なされます。
近似比: SF(I) <= (3/2) ·OPT(I) + 2。3/2 の漸近境界は厳密です。Sleater のアルゴリズム
Sleater のアルゴリズムは 4 つのステップで構成されます。幅が 1/2 より大きいすべてのアイテムは、ストリップの底部に重ねて詰められます。h0 が結果の詰め込みの高さであると仮定すると、後続のすべての詰め込みは h0 より上で行われます。
残りのアイテムは、高さが増加せずに並べられます。アイテムのレベルは、高さ h0 の線に沿って左から右に (高さが増加せずに) 詰められます。
次に、中央に垂直線を引いて、ストリップを 2 つの均等な半分に切ります (この線は、右半分に部分的に梱包されているアイテムを切断する可能性があることに注意してください)。長さが半分の 2 つの水平線セグメントを、1 つは左半分 (左ベースラインと呼ばれる) を横切り、もう 1 つは右半分 (右ベースラインと呼ばれる) を横切るように、2 つの線がどのアイテムとも交差しないように、できるだけ低く引きます。
高さが低い左または右のベースラインを選択し、次のアイテムの幅が広くなりすぎるまで、ストリップの対応する半分にアイテムのレベルを詰め込みます。
新しいベースラインが形成され、すべてのアイテムがパックされるまで、ステップ（4）が下位のベースラインで繰り返されます。
時間計算量：O（n·log n）。Sleator
アルゴリズムの近似比は2.5で、厳密です。