مشاكل التعبئة والتغليف

تختلف هذه المسائل رياضياً عن الأفكار الواردة في نظرية تعبئة الدوائر . وتتناول مسألة تعبئة الدوائر ذات الصلة تعبئة دوائر ، قد تكون بأحجام مختلفة، على سطح ما، على سبيل المثال المستوى أو الكرة .

لا يمكن أبدًا رصّ نظائر الدائرة في أبعاد أخرى بكفاءة كاملة في أبعاد أكبر من بُعد واحد (في كون أحادي البُعد، نظير الدائرة هو نقطتان فقط). أي أنه ستكون هناك دائمًا مساحة غير مُستغلة إذا اقتصر الرصّ على الدوائر فقط. تُحقق الطريقة الأكثر كفاءة لرصّ الدوائر، وهي الرصّ السداسي ، كفاءة تقارب 91%. ^{[ 8 ]}

في ثلاثة أبعاد، توفر البنى المتراصة أفضل ترتيب شبكي للكرات، ويُعتقد أنها الأمثل بين جميع الترتيبات. مع ترتيبات الكرات "البسيطة" في ثلاثة أبعاد (مع تعريف دقيق لكلمة "بسيطة")، توجد تسعة ترتيبات قابلة للتحديد. ^{[ 9 ]} كما ثبت أن شبكة E8 ثمانية الأبعاد وشبكة Leech ذات 24 بُعدًا هما الأمثل في فضاء الأبعاد الحقيقية الخاص بهما.

يمكن ترتيب المكعبات بسهولة لملء الفراغ ثلاثي الأبعاد بالكامل، وأكثر التراص طبيعية هو شكل قرص العسل المكعب . لا يوجد أي مجسم أفلاطوني آخر قادر على ملء الفراغ بمفرده، ولكن بعض النتائج الأولية معروفة. يمكن أن تحقق رباعيات الأوجه نسبة تعبئة لا تقل عن 85%. أحد أفضل تراكيب المجسمات الاثني عشرية المنتظمة يعتمد على الشبكة المكعبة ذات المراكز الوجهية (FCC) المذكورة سابقًا.

يمكن للأشكال الرباعية الأوجه والأشكال الثمانية الأوجه معًا أن تملأ كل الفراغ في ترتيب يُعرف باسم خلية النحل الرباعية الأوجه والثمانية الأوجه .

تشير عمليات المحاكاة التي تجمع بين أساليب التحسين المحلية والتعبئة العشوائية إلى أن تعبئة الشبكة للأشكال العشرية الوجوه، والأشكال الاثني عشرية الوجوه، والأشكال الثمانية الوجوه هي الأمثل في الفئة الأوسع لجميع التعبئة. ^{[ 3 ]}

حدد الحد الأدنى لعدد الحاويات المكعبة (الصناديق) اللازمة لتعبئة مجموعة معينة من المكعبات. يمكن تدوير المكعبات المستطيلة المراد تعبئتها بزاوية 90 درجة حول كل محور.

