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