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

今日、Habr様、コンビナトリアルオプティマイゼーションについてお話します。
古代（少なくとも前世紀の初めから）から、数学者は、必要で有用な物のある量のビールをバックパックに最適に入れる方法を知りました。 ナップザックとそのサブタスクの問題が定式化されました-何千もの！ -コンピュータ科学者、暗号作成者、さらには言語学者に興味を持っている。

2次元のパッケージング（2次元のビンパッキング）の問題の1つであるコンテナーの パッキング （ ビンパッキング問題 ）は、ナップザックの問題から生じました。 いくつかのバリエーションを再び破棄したので、ようやく半制限されたストリップの2次元パッキング（2次元ストリップパッキング、2DSP）に行きました。 すでに舞台裏にどれだけ面白いものが残っているのか感じてください。 しかし、私たちは分類を歩き終えていません。 2DSPには2つの入力オプションがあります。パックされたオブジェクトのセットが事前にわかっている場合（オフラインの問題）と、データがバッチで到着する場合（オンラインの問題）です。

この記事では、オフラインバリアント2DSPを解決するためのアルゴリズムについて説明します。 カットの下には、少しの素材と色の付いた正方形の写真がたくさんあります。

実際、問題は何ですか？

2次元のパッキング問題の特殊なケースとして、2DSPは、特定の形状のオブジェクトを特定の形状の有限数のコンテナーにパッキングすることにあり、使用されるコンテナーの数が最小になるか、オブジェクトの数または体積（パックされる）が最大になります。 2次元パッケージとの違いは、コンテナが1つしかないことです。コンテナの数を最小化する代わりに、1つの高さを最小化します。 必要に応じて最大の梱包密度を提供します。

問題はNP困難であるため、研究は主に近似解法アルゴリズムの開発に焦点を当てています。 （ 遺伝的アルゴリズムはHabréで言及されました）。 近似アルゴリズムは、一定の精度で最適なソリューションを見つけますが、データセットの最適なパッケージ化を保証するものではありません。 この場合、最適性の基準は、最適化しようとしたものによって異なります。
私は、最も単純な戦略と、これが人生でどのように適用されるかについて説明します（ビールの入ったバックパックを除く）。

したがって、n個の長方形のセットと、幅Wが固定され、高さが無限の半制限のコンテナーガラスがあります。 幅の各長方形はWを超えません。タスクは、グラスをできるだけ小さくするために、オーバーレイや交差なしで長方形をグラスに入れることです。 すべての長方形を直交してパックする必要があり、回転できないことに同意しましょう。

ソースデータ （20世紀の初め、キュービズム）	半制限車線	包装オプション（悪い）	パッケージングオプション（より良い）

この問題には、パックされた長方形の高さがストリップの幅で割った合計面積に等しいという理想的なソリューションがあることがわかります。

動物園アルゴリズム

2DSPのオフラインバージョンでは、すべてのパックされた長方形のサイズがすぐにわかるため、特定の基準に従ってソート、選択、グループ化、または適切な場所への単純なバンプが可能です。 ほとんどのアルゴリズムはこれに基づいています：

1. レベル（レベル）
2. 棚（棚）
3. フラット（平面）

フラットアルゴリズムは長方形を互いに厳密に近づけて配置しますが、これは一見すると思われるかもしれませんが、これは最も成功した戦略ではありません。 レベル1は、ストリップを選択された長方形の1つと同じ高さのレベルに分割し、他のすべてを特定の基準に従って特定のレベルに配置します。 シェルフシェルフは、一度に複数のシェルフ（シェルフ）を事前に決定し、それらに沿って長方形をプッシュします。この動作はオンラインアルゴリズムの典型であり、これはまったく別の話です。

一般的な単語に拡張するよりも、すべてを順番に処理する方が適切です。

次のフィット減少高

彼らが言うように、アルゴリズムは「額に」。 長方形は高さの増加なし（高さの減少のヒント）で並べ替えられ、最高はストリップの左下隅にあり、それにより高さが等しい最初のレベルを初期化します。 残りの長方形は左から右に配置されますが、現在のレベルにはスペースがあります。 レベルに収まらない長方形は上に配置され、次のレベルを形成します。
次の2つの例について、各アルゴリズムの図を作成します。明確にするために、左側では長方形の形状が長くなり、右側ではより正方形になります。

NFDHアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法 
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：レベル= 0;  h（レベル）= 0;  w（レベル）= 0;  i = 1
  2：h（L1）≥h（L2）≥...≥h（Ln）のように、高さが増加しない順に長方形をソートします
  3：ストリップの下部で左揃えの長方形Liをパック
  4：h（レベル）= h（Li）;  w（レベル）= w（Li）
  5：i = 2..nの場合
  6：W-w（レベル）≥w（Li）の場合
  7：長方形Li-1の右側に長方形Liを詰める
  8：w（レベル）+ = w（Li）
  9：else [W-w（レベル）<w（Li）]
 10：前のレベルの上に新しいレベルを作成し、新しいレベルに長方形Liをパックします
 11：レベル++;  w（レベル）= w（Li）;  h（レベル）= h（レベル-1）+ h（Li）
 12：終了する場合
 13：終了
 14：H = h（レベル）を印刷 

ファーストフィットの減少

前のアルゴリズムと同様に、次の長方形ごとに、場所が最後のレベルだけでなく、最低レベルから検索されるという違いがあります。 したがって、「最初の適合」-長方形は下から最初の適切なレベルに配置されます。 直観的には、パッケージングの方が優れています。 別の重要な違いはパフォーマンスです。最悪の場合、すべてのレベルをボトムアップですべてのステップで考慮する必要があるためです。

FFDHアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：レベル= 0;  h（レベル）= 0;  i = 1;  LevelNum = 1
  2：h（L1）≥h（L2）≥...≥h（Ln）のように、高さが増加しない順に長方形をソートします
  3：ストリップの下部で左揃えの長方形Liをパックします。  h（レベル+ 1）= h（Li）
  4：for i = 2..n do
  5：すべてのレベルを（下から）十分なスペースのある最低レベルで検索します
  6：そのようなレベルが存在する場合
  7：長方形Liをそのレベルで左揃えでパック
  8：その他[既存のすべてのレベルに十分なスペースがない]
  9：LevelNum ++;  level = LevelNum;  h（レベル）= h（レベル-1）+ h（Li）
 10：新しいレベルで長方形Liをパックする
 11：終了する場合
 12：終了
 13：H = h（レベル）を印刷 

ベストフィットが高くなる

前のアルゴリズムの修正。 その本質は、最初の長方形ではなく、次の長方形のパッキングに適したレベルのものであり、最適なものが選択されます。 最適なレベルは、現在の四角形をパックした後にスペースが最小限になるレベルです。 簡単に言えば、最小の適切なスペースが選択され、レベルのより良い充填に貢献します。

BFDHアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：レベル= 0;  h（レベル）= 0;  i = 1;  LevelNum = 1
  2：h（L1）≥h（L2）≥...≥h（Ln）のように、高さが増加しない順に長方形をソートします
  3：ストリップの下部で左揃えの長方形Liをパックします。  h（レベル+ 1）= h（Li）
  4：for i = 2..n do
  5：すべてのレベルを検索して、十分なスペースがあり、残りのスペースが最小のレベルを探します
  6：そのようなレベルが存在する場合
  7：長方形Liをそのレベルで左揃えでパック
  8：その他[既存のすべてのレベルに十分なスペースがない]
  9：最上位レベルの上に新しいレベルを作成し、長方形Liをパックします
 10：LevelNum ++;  level = LevelNum;  h（レベル）= h（レベル-1）+ h（Li）
 11：終了する場合
 12：終了
 13：H = h（レベル）を印刷 

ナップザック0-1

ここに詳しく滞在する価値があります。 ナップザック0-1は、ナップザック問題の特殊なケースです。 主な質問（いいえ、42ではなく、結果のパッケージングボリューム）に答えるだけでなく、 ソリューション（パッケージ化する必要があるアイテムのリスト）を提供することも注目に値します。 手順は次のとおりです。長方形は高さの増加しない順にソートされます。 最初の長方形は新しいレベルにパックされます。 このレベルでは、ナップザック0-1問題の解決策があります。これは、面積が最大化された長方形のリストを提供します。 選択された長方形がパックされ、アンパックされたリストから抽出され、レベルが閉じられ、新しい長方形が開きます-通常どおり、残りの最初の（最高）が初期化されます。 長方形ができるまで繰り返します。

