مسألة حقيبة الظهر

مسألة حقيبة الظهر هي مسألة تدخل في إطار الاستمثال التوافقي.[1][2][3] فإذا كانت لدينا مجموعة من العناصر، لكل منها وزن و قيمة، فعليك أن تحدد العناصر التي تُدرج في الحقيبة، بحيث يكون مجموع أوزانها أقل من أو يساوي قدراً معيناً، وأن يكون مجموع القيم أعلى ما يكون. اسم هذه المسألة مأخوذ من حالة شخص ما لديه حقيبة ذات حجم محدد، وعليه أن يعبئها بالعناصر الأعلى قيمةً.

Knapsack.svg

تم تناول هذه المسألة منذ أكثر من قرن، وليس من المعروف كيف نشأ تعبير (مسألة حقيبة الظهر)، رغم أنه تم ذكرها في أعمال العالم الرياضي توبياس دانزج (1844-1956)، وهو من اقترح أن الاسم ربما قد يكون نشأ في التراث الشعبي قبل أن تتم نمذجة المسألة رياضياً.

التطبيقاتعدل

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

من أقدم تطبيقات هذه المسألة هو إنشاء وتقييم الامتحانات ذات الأسئلة الاختيارية. في هذه الامتحانات يمكن للطالب أن يختار أي مجموعة من الأسئلة يريد إجابتها، وبحيث يستهدف الحصول على الدرجة النهائية. فمثلاً في حالة كون الامتحان محتوياً على 12 سؤالاً، لكل منها 10 درجات، يسهل على الطالب معرفة أنه يحتاج لإجابة 10 أسئلة فقط للحصول على الدرجة النهائية (100 درجة). لكن لو احتوى الامتحان على أسئلة ذات درجات متفاوتة، لأصبح الاختيار أصعب، ولاحتاج الأمر لخوارزم (مسألة حقيبة الظهر) لتحديد مجموعة الأسئلة التي يمكن للطالب أن يجيبها ليحصل على الدرجة النهائية.

انظر أيضاعدل

مراجععدل

  1. ^ Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Unbounded Knapsack Problem : dynamic programming revisited". European Journal of Operational Research. 123 (2): 168–181. doi:10.1016/S0377-2217(99)00265-9. مؤرشف من الأصل في 29 يناير 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. ^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "The Multiple Subset Sum Problem". SIAM J. on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. مؤرشف من الأصل في 21 يوليو 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. ^ "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes". in Proc. IEEE INFOCOM’14, 2427–2435. نسخة محفوظة 09 أغسطس 2017 على موقع واي باك مشين.


 
هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال، بحاجة للتوسيع. شارك في تحريرها.