مرجع
آخر الزيارات

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

186 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: خوارزمية الـ (Next-Fit) هي خوارزمية من خوارزميات الـ (Online) وتستعمل لحل مسألة تعبئة الصناديق (Bin Packing Problem) والتي تهدف إلى تعبئة عناصر مختلفة الحجم في صناديق متساوية السعة، بحيث نستعمل أقل عدد ممكن من الصناديق .

في البداية، خوارزمية الـ (Next-Fit) هي خوارزمية من خوارزميات الـ (Online) وتستعمل لحل مسألة تعبئة الصناديق (Bin Packing Problem) والتي تهدف إلى تعبئة عناصر مختلفة الحجم في صناديق متساوية السعة، بحيث نستعمل أقل عدد ممكن من الصناديق .

إ‌)  فإذا كانت المساحة كافية، بضعناه في الصندوق .

علاوةً على ذلك، مدخلات الخوارزمية هي قائمة العناصر ذات الأحجام المختلفة، بمخرجاتها هي توزيع تلك العناصر على الصناديق ذات السعة الثابتة، بحيث يكون مجموع حجم العناصر المخزنة في أي صندوق لا تتجاوز سعتة، بكن هذه المسألة من النوع الـ (NP-hard) . وتتلخص خطوات الخوارزمية في الآتي :

ومن جهة أخرى، ب‌) وإن كانت المساحة غير كافية، بغلقنا الصندوة، بفتحنا صندوقاً جديداً ووضعناه فيه .

3) يتم تكرار هذه العملية لكل العناصر .

1) يتم تحديد صندوق أولي فارغ لتخزين العناصر .

كذلك، هذه الخوارزمية تعتبر خوارزمية ذات مساحة محدودة، بمعنى أنها تتطلب أن يكون هناك فقط صندوقاً واحداً مفتوحاً في أي وقت من تنفيذهة، بقد وضعت هذه الخوارزمية من قبل (David S. Johnson) في رسالته للدكتوراه عام 1973 في معهد ماساتشوستس للتقنية (MIT) .

من جهة ثانية، 2) عند وصول عنصر ما من القائمة، بقوم بفحص حجم العنصة، بمدى ملائمته للمساحة المتبقية من الصندوق الذي تم تحديده في الخطوة (1) :

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.