アルゴリズムKP01

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：h（L1）≥h（L2）≥...≥h（Ln）のように、高さが増加しない順に長方形をソートします
  2：レベル= 0
  3：展開された長方形がある間に
  4：最初にアンパックされた長方形をパック、Liが言う
  5：h（レベル）+ = h（Li）
  6：KP01インスタンスを解決する
  7：選択した長方形をパック
  8：レベル=レベル+ 1
  9：しばらくの間
 10：印刷H = h（レベル） 

スプリットフィット

「分割統治」の原則に基づいてFFDNを改善するために設計されたアルゴリズム。 まず、ストリップの半分よりも広い長方形が選択されます。 最初に梱包されます。 これらのうち、さらに広いものが選択されます。ストリップの2/3よりも広いです。 FFDHアルゴリズムが詰め込まれています。 それらの上に、 次のレベルから始めましょう（レベルRと呼びましょう）、残りの1つはパックされています。それらはまだ1/2より広いですが、すでに2/3です。 また、FFDHを使用してパッケージ化されます。 この分割は、レベルRで始まり、パッケージの現在の上部境界で終わる、ちょうどパックされたものの右側に1/3の幅の空き領域を作成します（つまり、長方形1/2 <幅<= 2/3の上に拡張しません）。 1/2ストライプよりも狭い残りのすべての長方形は、最初に同じFFDHを使用して、形成された領域に詰め込まれ、収まらない場合は上から詰められます。 言葉では面倒に聞こえますが、画像はより鮮明になります。 そして、私の文学的なエクササイズにすでに疲れている人のために-擬似コード：

SFアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
 1：m≥1をL内のすべての長方形の最大整数とします
   最大で幅1 = m
 2：長方形のリストLを2つのサブリストL1とL2に分割します
    L1は、幅よりも大きい長方形のリストです
    1 /（m + 1）、L2は最大1 /（m + 1）の幅の長方形のリスト
 3：FFDHアルゴリズムを使用して、L1長方形をストリップに詰めます
 4：このパッキングのブロックを再配置して、幅のブロックを
    （m + 1）/（m + 2）よりも大きい場合、幅よりも小さい
   最大（m + 1）/（m + 2）
 5：幅が最大で1 /（m + 2）の長方形を領域Rに詰める
   長方形が上部に重ならないようにFFDHアルゴリズムを使用する
    RのRとRに収まらないものは、L1のパッキングの上にパッキングされます。
 6：各レベルの高さを追加することにより、ストリップの高さを出力します 

参加する

どうやら、このアルゴリズムは入力データの特定の性質のために投獄されました。まあ、実際の状況には存在する権利があります。 これで、すべてを自分で理解できるようになります。 通常のように、増加しない高さでソートされた長方形はペアで結合され、ペアの高さの差が指定された分数（通常0〜10％）を超えないようにします。 別の条件は、それらの合計幅がストリップに収まることです。 結果の「スーパー長方形」は、NFDHとFFDHを使用してペアなしで残りと一緒にパックされ、最適なソリューションが選択されます。
長方形が幅で並べ替えられ、垂直方向に結合される場合、このアルゴリズムにはバリエーションがあります。これは、ペアの幅の最大偏差が所定のパーセント数だけ同じ条件で行われます。

結合アルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}、aとしての定数ガンマ
       割合とストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：h（L1）≥h（L2）≥...≥h（Ln）のように、高さが増加しない順に長方形をソートします
  2：j = 1
  3：一方、j + 1≤n do
  4：if（h（Lj）-h（Lj + 1））/ h（Lj）* 100 <ガンマ
         そしてw（Lj）+ w（Lj + 1）≤W
  5：w（Lj）+ = w（Lj + 1）
  6：j + = 2
  7：その他
  8：j ++
  9：終了する場合
 10：終了
 11：NFDHおよびFFDHアルゴリズムを実行して、長方形をパックします
 12：最適なソリューションから、元のインスタンスの実行可能なパッキングを構築します
 13：各レベルの高さを追加することにより、ストリップの高さを出力します 

