梱包の問題

梱包問題は数学における最適化問題の一種で、物体を容器に詰め込むことを試みる問題です。目標は、1 つの容器をできるだけ密に詰めるか、またはすべての物体をできるだけ少ない容器に詰めることです。これらの問題の多くは、実際の梱包、保管、輸送の問題に関係しています。各梱包問題には、物体が重なり合うことが許される容器のすべての領域を完全に覆うのに、同じ物体がいくつ必要かという双対被覆問題が あります。

ビンパッキング問題では、人々に次のことが与えられます:

• コンテナー。通常は 2 次元または 3 次元の凸領域で、サイズが無限の場合もあります。問題によっては複数のコンテナーが与えられる場合があります。
• オブジェクトのセット。一部またはすべてを 1 つ以上のコンテナーにパックする必要があります。セットには、サイズが指定されたさまざまなオブジェクト、または繰り返し使用できる固定サイズの単一のオブジェクトを含めることができます。

通常、梱包は商品と他の商品やコンテナの壁が重ならないようにする必要があります。いくつかのバリエーションでは、最大の梱包密度で単一のコンテナを梱包する構成を見つけることが目的です。より一般的には、すべてのオブジェクトをできるだけ少ないコンテナに梱包することが目的です。^[1]いくつかのバリエーションでは、（オブジェクト同士の、またはコンテナの境界との）重なりが許容されますが、最小限に抑える必要があります。

これらの問題の多くは、容器のサイズがあらゆる方向に大きくなると、無限のユークリッド空間に物体をできるだけ密に詰め込む問題と同等になる。この問題は多くの科学分野に関連しており、大きな注目を集めている。ケプラー予想は、トーマス・カリスター・ヘイルズによって正しいと証明される何百年も前に、球を詰め込む最適解を仮定していた。楕円体^{[2] 、}プラトン立体とアルキメデス立体^[3] （四面体^{[4] [5]}を含む）、 [ ^{6 ]}三脚体（3つの正の軸に平行な光線に沿った立方体の和集合）、 ^[7]など、他の多くの形状も注目を集めている。

これらの問題は、円充填定理の考え方とは数学的に異なります。関連する円充填問題は、平面や球などの表面上に、異なるサイズの円を充填することを扱います。

他の次元の円に対応するものは、 1 より大きい次元で完全な効率で詰め込むことはできません(1 次元の宇宙では、円に相当するものは 2 つの点だけです)。つまり、円だけを詰め込むと、常に未使用のスペースが残ります。円を詰める最も効率的な方法である六角形の詰め込みは、約 91% の効率を生み出します。^[8]

3次元では、最密充填構造が球の格子充填に最適であり、すべての充填の中で最適であると考えられています。3次元での「単純な」球充填（「単純」は慎重に定義されます）では、9つの定義可能な充填が可能です。^[9] 8次元のE8格子と24次元のリーチ格子も、それぞれの実次元空間で最適であることが証明されています。

立方体は簡単に配置して三次元空間を完全に埋めることができます。最も自然な詰め方は立方ハニカムです。他のプラトン立体は単独で空間を埋めることはできませんが、いくつかの予備的な結果がわかっています。四面体は少なくとも 85% の詰め込みを実現できます。正十二面体の最も優れた詰め込みの 1 つは、前述の面心立方 (FCC) 格子に基づいています。

四面体と八面体は、四面体-八面体ハニカムと呼ばれる配置で空間全体を埋めることができます。

局所改善法とランダムパッキングを組み合わせたシミュレーションでは、二十面体、十二面体、八面体の格子パッキングが、すべてのパッキングのより広いクラスの中で最適であることが示唆されている。^[3]

指定されたアイテムの直方体セットを梱包するために必要な 直方体コンテナ (ビン)の最小数を決定します。梱包する長方形の直方体は、各軸で 90 度回転できます。

