2次元パッケージングについて：オンラインアルゴリズム

これは、オフラインパッケージングアルゴリズムに関する投稿の続きです。



問題の本質：ゲームオーバーなしのテトリスのように、半無限のストリップと、有限の長方形のセットがあります。 四角形のデータはリアルタイムで取得されます。 新しい長方形はそれぞれすぐに配置し、移動しないようにする必要があります。 目標は、パックされた長方形の全体の高さを最小化することです。

これは、長方形を半拘束ストリップにパックするタスクのオンラインバリエーションです（2次元ストリップパッキング、2DSP）。



前の記事でもう少し理論的な情報を見つけることができますが、今のところ、これ以上の苦労をせずに、アルゴリズムに移りましょう。



このブリックのシーケンスを説明するために使用されます：



（ソースデータスポンサー-random.org）。

いくつかの発見的アルゴリズムについて説明します。一般的な考え方は、ストリップを領域に事前に分割し、特定の基準に従って特定の領域に新しく到着した長方形を配置することです。

レベルアルゴリズム

すべてのレベルアルゴリズムのアプローチは、この段階で使用可能な長方形の高さに基づいて、ストリップをレベルに分割することです。 長方形は、可能な限り左から右に現在のレベルのベースに沿って配置されます。 収まらない長方形は次のレベルにパックされます。 各レベルの高さは、その最上位の長方形によって決まります。 3つのパッケージオプションがあります。

次の適合レベル-次のレベルが開くと、前のレベルは「閉じ」、もはや考慮されません。

最初の適合レベル-アルゴリズムの各ステップで、最低レベルから開始して各レベルが表示され、十分なスペースがある最初の適切なレベルで長方形がパックされます。

最適なレベル-アルゴリズムの各ステップで、 すべてのレベルがスキャンされ、最適なレベルが選択されます-パッケージング後に最小限のスペースになるレベル。

上記の3つのアルゴリズムはすべて説明されています。 この段階では、どちらがどこにあるか簡単に推測できます。

バイレベルネクストフィット

Next Fit Levelのトリッキーな修正。 2つのレベルが作成され、それぞれに独自の戦略があります。

下位レベル（またはすべての奇妙なもの）：最初の入力長方形は左端に詰められ、残りは右から左に、十分なスペースがあります。 次に、レベルが閉じられ、その高さはその中の最も高い長方形によって決まります。

上位レベル（またはすべての偶数）：下位レベルに長方形が1つしかない場合、レベルは下位レベルと同様にパックされます。 2つ以上の場合、最初の長方形は、ストリップの端に押し付けられた2つのうちの下部に詰められ、ストリップの端に押し付けられます。 後続のものは、最初のものがどこにパックされたか（左または右）に関係なく、右から左にパックされます。



混乱したように聞こえますが、なぜタンバリンと踊るのかはすぐにはわかりません。 このアルゴリズムが明らかに提供する唯一のことは、左端にゆがむことなく、ストリップのボリューム上でより均一な長方形の分布です。 ただし、圧縮アルゴリズムを検討する場合は、この戦略に戻ります。

シェルフアルゴリズム

シェルフアルゴリズムは長方形の正確な高さに関連付けられておらず、レベル（シェルフ）の最初のアルゴリズムをパックした後、次のアルゴリズムが少し高い場合にスペースがほとんどありません。 この「少し」は、パラメーターr∈（0; 1）によって調整されます。 棚の高さはr ^kとして定義されます。ここで、整数kと最初のパックされた長方形の高さh（L _i ） ^に対して r ^{k + 1} <h（L _i ）≤r ^kです。 ティアアルゴリズムと同様に、Next Fit、First Fit、およびBest Fitシェルフバイパス戦略が適用されます。 各シェルフに残された「予約」は、最後の2つのケースで有益になります（FFLとFFS、BFLとBFSを比較してください）。 この例では、 p = 0.7です。

高調波シェルフ

ハーモニックシェルフは、同じレベルの高さだけでなく、同じ幅の1つのレベルの長方形にパックします。 結果はより多くのレベルになりますが、それらはより高密度になります。 許容幅を計算するために、追加のパラメーターMが導入されています。



ストリップの合計幅。簡単にするために、 M間隔I ₁ .. I Mで割った単位として取ります_。 著者は、 Mの合理的な値は[3; 12]。 間隔の幅は次の式で計算されます。



;



各長方形について、 pが計算されます。 高さパラメータkは、オフショアアルゴリズムと同様に計算されます。 2つの条件がチェックされます。高さr ^kの任意の棚に長方形の場所があり、そのpがすでにそこに詰められているかどうか。 少なくとも1つが満たされていない場合、ブラックジャックと最も快適な条件で、シェルフが作成されます。 この例では、 p = 0.7、 M = 4です。

アザール

レベルに分割するには、特定のしきい値0 < Y <1/2を導入します。 長方形の幅は、ストリップの幅に応じてスケーリングされます。ストリップの幅は、1単位と見なされます。 高さ2 ^{j -1} <h（L _i ）≤2 ^jおよび幅2 ^{- x -1} <h（L _i ）≤2 ^-xの長方形は1レベルにパックされます。 つまり、レベルは、ある整数jと正の整数xのペア（ x 、 j ）によって特徴付けられます。