回転しない床の天井

まだスペースレベルにとどまることに困惑している場合は、このアルゴリズムが最適です。 長方形は高さの増加によってソートされます（予想外に、そうですか？）そして、いくつかの修正を加えたBFDHアルゴリズムが適用されます。 各レベルには「床」と「天井」があります。 可能な限り、長方形は「床」に左から右に詰め込まれます。 場所が終わると、「天井」を右から左に詰め込もうとします。 天井にスペースがない場合は、新しいレベルのみが始まります。 BFDHの最高の伝統では、あらゆる段階で、最初に「床」、次に「天井」のすべてのレベルが最適な場所で表示されます。 ご覧のとおり、パッケージングは​​悪くありません。 このメソッドは、「天井」に最小の長方形を正常にパックします。

FCNRアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：h（L1）≥h（L2）≥...≥h（Ln）のように、高さが増加しない順に長方形をソートします
  2：for i = 1..n do
  3：Liが上限に達した場合
  4：天井にLiを最小限の残余スペースで詰める
  5：その他[Liは上限に達していない]
  6：Liがフロア実現可能であれば
  7：最小の残余スペースで床にリチウムを詰める
  8：その他[Liはフロア実行不可能]
  9：レベル++;
 10：終了する場合
 11：終了する場合
 12：終了
 13：ストリップの高さHを出力します。これは、各レベルの高さを追加することにより求められます 

スレイター

レベルに分割することなく、「フラットな」アルゴリズムの時代が来ました。 Sleatorアルゴリズムは、バックパックをパックするという直感的な原則を使用します。最大のアイテムを下に折り、小さなアイテムで埋めます。 外観は次のとおりです。 長方形から、ストリップの半分よりも幅が広い、幅の広いものが選択され、推測し、左に揃えてランダムに積み重ねられます。 残りのものは、増加しない高さでソートされ、既に配置されているものに向かって左から右に次々に積み重ねられ始めます。 それらの合計幅がストリップの幅の半分を超えるとすぐに、残りのストリップは、「現時点では少ない」という原則に従って、左（ストリップの左端から開始）または右（中央から）に散らばります。 図からわかるように、ボックスよりもこの方法で本を積み重ねる方が便利です。

Sleatorアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：Lを長方形で構成される2つのサブリストL1およびL2に分割する
    それぞれ幅が1/2より大きく、最大で1/2の幅。
  2：L1のすべての長方形を左上に揃えて積み重ねます
    ストリップの下部から開始します。  hstackを計算する
  3：パッキングはHstackより上に続きます
  4：増加しない高さに従ってL2の長方形をソートします
     i（n）に対してh（Li）≥h（Li + 1）
  5：HtallをリストL2の最も高い長方形の高さとします。
  6：左から右に左揃えで長方形を詰める
    詰めるスペースが不十分になるまでストリップの端
    長方形またはすべての長方形がパックされている
  7：ストリップを垂直線で2つの等しいセグメントに分割します。
    内部が傍受される可能性のある長方形が1つある可能性があります
    縦線で。
  8：HrightとHleftを右側の長方形の高さとする
     （それぞれ左）左（または右）のエッジを持つストリップの半分
    垂直線に隣接しているか、その内部が遮断されている
    縦線で
  9：展開された長方形がある間に
 10：長さ半分の水平線を描く
      高さがHleftとHrightである長方形
 11：後続の梱包はすべて左側になります
      またはストリップの右セグメント
 12：最小の高さとパックのセグメントを選択します
      ストリップの端から
      すべての長方形が完成するまでの縦線
      パックされているか、収まらない長方形がある
 13：終了
 14：印刷H =最大{Hleft;  Hright} 

バーク

ここでも、追加の「高さマップ」が導入されるレベルレスアルゴリズム：

 |  |  |  _ _ ___ |
 |  |  |  |  | _ | _ |  |  |
 |  |  | _ |  |  |  |  |
 | _ _ _ _ _ _ _ _ _ | |  .. | _ | _ | _ | _ _ | _ | _ _ |
  0 0 0 0 0 0 0 0 0 1 0 3 2 3 0 3 3 

