مسألة تعبئة الصناديق
عند الانتقال إلى منزل جديد، تملأ صندوقًا تلو الآخر وتتساءل: هل كان ترتيب أذكى سيحتاج إلى صناديق أقل؟ هذه هي مسألة تعبئة الصناديق، وهي مشهورة بصعوبتها: حتى الحواسيب لا تجد أقل عدد من الصناديق للمدخلات الكبيرة إلا ببحث ذكي. ومع ذلك، تقترب القواعد البسيطة من الحل بشكل مدهش.
المسألة
لدينا عناصر لها أحجام وصناديق يتسع كل منها للمقدار نفسه، والمطلوب وضع كل عنصر في صندوق بحيث لا يفيض أي صندوق، باستخدام أقل عدد ممكن من الصناديق. يمكن أن تمثل الأحجام أوزانًا أو أطوالًا أو مددًا زمنية أو أحجام ملفات. تبدو كلغز لعصر يوم ممطر، لكنها NP-صعبة: لا تُعرف طريقة تجد أقل عدد من الصناديق بسرعة لكل مدخل.
قواعد سريعة
الملاءمة التالية تملأ صندوقًا واحدًا حتى لا يتسع للعنصر التالي، ثم تبدأ صندوقًا جديدًا ولا تعود إلى الوراء أبدًا. الملاءمة الأولى تُبقي كل الصناديق مفتوحة وتضع كل عنصر في أول صندوق فيه متسع. أفضل ملاءمة تضع كل عنصر في أكثر الصناديق امتلاءً من بين ما لا يزال فيه متسع. والثلاث تقرر فورًا، وهذا مفيد عندما تصل العناصر واحدًا تلو الآخر ويجب وضعها على الفور.
الترتيب أولًا
العناصر الكبيرة هي الصعبة، لأنها تحتاج إلى مساحة فارغة كبيرة. ترتيب العناصر من الأكبر إلى الأصغر ثم استخدام الملاءمة الأولى أو أفضل ملاءمة يضع العناصر الكبيرة والصناديق ما زالت فارغة، ويملأ الفجوات بالعناصر الصغيرة. لا تستخدم الملاءمة الأولى التنازلية أبدًا أكثر من 11/9 من أقل عدد من الصناديق، زائد ثابت، مقابل 1.7 ضعف للملاءمة الأولى على عناصر غير مرتبة.
مثال
خذ صناديق حجمها 10 والعناصر 2 و3 و2 و1 و3 و4 و5 و6 و7 و7، ومجموعها 40. تضع الملاءمة الأولى 2 و3 و2 و1 في الصندوق الأول، و3 و4 في الثاني، ثم يحتاج كل من 5 و6 و7 و7 إلى صندوق خاص به: 6 صناديق. وبعد الترتيب من الأكبر إلى الأصغر، تكوّن الملاءمة الأولى التنازلية 7 + 3 و7 + 3 و6 + 4 و5 + 2 + 2 + 1: أي 4 صناديق ممتلئة، وهو ما يساوي الحد الأدنى 40 / 10 = 4.
إيجاد أقل عدد من الصناديق
لعدد صغير من العناصر يمكن إيجاد الإجابة الدقيقة بالبرمجة الديناميكية على المجموعات الجزئية: لكل مجموعة من العناصر، يُبنى أقل عدد من الصناديق وأفرغ صندوق أخير يتسعان لها انطلاقًا من المجموعات التي ينقصها عنصر واحد. ويستغرق ذلك نحو 2ⁿ·n خطوة لـ n عنصر. أما الحالات الأكبر فتُحل بطريقة التفرع والتحديد أو بالبرمجة الصحيحة، ويبيّن الحد الأدنى إلى أي مدى قد تبعد التعبئة عن الأفضل.
أين تُستخدم
تحميل الشاحنات والحاويات، وقطع الأنابيب أو لفائف الورق من أطوال قياسية بأقل هدر ممكن (مسألة قطع المخزون)، ووضع الآلات الافتراضية على الخوادم، وحفظ الملفات على الأقراص، كلها مسائل تعبئة صناديق. وفي بُعدين أو ثلاثة أبعاد، مع علب بدلًا من الأعداد، تصبح المسألة أصعب.
الأسئلة المتداولة
ما الفرق بين تعبئة الصناديق الفورية (online) وغير الفورية (offline)؟
في الحالة الفورية، يجب وضع كل عنصر بمجرد وصوله دون معرفة البقية؛ وهكذا تعمل الملاءمة التالية والملاءمة الأولى وأفضل ملاءمة. وفي الحالة غير الفورية، تكون كل العناصر معروفة مسبقًا، فيمكن ترتيبها أولًا كما تفعل الملاءمة الأولى التنازلية.
إلى أي مدى تقترب الملاءمة الأولى التنازلية من الأفضل؟
تستخدم على الأكثر 11/9 من أقل عدد من الصناديق زائد 6/9 صندوق، وهو حد أثبت György Dósa عام 2007 أنه دقيق تمامًا. وعلى المدخلات المعتادة تكون عادةً مثلى أو تزيد بصندوق واحد.
هل تعبئة الصناديق هي نفسها مسألة حقيبة الظهر؟
هما مرتبطتان لكنهما مختلفتان. في مسألة حقيبة الظهر تُملأ حقيبة واحدة بأثمن العناصر؛ وفي تعبئة الصناديق يوضع كل عنصر في أقل عدد ممكن من الحقائب. وكثيرًا ما تعمل البرامج الدقيقة لحل تعبئة الصناديق بحل مسائل شبيهة بمسألة حقيبة الظهر مرة بعد مرة.
لماذا لا يسمح التطبيق إلا بـ 12 عنصرًا؟
لأن الإجابة الدقيقة تفحص كل مجموعة من العناصر، و12 عنصرًا تعطي بالفعل 4096 مجموعة. القواعد السريعة يمكنها التعامل مع آلاف العناصر، لكن الرسم والمقارنة بالإجابة الدقيقة لا يمكنهما ذلك.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب تعبئة الصناديق