خوارزميات تعبئة الصندوق

• تعرُّف خوارزميات تعبئة الصندوق، واستعمالها لإيجاد الحل الأمثل لمسألة تعبئة.

كيف نملأ الصناديق بأقل عدد ممكن؟

يرغب مُدَرِّب في صالة رياضية أن يُرَتِّب على رفوف الأثقال المُبَيَّنة كتلتها (بالكيلوغرام) في ما يلي الكتل بالكيلوغرام: $18\ 16\ 24\ 16\ 20\ 10\ 12\ 8$ $16\ 12\ 10\ 4\ 12\ 6\ 13$ علمًا بأنه يُمكن لكل رف منها أن يحمل $40\ \text{kg}$ في الحد الأقصى. كيف يُمكن للمُدَرِّب أن يُرَتِّب الأثقال باستعمال أقل عدد من الرفوف؟

• المسألة: عندي $n$ من العُلَب لها المقطع العرضي نفسه، لكنَّ ارتفاعاتها مُتفاوتة.
• المطلوب: تعبئتها في صناديق ارتفاعاتها مُتساوية باستعمال أقل عدد مُمكن من الصناديق.

• الشحن: تنظيم صناديق البضائع وترتيبها داخل حاويات الشحن.
• الشاحنات: تحميل البضائع في شاحنات عليها قيود في الكتلة.
• التخزين: تخزين ملفات بيانات مختلفة الحجوم في عدد من الأقراص المُدَمجة.
• الخطوة الأولى: إيجاد الحد الأدنى من عدد الصناديق اللازمة.

1. اجمع المقاسات.: اجمع مقاسات العناصر جميعها.
2. اقسم.: اقسم المجموع على مقاس الصندوق الواحد.
3. قرِّب إلى الأعلى.: قرِّب الناتج إلى الأعلى؛ فهذا هو الحد الأدنى لعدد الصناديق.

لماذا يُقَرَّب الناتج إلى الأعلى؟ أُبَرِّر إجابتي.

يُراد تعبئة العُلَب (المُعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاعُ كلٍّ منها وحدة طول واحدة، علمًا بأنَّ للعُلَب والصناديق المقطع العرضي نفسه.

ارتفاعات العُلَب: $0.5\ 0.7\ 0.5\ 0.2\ 0.4\ 0.2\ 0.5\ 0.1\ 0.6$ أجد الحدَّ الأدنى من عدد الصناديق اللازمة لتعبئة العُلَب.

الملاءمة الأولى: ضع كل عنصر في أول صندوق يتسع له

• الفكرة: من خوارزميات حل مسألة تعبئة الصندوق خوارزمية الملاءمة الأولى ⁦(first-fit algorithm)⁩.

1. إيجاد الحد الأدنى من عدد الصناديق اللازمة.
2. اتباع ترتيب العناصر (العُلَب) المُعطى في المسألة.
3. وضع كل عنصر في أوّل صندوق مُتوافر يتّسع له، بدءًا بالصندوق الأوّل في كل مرّة.
4. في حال لم يتّسع أي صندوق للعنصر الذي يُراد وضعه، فإنّه يجب إضافة صندوق آخر.

• أُلاحظ من الشكل أنّ ارتفاع العُلَب في أيّ من الصناديق لم يتجاوز $1.5$ وحدة طول.

يُراد تعبئة العُلَب (المُعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها $20$ وحدة طول.

ارتفاعات العُلَب: $11\ 2\ 15\ 5\ 6\ 17\ 7$

⁦a)⁩ أستعمل خوارزمية الملاءمة الأولى لتعبئة العُلَب في الصناديق، ثمّ أُحدّد عدد الصناديق اللازمة لذلك.

⁦b)⁩ هل توصّلتُ إلى الحل الأمثل لهذه المسألة؟ أُبرّر إجابتي.

⁦c)⁩ أجد الارتفاع المهدور في الصناديق جميعها.

الملاءمة الأولى المتناقصة: رتِّب ثم عبِّئ

• الفكرة: خوارزمية الملاءمة الأولى المتناقصة ⁦(first-fit decreasing algorithm)⁩ تبدأ بترتيب مقاسات العناصر المُعطاة ترتيبًا تنازليًا.
• ثمّ تُطبَّق خوارزمية الملاءمة الأولى لتعبئة العناصر في الصناديق.

1. ترتيب مقاسات العناصر تنازليًا.
2. تطبيق خوارزمية الملاءمة الأولى على العناصر التي أُعيد ترتيب مقاساتها.

أحلُّ المثال 3 باستعمال خوارزمية الملاءمة الأولى، ثمَّ أقارن بين الحلَّين.

أستعمل خوارزمية الملاءمة الأولى المُتناقصة لإعادة حلِّ المسألة الواردة في المثال 2، وأحدِّد إذا كان الحلُّ الناتج هو الحلُّ الأمثل أم لا.

