ما هي مشكلة تعبئة الحاويات (Bin Packing Problem)؟ شرح مبسّط مع الخوارزميات

مشكلة تعبئة الحاويات (Bin Packing Problem) هي مسألة تحسين في علوم الحاسوب هدفها بسيط في ظاهره: لديك مجموعة من العناصر بأحجام مختلفة، وحاويات (bins) متطابقة سعة كل منها ثابتة، والمطلوب توزيع كل العناصر داخل الحاويات باستخدام أقل عدد ممكن منها، بشرط ألّا يتجاوز مجموع أحجام العناصر داخل أي حاوية سعتها. تبدو المسألة عادية، لكنها في الحقيقة من المسائل التي يصعب حلها بشكل أمثل عندما يكبر عدد العناصر، ولهذا صارت من الأمثلة الكلاسيكية في تدريس الخوارزميات ونظرية التعقيد.

الفكرة عبر مثال ملموس

تخيّل أن سعة كل حاوية = 10، ولديك العناصر التالية بالأحجام: 6، 5، 4، 3، 2.

• لو وضعت 6 مع 4 في حاوية، صارت ممتلئة تمامًا (10).
• ثم 5 مع 3 مع 2 في حاوية ثانية (المجموع 10).

النتيجة: حاويتان فقط، وهو الحل الأمثل هنا. لكن لو وزّعتها بترتيب أعشوائي قد تحتاج ثلاث حاويات أو أكثر. جوهر المشكلة إذن هو الترتيب والاختيار: أي عنصر يذهب إلى أي حاوية حتى نقلّل الفراغ المهدور.

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

لماذا تُعد مشكلة صعبة؟

مشكلة تعبئة الحاويات مصنّفة على أنها NP-hard. عمليًا هذا يعني أنه لا توجد خوارزمية معروفة تصل إلى الحل الأمثل دائمًا خلال زمن معقول عندما يكبر عدد العناصر؛ فعدد الطرق الممكنة لتوزيع العناصر ينفجر بشكل هائل مع كل عنصر إضافي.

لهذا السبب ينقسم التعامل معها إلى مسارين:

1. الحلول المثلى (Exact): مثل البرمجة الخطية الصحيحة (Integer Linear Programming) أو خوارزميات التفريع والتقييد (Branch and Bound). تعطي أفضل نتيجة ممكنة لكنها بطيئة جدًا وغير عملية على مدخلات كبيرة.
2. الحلول التقريبية (Approximation / Heuristics): سريعة وسهلة التنفيذ، تعطي نتيجة قريبة من الأمثل لكنها لا تضمنه دائمًا. وهي الأكثر استخدامًا في التطبيقات الحقيقية.

أشهر الخوارزميات التقريبية

معظم الخوارزميات العملية تعالج العناصر واحدًا تلو الآخر (online أو offline) وتقرر أين تضع كل عنصر:

1. First-Fit: ضع العنصر في أول حاوية تتّسع له. إن لم تتّسع أي حاوية مفتوحة، افتح حاوية جديدة.
2. Best-Fit: ضع العنصر في الحاوية التي ستترك أقل فراغ متبقٍ بعد إضافته، أي «أضيق» حاوية مناسبة.
3. Worst-Fit: العكس — ضعه في الحاوية ذات أكبر فراغ متبقٍ، لإبقاء الحاويات متوازنة.
4. First-Fit Decreasing (FFD): رتّب العناصر تنازليًا من الأكبر إلى الأصغر أولًا، ثم طبّق First-Fit. هذه الخطوة الصغيرة تحسّن النتيجة بشكل ملحوظ، لأن العناصر الكبيرة تُوضع أولًا وتُملأ الفجوات لاحقًا بالعناصر الصغيرة.

جدول مقارنة سريع

الخوارزمية	الفكرة	جودة الحل	ملاحظة
First-Fit	أول حاوية مناسبة	جيدة	سريعة وبسيطة التنفيذ
Best-Fit	أضيق حاوية مناسبة	أفضل قليلًا من First-Fit غالبًا	تحتاج تتبّع الفراغات
Worst-Fit	أوسع حاوية مناسبة	متوسطة	مفيدة للتوازن لا للضغط
First-Fit Decreasing	ترتيب تنازلي ثم First-Fit	الأفضل عمليًا بين الأربع	يتطلب معرفة كل العناصر مسبقًا

القاعدة العملية: إن كانت كل العناصر معروفة مسبقًا (حالة offline)، فابدأ بـ First-Fit Decreasing — فهو غالبًا أقرب خيار للأمثل بأقل جهد. أما إذا وصلت العناصر تباعًا ولا تعرف القادم (حالة online)، فـ First-Fit أو Best-Fit هما الخياران المنطقيان.

أنواع المشكلة

• أحادية البعد: التوزيع حسب قيمة واحدة (وزن، طول، حجم رقمي). هذه الصورة الأشهر.
• متعددة الأبعاد: كل عنصر له أكثر من قيد في آن واحد (طول وعرض وارتفاع مثلًا)، كما في تعبئة صناديق فعلية، وهي أصعب بكثير.
• متغيرة الحجم (Variable-Sized): الحاويات المتاحة ليست متطابقة، بل بأحجام أو تكاليف مختلفة، والهدف تقليل التكلفة لا مجرد العدد.

نصيحة عملية وخطأ شائع

الخطأ الشائع هو الحكم على خوارزمية بأنها «الأفضل دائمًا». لا توجد خوارزمية تفوز في كل الحالات؛ الأداء يعتمد على توزيع أحجام العناصر. نصيحة من التطبيق: عند بناء حل حقيقي، لا تكتفِ بخوارزمية واحدة — شغّل عدة خوارزميات على نفس البيانات (First-Fit، Best-Fit، FFD) واختر أفضل نتيجة، فالكلفة الحسابية للمقارنة زهيدة مقابل توفير حاوية أو خادم كامل. وتذكّر أن ترتيب العناصر تنازليًا قبل التوزيع هو أرخص تحسين يمكنك الحصول عليه تقريبًا.

الأسئلة الشائعة

هل مشكلة Bin Packing نفسها مشكلة Knapsack؟ لا. في مشكلة الحقيبة (Knapsack) لديك حاوية واحدة وتختار مجموعة فرعية من العناصر لتعظيم قيمة معينة. في Bin Packing يجب وضع كل العناصر وتقليل عدد الحاويات. المسألتان متقاربتان لكنهما مختلفتان في الهدف.

ما الفرق بين النسخة online والنسخة offline؟ في offline تعرف كل العناصر مسبقًا فيمكنك ترتيبها (مثل FFD). في online تصل العناصر واحدًا تلو الآخر ويجب اتخاذ القرار فورًا دون معرفة ما سيأتي، وهو أصعب وتكون نتائجه عادة أقل جودة.

ما درجة قرب الحلول التقريبية من الأمثل؟ خوارزمية مثل First-Fit Decreasing تعطي نتيجة قريبة جدًا من الأمثل في الحالات العملية، وغالبًا لا تتجاوز عدد الحاويات المثالي إلا بنسبة صغيرة، وهو ما يكفي لمعظم التطبيقات.

أين أصادف هذه المشكلة في الواقع؟ في اللوجستيات (تحميل الشحنات)، وفي الحوسبة السحابية (توزيع الأحمال على الخوادم الافتراضية)، وفي تصنيع المواد (تقطيع بأقل هدر)، وحتى في تنظيم ملفات على أقراص تخزين محدودة السعة.