مشكلة نابساك

مشكلة الحقيبة (نابساك) أو (راكساك)؛ هي مشكلة تحدث في عملية التحسين التوافقي. حيث يتواجد عدد من المواد، لكلٍّ وزنها وقيمتها. المطلوب هو تحديد العدد المتضمن في المجموعة من كل مادة بحيث يكون إجمالي الوزن أقل من أو مساوٍ للحد المطلوب، وتبلغ القيمة الإجمالية أكبر قدر ممكن. تستمد المشكلة اسمها من العقبة التي يواجهها الشخص عند تقييده بحقيبة ذات حجم ثابت عليه ملؤها بالمواد ذات القيمة الأعلى.

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

وقد تمت دراسة مشكلة الحقيبة (نابساك) لأكثر من قرن، مع الأعمال المبكرة التي يرجع تاريخها إلى عام 1897 للميلاد. ويعود اسمها إلى الأعمال المبكرة لعالم الرياضيات توبياس دانتزغ (1884-1956). وتشير المشكلة إلى المشكلة الشائعة المتعلقة بحزم المواد الأكثر قيمة وفائدة دون التسبب بإثقال الأمتعة.

التطبيقات

أثبتت دراسة سجل الخوارزميات في جامعة ستوني بروك التي أجريت عام 1998 أنه من أصل 75 مشكلة حسابية، احتلت (النابساك) المرتبة الثامنة عشر كأكثر المشاكل شعبية والرابعة من حيث الأكثر حاجة بعد الkd-trees ومشكلة التعبئة بن.

تظهر مشكلة الحقيبة (النابساك) في عملية صناعة القرار على ارض الواقع في كافة المجالات، مثل ايجاد الطريقة الأقل تكلفة لقطع المواد الخام، واختيار الاستثمارات والقضايا، والتوريق المالي للأصول المدعومة، وتوليد المفاتيح لميركيل-هيلمان، وغيرها من نظم الترميز باستخدام النابساك.

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

التعريف

المشكلة الأكثر شيوعا التي يتم حلها هي مشكلة نابساك 0-1، التي يتم فيها ترقيم عدد (xi) من النسخ من كل نوع ب 0أو 1. مع إعطاء مجموعة من المواد أرقاماً من 1إلى (n). كلٌ له وزنه (wi) وقيمته (vi)، بالإضافة إلى الحد الأقصى لسعة الوزن (W)،

maximize

subject to and .

نلاحظ أن (xi) تمثل عدد حالات وضع المادة (i) في الحقيبة. والمشكلة هي تحقيق أقصى قدر ممكن من مجموع قيم المواد الموجودة في الحقيبة، بحيث يكون مجموع الأوزان أقل من أو يساوي قدرة الحقيبة.

تزيل مشكلة الحقيبة المحدودة (BKP) القيد المتمثل بوجود قطعة واحدة من كل مادة، إلا أنها تحد العدد (xi) من النسخ لكل نوع من المواد بعدد صحيح ( )

maximize

subject to and

لا تضع مشكلة الحقيبة غير المحدودة حد أعلى لعدد النسخ من كل نوع من المواد. ويمكن صياغتها على النحو الوارد أعلاه، باستثناء أن القيد الوحيد على (xi)هو أنه عدد صحيح غير سالب.

Maximize

subject to and

هناك مثال على مشكلة الحقيبة غير المحدودة موضَّح من خلال الشكل المرفق في بداية هذه المقالة مع تسميته التوضيحية.

التعقيد الحسابي

تعتبر مشكلة الحقيبة (نابساك) مثيرة للاهتمام من وجهة نظر علم الحاسوب لأسباب عديدة

• إن قرار أخذ المادة أو عدمه يتم حسابه بصيغة متعدد الحدود؛ لذلك لا يوجد أي خوارزمية معروفة صحيحة وسريعة (بوقت متعدد الحدود) لكل الحالات.

• باعتبار أن مشكلة اتخاذ القرار تعتبر متعدد حدود كامل، فإن عملية تحسين حل المشكلة تعد غير محدودة بمتعدد الحدود، ووضوحها لا يقل صعوبة عن مشكلة اتخاذ القرار، ولا يوجد أي خوارزمية متعددة الحدود تستطيع تحديد ذلك عن طريق تقديم حل، حتى لو كان مثاليا (الذي قد يعني أنه لا يوجد حل باستخدام قيمة أعلى، وبذلك حل مشكلة اتخاذ القرار متعددة الحدود).

• هناك خوارزمية شبه متعددة الحدود باستخدام البرمجة الديناميكية.

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

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

الحل

• مشكلة نابساك 0-1

إن حل مشكلة نابساك 0-1 يكمن في الوقت شبه متعدد الحدود. لنفترض أن هي مجموعة أعداد صحيحة موجبة، حدد لتكون أعلى قيمة يمكن الحصول عليها مع مراعاة أن يكون الوزن أقل من أو يساوي باستخدام مواد قد يصل عددها إلى .

بإمكاننا تحديد بشكا متكرر على النحو التالي

•

• if (تساوي المادة الجديدة أكثر من حد الوزن الحالي)

• if .

من الممكن إيجاد الحل عن طريق حساب . للقيام بذلك بكفاءة يمكننا استخدام جدول لتخزين العمليات الحسابية السابقة.

فيما يلي توضح البرمجية المبدئية للبرنامج الديناميكي

1. // Input

2. // Values (stored in array v)

3. // Weights (stored in array w)

4. // Number of distinct it s (n)

5. // Knapsack capacity (W)

6.

7. for j from 0 to W do

8. m[0, j] 0

9.

10. for i from 1 to n do

11. for j from 0 to W do

12. if w[i-1] > j then
13. m[i, j] m[i-1, j]

14. else

15. m[i, j] max(m[i-1, j], m[i-1, j-w[i-1 + v[i-1])

فإذن سيطبق هذا الحل في وقت ومساحة . بالإضافة إلى ذلك، إذا لم نستخدم سوى مجموعة أحادية الأبعاد لتخزين القيم المثلى الحالية والمرور على هذه المجموعة i+1 مرات، وإعادة الكتابة من ألى كل مرة، فإننا سنحصل على ذات النتيجة لمساحة فقط.

شريط بوابات برمجة الحاسوب معلوماتية رياضيات

تصنيف أبحاث العمليات

تصنيف استمثال توافقي

تصنيف بحوث عمليات

تصنيف برمجة خطية

تصنيف برمجة ديناميكية

تصنيف تعمية

تصنيف خوارزم

تصنيف مسائل NP كاملة