وأجد مجموع الارتفاعات المهدورة في الصناديق جميعها، ثمَّ أقارن الحلَّ الذي توصَّلتُ إليه بالحلِّ الناتج باستعمال خوارزمية الملاءمة الأولى.

الصندوق الكامل: املأ الصناديق الممتلئة أولًا

• الفرق: الخوارزميتان السابقتان تشترطان التزام الترتيب المُعطى أو الترتيب التنازلي لمقاسات العناصر.
• الثالثة يُمكن استعمالها من دون الالتزام بأيِّ ترتيب لمقاسات العناصر: خوارزمية الصندوق الكامل ⁦(full-bin packing algorithm)⁩.

1. إيجاد الحدِّ الأدنى من عدد الصناديق اللازمة.
2. البحث عن العناصر التي يُمكن أن تملأ صندوقًا كاملًا، ثمَّ تعبئتها أوَّلًا.
3. تطبيق خوارزمية الملاءمة الأولى على العناصر المُتبقية.

أستعمل خوارزمية الصندوق الكامل لإعادة حلِّ المسألة الواردة في المثال 3، وأُحدِّد إذا كان الحلُّ الناتج هو الحلُّ الأمثل أم لا.

ثمَّ أُقارن الحلَّ الذي توصَّلتُ إليه بالحلِّ الناتج باستعمال خوارزمية الملاءمة الأولى المُتناقصة.

قارن بين الخوارزميات الثلاث

• يُمكن توظيف خوارزميات التعبئة في العديد من التطبيقات الحياتية التي تهدف إلى تقليص أكبر قَدْر من الهدر في المساحات والأطوال.

من الحياة: قصّ القماش وحفظ الملفات

تخزين البيانات: سعات 9 ملفات حاسوبية (بالجيجابيت) يُراد حفظها في أقراص تخزين، سعة كلّ منها $100$ جيجابيت.

السعات بالجيجابيت: $29\ 52\ 73\ 87\ 74\ 47\ 38\ 61\ 41$

⁦a)⁩ أجد الحدّ الأدنى من عدد أقراص التخزين اللازمة لحفظ الملفات.

⁦b)⁩ أُحدّد كيف تُحفظ الملفات في الأقراص باستعمال خوارزمية الملاءمة الأولى المتناقصة، ثمّ أُحدّد عدد الأقراص اللازمة لذلك باستعمال هذه الخوارزمية، ثمّ أجد مساحة التخزين المهدورة في الأقراص.

⁦d)⁩ أيّ الخوارزميتين توصّلتُ بها إلى الحلّ الأمثل؟ أُبرّر إجابتي.

تدرَّب على الخوارزميات الثلاث

ارتفاع كلّ صندوق $5$ وحدات طول؛ للعُلَب والصناديق المقطع العرضي نفسه.

ارتفاعات العُلَب: $1.8\ 1.4\ 2.6\ 1.6\ 2.8\ 0.9\ 3.1\ 0.8\ 1.2\ 2.4\ 0.6$ 1. أستعمل خوارزمية الملاءمة الأولى لتعبئة العُلَب في الصناديق، ثمّ أُحدّد عدد الصناديق اللازمة لذلك.

2. هل الحلّ الناتج في السؤال السابق هو الحلّ الأمثل لهذه المسألة؟ أُبرّر إجابتي.

3. أجد الارتفاع المهدور في الصناديق جميعها.

ارتفاع كلّ صندوق $60$ وحدة طول؛ للعُلَب والصناديق المقطع العرضي نفسه.

ارتفاعات العُلَب: $31\ 10\ 38\ 45\ 19\ 47\ 35\ 28\ 12$ 4. أستعمل خوارزمية الملاءمة الأولى المتناقصة لتعبئة العُلَب في الصناديق، ثمّ أُحدّد عدد الصناديق اللازمة لذلك.

5. هل الحلّ الناتج في السؤال السابق هو الحلّ الأمثل لهذه المسألة؟ أُبرّر إجابتي.

6. أجد الارتفاع المهدور في الصناديق جميعها.

ارتفاع كلّ صندوق $65$ وحدة طول؛ للعُلَب والصناديق المقطع العرضي نفسه.

ارتفاعات العُلَب: $42\ 21\ 15\ 16\ 35\ 10\ 31\ 11\ 27\ 39$ 7. أستعمل خوارزمية الصندوق الكامل لتعبئة العُلَب في الصناديق، ثمّ أُحدّد عدد الصناديق اللازمة لذلك.

8. هل الحلّ الناتج في السؤال السابق هو الحلّ الأمثل لهذه المسألة؟ أُبرّر إجابتي.

9. أجد الارتفاع المهدور في الصناديق جميعها.

