رياضيات أعمال فصل أول

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

إذا كان لديَّ n من العُلَب التي لها المقطع العرضي نفسه (مستطيل عرضه x، وطوله y)، لكنَّ ارتفاعاتها مُتفاوِتة كما يظهر في الشكل التالي، وأردت تعبئتها في صناديق، عرض كلٍّ منها ،x وطول كلٍّ منها y، وارتفاعاتها مُتساوِية، فكيف يُمكِنني فعل ذلك باستعمال أقل عدد مُمكِن من الصناديق؟

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

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

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

 

مثال:

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

$5 7 3 5 6 2 4 4 7 4$

الخطوة 1: أجد مجموع ارتفاعات العُلَب.

$5+7+3+5+6+2+4+4+7+4=47$

الخطوة 2: أَقسِم مجموع ارتفاعات العُلَب على ارتفاع الصندوق الواحد.

$\frac{47}{10}=4.7\approx 5$

إذن، الحدُّ الأدنى من عدد الصناديق اللازمة لتعبئة العُلَب هو 5 صناديق.

 

خوارزمية المُلاءَمة الأولى

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

يُمكِن حلُّ مسائل تعبئة الصندوق باستعمال خوارزمية المُلاءَمة الأولى، وذلك باتِّباع الخطوات الآتية:

1 إيجاد الحدِّ الأدنى من عدد الصناديق اللازمة.

2 اتِّباع ترتيب العناصر (العُلَب) المُعطى في المسألة.

3 وضع كل عنصر في أوَّل صندوق مُتوافِر يَتَّسِع له، بَدْءًا بالصندوق الأوَّل في كل مَرَّة.

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

 

مثال:

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

$0.8 0.6 0.5 0.7 0.9 0.4 0.3 0.6 0.5 0.6$

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

الخطوة 1: أجد الحدَّ الأدنى من عدد الصناديق اللازمة لتعبئة العُلَب.

$0.8+0.6+0.5+0.7+0.9+0.4+0.3+0.6+0.5+0.6=5.9$

$\frac{5.9}{1.5}=3.9\overline{3}\approx 4$

الخطوة 2: أضع كل عُلْبة في أوَّل صندوق مُتوافِر يَتَّسِع لها، بَدْءًا بالصندوق الأوَّل في كل مَرَّة، وأَلتزِم ترتيب العناصر في المسألة.

2) هل توصَّلْتُ إلى الحلِّ الأمثل لهذه المسألة؟ أُبرِّر إجابتي.

لا؛ لأنَّ عدد الصناديق المُستعمَلة في هذا الحلِّ يزيد على الحدِّ الأدنى من عدد الصناديق اللازمة.

 

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

لإيجاد الارتفاع المهدور في الصناديق جميعها، أُحدِّد أوَّلًًا الارتفاع المهدور في كل صندوق، ثمَّ أجمع قِيَم الارتفاعات المهدورة جميعها:

---

خوارزمية المُلاءَمة الأولى المُتناقِصة

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

 

مثال:

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

$0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3$

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

الخطوة 1: أجد الحدَّ الأدنى من عدد الصناديق اللازمة لتعبئة العُلَب.

$0.6+1.5+1.6+0.2+0.4+0.5+0.7+0.1+0.9+0.3=6.8$

$\frac{6.8}{2}=3.4\approx 4$ بتقريب الناتج إلى الأعلى.

الخطوة 2: أُرتِّب ارتفاعات العُلَب ترتيبًا تنازليًّا.

$1.6 1.5 0.9 0.7 0.6 0.5 0.4 0.3 0.2 0.1$

الخطوة 3: أُطبِّق خوارزمية المُلاءَمة الأولى على ارتفاعات العُلَب التي أُعيد ترتيب مقاساتها.

إذن، عدد الصناديق اللازمة لتعبئة العُلَب باستعمال المُلاءَمة الأولى المُتناقِصة هو 4 صناديق.

 

2) هل توصَّلْتُ إلى الحلِّ الأمثل لهذه المسألة؟ أُبرِّر إجابتي.

نعم؛ لأنَّ عدد الصناديق المُستعمَلة في هذا الحلِّ مُساوٍ للحدِّ الأدنى من عدد الصناديق اللازمة.

 

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

أُلاحِظ عدم وجود ارتفاعات مهدورة إلّّا في الصندوق الأخير، وهو ارتفاع يساوي 1.2 وحدة طول.

 

خوارزمية الصندوق الكامل

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

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

 

مثال:

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

$3 4 5.2 4.4 4.3 5.6 4.6 4.7 3.2 4.8 5.3 4.1$

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

الخطوة 1: أجد الحدَّ الأدنى من عدد الصناديق اللازمة لتعبئة العُلَب.

$3+4+5.2+4.4+4.3+5.6+4.6+4.7+3.2+4.8+5.3+4.1=53.2$

$\frac{53.2}{17}=3.129\approx 4$ بتقريب الناتج إلى الأعلى.

 

الخطوة 2: أُطبِّق خوارزمية الصندوق الكامل.

2) هل توصَّلْتُ إلى الحلِّ الأمثل لهذه المسألة؟ أُبرِّر إجابتي.

نعم؛ لأنَّ عدد الصناديق المُستعمَلة في هذا الحلِّ مُساوٍ للحدِّ الأدنى من عدد الصناديق اللازمة.