k 個 の互いに素な開単位球を内部に詰め込める最小の球を見つける問題は、 であればn次元ユークリッド空間では単純かつ完全な解があり、無制限の無限次元ヒルベルト空間では単純かつ完全な解があります。一般的な問題の概要を示すために、ここで詳しく説明する価値があります。この場合、k個の対接単位球の構成が利用可能です。中心を、辺が 2 である正規次元単体の頂点に配置します。これは、正規直交基底から始めて簡単に実現できます。簡単な計算で、各頂点の重心からの距離が であることがわかります。さらに、空間の他の点は、必ずk個の頂点のうちの少なくとも1 つからより大きな距離を持ちます。球の包含に関して言えば、を中心とするk 個の開単位球は、この構成に対して最小である半径 の球に含まれます。 ${\displaystyle k\leq n+1}$${\displaystyle a_{1},\dots ,a_{k}}$${\displaystyle (k-1)}$${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$${\displaystyle a_{1},\dots ,a_{k}}$${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$

この構成が最適であることを示すために、点 を中心とする半径rの球体に含まれるk 個の互いに素な開単位球体の中心を とします。各 について対応する を有限集合 からへ写像することを考えます。すべての について、この写像は 1-リプシッツであり、キルシュブラウンの定理により、これは大域的に定義される 1-リプシッツ写像に拡張されます。特に、すべての について となる点が存在するので、 も成り立ちます。これは、の場合に限り、半径rの球体にk 個の互いに素な開単位球体が存在することを示しています。無限次元ヒルベルト空間では、の場合に限り、半径rの球体の内部に無限個の互いに素な開単位球体が存在することになることに注意してください。たとえば、 が正規直交基底である を中心とする単位球体は互いに素であり、原点を中心とする半径 の球体に含まれます。さらに、 の場合、半径rの球体内の互いに素な開単位球の最大数は です。 ${\displaystyle x_{1},\dots ,x_{k}}$${\displaystyle x_{0}}$${\displaystyle \{x_{1},\dots ,x_{k}\}}$${\displaystyle \{a_{1},\dots ,a_{k}\}}$${\displaystyle x_{j}}$${\displaystyle a_{j}}$${\displaystyle 1\leq j\leq k}$${\displaystyle 1\leq i<j\leq k}$${\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$${\displaystyle a_{0}}$${\displaystyle 1\leq j\leq k}$${\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$${\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$ ${\displaystyle r\geq r_{k}}$${\displaystyle r\geq 1+{\sqrt {2}}}$${\displaystyle {\sqrt {2}}e_{j}}$${\displaystyle \{e_{j}\}_{j}}$${\displaystyle 1+{\sqrt {2}}}$${\displaystyle r<1+{\sqrt {2}}}$${\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$

人は、大きさの直方体に詰め込むことができる、直径dの球形の物体の数を決定します。 ${\displaystyle a\times b\times c}$

半径r（< R）の同一の球n個を詰め込むために必要な、半径Rが与えられた円柱の最小の高さhを決定します。^[12]半径Rが小さい場合、球は柱状構造と呼ばれる秩序だった構造に配列します。

与えられた形状のn個の同一の単位体積多面体を詰め込むための最小半径Rを決定する。 ^[13]

2 次元パッキング問題にはさまざまなバリエーションが研究されてきました。

人々はn 個の単位円を与えられ、それを可能な限り小さな容器に詰めなければなりません。いくつかの種類の容器が研究されています。

• 円を円の中に詰め込む- 点を単位円内に広げることと密接に関連しており、点間の最大最小距離d _{n を見つけることを目的としています。最適解は}n ≤ 13およびn = 19で証明されています。
• 正方形に円を詰める- 点間の最小距離d _nを見つけることを目的とした、単位正方形に点を広げることと密接に関連しています。問題のこれら 2 つの定式化を変換するには、単位円の正方形の辺は になります。${\displaystyle L=2+2/d_{n}}$

  

  n ≤ 30の場合に最適解が証明されています。
• 長方形の中に円を詰める
• 直角二等辺三角形に円を詰める- n < 300の場合、良好な推定値が知られています。
• 正三角形への円の詰め込み- n < 13の場合の最適解は知られており、n < 28の場合の推測も可能です。^[14]

人々はn 個の単位正方形を与えられ、それを可能な限り小さな容器に詰めなければなりません。容器の種類は次のように異なります。

• 正方形の中に正方形を詰める: 1〜10、14〜16、22〜25、33〜36、62〜64、79〜81、98〜100、および任意の平方整数のnに対して最適解が証明されています。無駄なスペースは漸近的にO ( a ^3/5 )です。
• 正方形を円の中に詰める: n ≤ 35の場合、良い解が知られています。

  

• 同一の長方形を長方形に詰め込む:サイズ( l , w )の単一の長方形の複数のインスタンスを、90° 回転させて、より大きなサイズ( L , W )の長方形に詰め込む問題は、パレットへの箱の積載や、特に木材パルプの積み込みなどの用途があります。たとえば、サイズ (1600,1230) の長方形に、サイズ (137,95) の長方形 147 個を詰め込むことができます。
• 異なる長方形を長方形に詰め込む: 幅と高さが異なる複数の長方形を、最小面積の囲み長方形(ただし、囲み長方形の幅と高さに境界はありません) に詰め込む問題は、画像を 1 つの大きな画像に結合する場合に重要な応用があります。Web サーバーから各画像を要求することに伴うオーバーヘッドのため、1 つの大きな画像を読み込む Web ページは、同じページが複数の小さな画像を読み込む場合よりもブラウザーでレンダリングが高速になることがよくあります。この問題は一般にNP 完全ですが、小さなインスタンスを解決するための高速アルゴリズムがあります。

タイリングやテッセレーションの問題では、隙間や重なりがあってはなりません。このタイプのパズルの多くは、長方形やポリオミノをより大きな長方形や正方形のような形に詰め込むというものです。

長方形（および直方体）を隙間や重なりのない長方形（直方体）に並べることに関して 重要な定理があります。

a × bの長方形に1 × nのストリップを詰め込むことができるのは、 nがaを割り切るかnがbを割り切る場合に限られます。^{[15] [16]}

デ・ブリュインの定理：箱が何らかの自然数p、q、rに対してap × abq × abcrの次元を持つ場合、箱は調和ブリック a × ab × abcで充填できる（つまり、箱はブリックの倍数である）。^[15]

ポリオミノタイリングの研究は、主に 2 つのクラスの問題、すなわち、合同なタイルで長方形をタイリングすることと、各nオミノを長方形に 1 つずつ詰めることに関係します。

2 番目の種類の古典的なパズルは、12 個のペントミノすべてを3×20、4×15、5×12、または 6×10 のサイズの長方形に配置することです。

不規則な物体のパッキングは、閉じた形の解法にはあまり適さない問題ですが、実際の環境科学への応用は非常に重要です。たとえば、不規則な形状の土壌粒子は、サイズや形状が異なるため、パッキングの仕方が異なり、植物種が根の形成に適応し、土壌中の水の移動を可能にするという重要な結果をもたらします。^[17]

与えられた多角形の集合が与えられた正方形の容器に収まるかどうかを決定する問題は、実数の存在理論に対して完全であることが示されている。^[18]

• ビンパッキング問題
• 等しい球の最密充填
• コンウェイパズル
• カバーの問題
• 在庫問題を切り詰める
• 楕円体パッキング
• キス数問題
• ナップザック問題
• ランダムクローズパック
• セット梱包
• スロトウバー・グラーツマパズル
• ストリップパッキングの問題
• 四面体パッキング
• テトリス

• ワイスタイン、エリック・W.「クラナーの定理」。マスワールド。
• ワイスタイン、エリック・W.「デ・ブライジンの定理」。マスワールド。

ウィキメディア・コモンズには、梱包の問題に関連するメディアがあります。

• 3次元ビンパッキングの最適化

多くのパズルの本や数学の雑誌には、パッキング問題に関する記事が掲載されています。

• パッキングに関するさまざまな MathWorld の記事へのリンク
• 正方形の詰め込みに関する MathWorld のノート。
• エリックの梱包センター
• www.packomania.com 表、グラフ、計算機、参考資料などが掲載されたサイト。
• 「Box Packing」、Ed Pegg, Jr.著、Wolfram Demonstrations Project、2007 年。
• 最もよく知られている等円の円内詰め（1100まで）

• Python での円詰めチャレンジ問題