إن مسألة إيجاد أصغر كرة يمكن وضع k من الكرات المفتوحة المنفصلة بداخلها لها حل بسيط وكامل في الفضاء الإقليدي ذي الأبعاد n إذا${\displaystyle k\leq n+1}$وفي فضاء هيلبرت لانهائي الأبعاد بدون قيود. يجدر وصف ذلك بالتفصيل هنا لإعطاء فكرة عن المسألة العامة. في هذه الحالة، يتوفر تكوين من k كرات وحدة متماسّة مثنى مثنى . يضع الباحثون المراكز عند الرؤوس.${\displaystyle a_{1},\dots ,a_{k}}$من شخص عادي${\displaystyle (k-1)}$مُجَسَّمٌ مُعَمَّدٌ ذو ضلعين؛ يُمكن تحقيقه بسهولة انطلاقًا من أساس متعامد . تُظهر عملية حسابية بسيطة أن بُعد كل رأس عن مركز الثقل هو${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$علاوة على ذلك، فإن أي نقطة أخرى في الفضاء تكون بالضرورة على مسافة أكبر من رأس واحد على الأقل من الرؤوس k . من حيث احتواء الكرات، فإن الكرات الوحدوية المفتوحة k المتمركزة عند${\displaystyle a_{1},\dots ,a_{k}}$يتم تضمينها في كرة نصف قطرها${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$وهو الحد الأدنى لهذا التكوين.

لإثبات أن هذا التكوين هو الأمثل، دع${\displaystyle x_{1},\dots ,x_{k}}$لتكن مراكز k كرات مفتوحة منفصلة ذات وحدة واحدة محصورة في كرة نصف قطرها r مركزها نقطة${\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}\|}$هذه الخريطة هي خريطة ليبشيتز -1، وبحسب نظرية كيرزبراون، فإنها تمتد إلى خريطة ليبشيتز-1 معرفة عالميًا؛ على وجه الخصوص، توجد نقطة${\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}$يُبين هذا أنه يوجد k كرة مفتوحة منفصلة من نوع الوحدة في كرة نصف قطرها r إذا وفقط إذا${\displaystyle r\geq r_{k}}$لاحظ أنه في فضاء هيلبرت ذي أبعاد لا نهائية، فإن هذا يعني وجود عدد لا نهائي من الكرات المفتوحة المنفصلة ذات الوحدة داخل كرة نصف قطرها r إذا وفقط إذا${\displaystyle r\geq 1+{\sqrt {2}}}$على سبيل المثال، الكرات الوحدوية المتمركزة عند${\displaystyle {\sqrt {2}}e_{j}}$، أين${\displaystyle \{e_{j}\}_{j}}$هي أساس متعامد، وهي منفصلة ومضمنة في كرة نصف قطرها${\displaystyle 1+{\sqrt {2}}}$متمركزة عند نقطة الأصل. علاوة على ذلك، لـ${\displaystyle r<1+{\sqrt {2}}}$، الحد الأقصى لعدد الكرات المفتوحة المنفصلة ذات الوحدة داخل كرة نصف قطرها r هو$${\displaystyle \left\lfloor {\frac {2}{2-(r-1)^{2}}}\right\rfloor .}$$

يحدد الناس عدد الأجسام الكروية ذات القطر المحدد d التي يمكن وضعها في متوازي مستطيلات بحجم${\displaystyle a\times b\times c}$.

يحدد العلماء الحد الأدنى للارتفاع h لأسطوانة ذات نصف قطر R معين بحيث يمكن وضع n كرة متطابقة نصف قطرها r (< R ) . ^{[ 12 ]} بالنسبة لنصف قطر صغير R ، تترتب الكرات في هياكل منتظمة تسمى الهياكل العمودية .

يحدد الناس الحد الأدنى لنصف القطر R الذي يسمح بتعبئة n من المجسمات متعددة الأوجه المتطابقة ذات الحجم الواحد من شكل معين. ^{[ 13 ]}

يُعطى الأشخاص عددًا من الدوائر الموحدة ، وعليهم وضعها في أصغر حاوية ممكنة. وقد دُرست أنواع عديدة من الحاويات:

• تُعدّ عملية رصّ الدوائر داخل دائرة عمليةً وثيقة الصلة بنشر النقاط على دائرة الوحدة، بهدف إيجاد أصغر مسافة فاصلة، d _{_n} ، بين النقاط. وقد تمّ إثبات وجود حلول مثلى عندما تكون n ≤ 14 و n = 19 .
• تعبئة الدوائر في مربع - وهي عملية ترتبط ارتباطًا وثيقًا بنشر النقاط في مربع وحدة بهدف إيجاد أصغر مسافة فاصلة، d _n ، بين النقاط. وللتحويل بين هاتين الصيغتين للمسألة، سيكون طول ضلع المربع للدوائر الوحدة هو${\displaystyle L=2+2/d_{n}}$.

  

  تم إثبات الحلول المثلى لـ n ≤ 30 .
• تعبئة الدوائر في مستطيل
• تعبئة الدوائر في مثلث قائم الزاوية متساوي الساقين - توجد تقديرات جيدة معروفة لـ n < 300 .
• تعبئة الدوائر في مثلث متساوي الأضلاع - الحلول المثلى معروفة لـ n ≤ 15 ، والتخمينات متاحة لـ n ≤ 34. ^{[ 14 ]}

يُعطى الأشخاص n مربعًا وحدة ، وعليهم وضعها في أصغر حاوية ممكنة، حيث يختلف نوع الحاوية:

• تعبئة المربعات في مربع : تم إثبات الحلول المثلى لقيم n من 1 إلى 10، ومن 14 إلى 16، ومن 22 إلى 25، ومن 33 إلى 36، ومن 62 إلى 64، ومن 79 إلى 81، ومن 98 إلى 100، وأي عدد صحيح مربع . المساحة المهدرة هي O ( a³ ^/⁵ ) تقريبًا .
• تعبئة المربعات في دائرة : توجد حلول جيدة معروفة لـ n ≤ 35 .

  

• تعبئة مستطيلات متطابقة داخل مستطيل : تُعدّ مشكلة تعبئة عدة مستطيلات متطابقة بأبعاد ( طول × عرض ) مع إمكانية تدويرها بزاوية 90 درجة، داخل مستطيل أكبر بأبعاد ( طول × عرض )، من المشكلات الشائعة في تطبيقات مثل تحميل الصناديق على المنصات، وتحديدًا في تخزين لب الخشب . على سبيل المثال، يمكن تعبئة 147 مستطيلاً بأبعاد (137 × 95) داخل مستطيل بأبعاد (1600 × 1230).
• تجميع مستطيلات مختلفة داخل مستطيل : تُعدّ مشكلة تجميع عدة مستطيلات بأطوال وعرض مختلفة داخل مستطيل محيط ذي مساحة دنيا (دون تحديد عرض أو ارتفاع المستطيل المحيط) ذات أهمية بالغة في دمج الصور في صورة واحدة أكبر. غالبًا ما يتم عرض صفحة الويب التي تُحمّل صورة واحدة كبيرة بشكل أسرع في المتصفح من الصفحة نفسها التي تُحمّل عدة صور صغيرة، وذلك بسبب العبء الإضافي الناتج عن طلب كل صورة من خادم الويب. تُصنّف هذه المشكلة عمومًا ضمن فئة NP-complete ، ولكن توجد خوارزميات سريعة لحلّ الحالات الصغيرة منها.