شحن: كتل 7 أجهزة بالكيلوغرام يُراد شحنها في صناديق، على ألا تتجاوز كتلة الصندوق الواحد $60\ \text{kg}$.

الكتل: $41\ 28\ 42\ 31\ 36\ 32\ 29$ 10. أجد الحدّ الأدنى من عدد الصناديق اللازمة لشحن الأجهزة.

11. أُحدّد كيف تُوزّع الأجهزة على الصناديق باستعمال خوارزمية الملاءمة الأولى، ثمّ أُحدّد عدد الصناديق اللازمة لذلك باستعمال هذه الخوارزمية.

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

14. أيّ الخوارزميات توصّلتُ بها إلى الحلّ الأمثل؟ أُبرّر إجابتي.

أسلاك نحاسية: أطوال 10 قطع بالسنتيمتر يُراد قصّها من أسلاك نحاسية، طول كلّ منها $1\ \text{m}$.

الأطوال بالسنتيمتر: $58\ 45\ 18\ 55\ 47\ 12\ 63\ 30\ 19\ 42$ 15. أُحدّد كيف تُقصّ القطع باستعمال خوارزمية الملاءمة الأولى، ثمّ أُحدّد عدد الأسلاك اللازمة لذلك باستعمال هذه الخوارزمية، ثمّ أجد طول الجزء المهدور من الأسلاك جميعها.

18. أيّ الخوارزميات توصّلتُ بها إلى الحلّ الأمثل؟ أُبرّر إجابتي.

أثقال: أعود إلى المسألة الواردة في بند (مسألة اليوم)، ثمّ أجيب عن الأسئلة الآتية تباعًا:

يُمكن لكل رف أن يحمل $40\ \text{kg}$ في الحد الأقصى.

الكتل بالكيلوغرام: $18\ 16\ 24\ 16\ 20\ 10\ 12\ 8$ $16\ 12\ 10\ 4\ 12\ 6\ 13$ 19. أُحدّد كيف تُرَتَّب الأثقال على الرفوف باستعمال خوارزمية الملاءمة الأولى، ثمّ أُحدّد عدد الرفوف اللازمة لذلك باستعمال هذه الخوارزمية.

20. أُحدّد كيف تُرَتَّب الأثقال على الرفوف باستعمال خوارزمية الصندوق الكامل، ثمّ أُحدّد عدد الرفوف اللازمة لذلك باستعمال هذه الخوارزمية.

مهارات التفكير العليا: الأخشاب والحقائب

تبرير: أطوال 8 قطع خشبية (بالسنتيمتر) تلزم لصنع خزانة صغيرة، ويُراد قَصُّها من ألواح خشبية.

الأطوال بالسنتيمتر: $20\ 35\ 50\ 60\ 20\ 70\ 75\ 20$ 21. تتوافر ألواح خشبية، طول كلّ منها $1\ \text{m}$، وسعرها $3\ \text{JD}$.

أستعمل خوارزمية المُلائمة الأولى المُتناقصة لتحديد كيف تُقَصُّ القطع الخشبية من الألواح، ثمَّ أجد التكلفة الكلية لصنع الخزانة.

ثمَّ أحسب الكمية المهدورة من الخشب.

23. أيُّ الخوارزميتين يُمكن استعمالها لصنع الخزانة بتكلفة أقل؟ أُبرر إجابتي.

24. ما أقل تكلفة لصنع الخزانة إذا أمكن استعمال الألواح التي طولها $1\ \text{m}$ والألواح التي طولها $1.5\ \text{m}$ معًا؟ أُبرِّر إجابتي.

تحدٍّ: كتل 9 حقائب سفر (إلى أقرب كيلوغرام) يُراد نقلها في حاويات، ويُمكن لكلٍّ منها أن تحمل كتلة إجمالية أقصاها $50\ \text{kg}$.

الكتل بالكيلوغرام: $24\ 14\ 8\ x\ 19\ 25\ 6\ 17\ 9$ إذا علمتُ أنَّ كتلة إحدى الحقائب لم تُقَسْ قياسًا دقيقًا، ولتكن ⁦x⁩ كيلوغرامًا، حيث: 23 ≥ ⁦x⁩ > 19 25. أحدّد كيف تُوزَّع الحقائب على الحاويات باستعمال خوارزمية المُلائمة الأولى.

26. أحدّد الطريقتين المُمكِنتين لتوزيع الحقائب على الحاويات باستعمال خوارزمية المُلائمة الأولى المُتناقصة.

27. أحدّد القيمة (القيم) المُمكِنة للمتغير ⁦x⁩ في كلّ من الطريقتين المُشار إليهما في السؤال السابق بعد توزيع الحقائب باستعمال خوارزمية المُلائمة الأولى المُتناقصة.