これは、ストリップが塗りつぶされると、最も塗りつぶされていない領域とその幅を追跡できる配列です。 最初はゼロで埋められます。 長方形は、増加しない、突然の幅でソートされます。 次に、アルゴリズムの各ステップで：
1.最低領域の位置が計算されます-配列の最小値のインデックス。
2.最も適切な長方形が選択されます-最初に、この領域に収まり、次に、できるだけ広く塗りつぶされます。
3.適切な長方形が見つかった場合、次のいずれかの方法でこの領域に配置されます。
3.1。エリアの左端。
3.2近隣の1つがストリップのエッジである場合、より高い近隣に近い場合、エッジに近い。
3.3近隣の1つがストリップの端である場合、より低い隣に近く、その後端から遠い。 長方形の幅に対応する配列の値に、その高さが追加されます。
4.適切な長方形がない場合、エリアは、その高さを最も近いエッジの高さに揃えることによって「塗りつぶされ」ます。
このアルゴリズムを使用してテトリスをプレイするボットをすでに作成したいとお考えですか？

バークアルゴリズム

 入力：パックする長方形の数n、
       長方形の寸法
        {w（Li）;  h（Li）}およびストリップ幅W
出力：ストリップで得られたパッキングの高さ。
  1：w（Li）≥w（Li + 1）≥..≥W（Ln）のように、増加しない幅に従って長方形をソートします
  2：各配置ポリシーについて
     （左端、最も高い隣人、最も小さい隣人）do
  3：長方形がパックされていない間
  4：最も低いギャップを見つける
  5：w（Li）≤GapWidthの場合
  6：配置ポリシーを使用して最適な四角形を配置する
  7：配列の要素を適切な高さに上げる
  8：その他
  9：最下位の高さまでギャップを上げる
 10：終了する場合
 11：終了
 12：終了
 13：最大のエントリを持つ配列の要素は、パッキングの全体の高さを示します
 14：各配置ポリシーによって取得された総梱包高さを比較し、最適なソリューションを返します 

誰が良い

各アルゴリズムの結果は帯域幅のレベルであり、少ないほど良いです。 それに対する最適の比率によって推定できます：



2セットのソースデータの結果を比較します。

	最適 決定	Nfdh	Ffdh	Bfdh	Kp01	SF	参加する	FCNR	スレイター	ブルーク
セット1	149	0.65	0.71	0.71	0.71	0.75	0.61	0.83	0.68	0.72
セット2	140	0.66	0.77	0.77	0.78	0.77	0.70	0.84	0.51	0.71

Floor Ceilingアルゴリズムが両方のデータセットで勝ったことがわかります。 Sleatorは最初のセットでより良い結果を示し、反対にJoinは2番目のセットにより適していることに注意してください。 しかし、これはすべて統計に過ぎません。

エピローグ

簡単な定式化により、バイナリパッケージングのタスクは、オブジェクトの直接的な梱包や材料の切断、資金の割り当て、クラスターでのタスクの計画など、膨大な数の実用的なアプリケーションに適用できます。 人生には洗練された問題はほとんどありませんが、いくつかの条件が限られているため、状況を多項式時間で達成できる優れたソリューションを備えた美しい数学モデルに減らすことができます。 そして、一度、バタフライ効果の結果として、破棄された条件はかなりの重量を要し、決定はすべての無名の人に渡ります。 世界が不完全であるのはそのような仮定のためです。

気が散ったもの。 次の部分では、タスクのオンラインバージョンとオフショアアルゴリズムについてお話したいと思います。 頑張って！

---

インスピレーションの源：
Nthabiseng Ntene 2D指向ストリップパッキング問題へのアルゴリズム的アプローチ
デビッド・ピシンガーナップザックの問題
二次元パッキングに関する調査
レベルアルゴリズムとシェルフアルゴリズム （注意、涙目設計）

コード（Qt）：
アルゴリズムpackager.h packager.cpp
Gui window.h window.cpp renderarea.h renderarea.cpp main.cpp

UPD： オンラインアルゴリズム