少なくともYの幅を持つ長方形は バッファーと呼ばれ、それぞれが個別のレベルにパックされます。 つまり、そのような長方形が捕まえられた場合、あなたは緊急に新しいレベルを開く必要があります。その高さはそれに等しいです。 他のすべて（非バッファー）は、最初の適切なレベルにパッケージ化されます。 適切-同じペア（ x 、 j ）の意味。 突然十分なスペースがない場合、非バッファーの長方形が新しいレベルの最初になり、このレベルの高さは2 ^jになります。

一般に、ある種の不健康な階層。

この例では、 Y = 0.4です。

圧縮アルゴリズム

圧縮アルゴリズムはBiNFLに基づいており、基本的にトップレベルのパッケージング方法へのパッチです。

一般的な違いは、最上位が常に左から右に詰め込まれていることです。

圧縮パーツの適合：上位レベルにパックされた各長方形について、下位レベルでその下にスペースがあるかどうかを確認します。 下位レベルに移動してその一部を上位レベルに残すことができる場合、それは移動します（したがって、Part Fit-部分的に前のレベルに「押す」ことができます）。 このようにして、第2レベルの全体の高さを減らすことができます。 彼はパッケージングにもはや根本的な影響を与えません。 最初の図は、レベル間にぶら下がっている長方形を示しています-シフトされました。

圧縮完全適合：上位レベルにパックされた各長方形について、前のレベルに完全にシフトダウンできるかどうかがチェックされます。 実際、可能であれば、それは変化しています。 これにより、戦略的な利点が得られます。この方法で解放されたスペースは、次の長方形に使用できます。 残念ながら、2番目の図にはこのような状況は含まれていませんが、2つの失敗を確認できます。

圧縮コンボ：はい、これは前の2つの組み合わせであり、したがってそれらの利点の組み合わせです。 3番目の図に示します。

オンラインフィット

以前の方法よりも面倒な方法ですが、生産性も向上します。 タスクのオフラインバージョンのBurkeアルゴリズムに基づいています。 おそらくいくつかの側面を描きます。







パッケージングプロセス中に、空の領域が形成される場合があります。この領域は、アルゴリズムが最初に埋めようとします。 それらがどのように形成されるかは、左の写真に示されています。 このため、帯域幅の特定の表現を保存する必要があることに注意してください。

空の領域を埋めた後、2つ（またはうまくいかないかもしれません）を取得することがあります。



また、1ステップのパッケージングで複数の領域を一度に作成できます。長方形の下のスペースは垂直方向に分析され、「ステップ」の数で分割されます。 中央の写真では、長方形が再びパックされた後の空の領域の2つの分割が示されています（ところで、この場所では水平に分割した方が良いように思われます）。

一般に、森の中に行くほど、より多くのボイドが発生します。 各ステップで、急速にフェードするボイドを詳しく調べます。 ここで、別の最適化が表示されます。使用可能な領域の測定値を入力し、好ましくないものを破棄できます。



適切な空き領域がない場合、パッケージングは​​バーク方式で続行されます。 思い出させます。 ストリップの高さマップが作成され、現在最も低い領域で長方形が試行されます。 そこに入らない場合、低い場所は最も近いステップのレベルまで「埋められ」、検索が繰り返されます。 したがって、潜在的な場所を最上部にプッシュすることができます。次に、空きスペースを形成するための別のオプションがあります（右を参照）。

空のエリアを識別するために、すべてのステップで同じ標高マップが使用されます。



一般的に、すべてがすでに言われています。 最初に空のエリアに詰め込み、次に最下層、最後に重要なこととして、上から「最下層」の縮退したケースに詰め込みます。

あとがき

何が起こっているのかという目的のない感覚を払拭するために、半限られたストリップでの2次元パッキングアルゴリズムの適用の古典的で刺激的な例を挙げます。 これは、マルチプロセッサシステム用のタスクスケジューラです。 クラスタ向けの最新のソフトウェアでは、より「成熟した」アルゴリズムが使用されますが、 計画タスク自体は2DSPに削減されます。 クラスター操作の条件下では、着信タスクのフローはパッケージングのオンラインデータにすぎません。水平方向のディメンション-必要なコア数、垂直方向-タスクの時間です。 （すべてがテクノロジーの夜明けのようです。コンピューターに接続し、必要なリソースの量とパンチカードがスピンする時間を事前に警告します）。 スケジューラは、タスクに特定のプロセッサを割り当て、開始時間を決定する必要があります。 ちなみに、スケジューラがタスクを待っているか、その場所を考えている間に時間がなくなるため、純粋な形式ではアルゴリズムを使用できません。 さらに、プログラマーはさまざまな特定の条件下で手で縛られます。タスクの優先度。 実行時にタスクをスケーリングする機能。 ハードウェアの遅延とシステムのセルフサービス（障害が発生したリソースに基づく再配布を含む）。 タスク内の通信の性質をクラスターのアーキテクチャなどにマッピングする

アルゴリズムは、実際の生活に適用し始めるまで、数学的厳密さにおいて完璧です。



そして最後に-心地よい、非人格的な形でのアルゴリズムの比較説明。 これは、最適なパッキング高さ（長方形の面積の合計をストリップの幅で割ったもの）と得られたものの比率です。

Nfl	Ffl	Bfl	ビンフル	NFS	FFS	Bfs	Hs	アザール	CPF	CFF	CC	の
0.56	0.63	0.75	0.56	0.45	0.57	0.57	0.37	0.44	0.60	0.59	0.63	0.72

---

コード（Qt）：

アルゴリズムpackager.h packager.cpp

Gui window.h window.cpp renderarea.h renderarea.cpp main.cpp