مسألة مجموع المجموعات الجزئية

تُعدّ مسألة مجموع المجموعات الجزئية ( SSP ) مسألة قرار في علوم الحاسوب . في صيغتها الأكثر عمومية، توجد مجموعة متعددة $S$ من الأعداد الصحيحة ومجموع مستهدف $T$ والسؤال هو تحديد ما إذا كان مجموع أي مجموعة جزئية من الأعداد الصحيحة يساوي بالضبط $T$ ^{[ 1 ]} من المعروف أن هذه المسألة من فئة NP-complete . علاوة على ذلك ، فإن بعض المتغيرات المقيدة منها هي أيضًا من فئة NP-complete، على سبيل المثال: ^{[ 1 ]}

المتغير الذي تكون فيه جميع المدخلات موجبة.
المتغير الذي قد تكون فيه المدخلات موجبة أو سالبة، و $T=0$ على سبيل المثال، بالنظر إلى المجموعة $\{-7,-3,-2,9000,5,8\}$ نعم، الإجابة هي نعم لأن المجموعة الفرعية $\{-3,-2,5\}$ المجموع يساوي صفرًا.
المتغير الذي تكون فيه جميع المدخلات موجبة، ويكون مجموع الهدف نصف مجموع جميع المدخلات بالضبط، أي $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ تُعرف هذه الحالة الخاصة من SSP باسم مشكلة التقسيم .

يمكن اعتبار مسألة SSP أيضًا مسألة تحسين : إيجاد مجموعة جزئية مجموعها لا يتجاوز T ، مع مراعاة ذلك، إيجاد مجموعة جزئية قريبة قدر الإمكان من T. وهي مسألة صعبة من نوع NP، ولكن هناك العديد من الخوارزميات التي يمكنها حلها بسرعة معقولة عمليًا.

SSP هي حالة خاصة من مشكلة حقيبة الظهر ومشكلة مجموع المجموعات الفرعية المتعددة .

الصلابة الحسابية

يعتمد التعقيد الزمني لمسألة SSP على معيارين:

n - عدد الأعداد الصحيحة المدخلة. إذا كان n عددًا صغيرًا وثابتًا، فإن البحث الشامل عن الحل يكون عمليًا.
L - دقة المسألة، وتُعرَّف بعدد القيم الثنائية اللازمة لصياغة المسألة. إذا كانت L قيمة ثابتة صغيرة، فهناك خوارزميات برمجة ديناميكية قادرة على حلها بدقة.

مع ازدياد كل من n و L ، تصبح مسألة SSP من المسائل الصعبة حسابيًا (NP-hard). ويتناسب تعقيد أفضل الخوارزميات المعروفة تناسبًا أُسّيًا مع أصغر المعاملين n و L. وتبقى المسألة صعبة حسابيًا حتى عندما تكون جميع الأعداد الصحيحة المُدخلة موجبة (ويكون مجموع الهدف T جزءًا من المُدخلات). ويمكن إثبات ذلك بالاختزال المباشر من مسألة 3SAT . ^{[ 2 ]} كما يمكن إثباته بالاختزال من مسألة المطابقة ثلاثية الأبعاد (3DM): ^{[ 3 ]}

لدينا مثال على خوارزمية 3DM، حيث مجموعات الرؤوس هي W و X و Y. تحتوي كل مجموعة على n رأسًا. يوجد m حافة، حيث تحتوي كل حافة على رأس واحد فقط من كل من W و X و Y. لنرمز إلى L بـ ceiling(log ₂ ( m +1))، بحيث يكون L أكبر من عدد البتات اللازمة لتمثيل عدد الحواف.
نقوم بإنشاء حالة من SSP مع m عدد صحيح موجبتُوصَف الأعداد الصحيحة بتمثيلها الثنائي. يمكن تمثيل كل عدد صحيح مُدخل بـ 3 nL بت، مُقسَّمة إلى 3 n منطقة من L بت. كل منطقة تُقابل رأسًا.
لكل حافة (w,x,y) في نموذج 3DM، يوجد عدد صحيح في نموذج SSP، حيث تكون ثلاث بتات بالضبط "1": وهي البتات الأقل أهمية في مناطق الرؤوس w و x و y. على سبيل المثال، إذا كان n = 10 و L = 3، و W = (0, ..., 9)، و X = (10, ..., 19)، و Y = (20, ..., 29)، فإن الحافة (0, 10, 20) تُمثَّل بالعدد (20 ⁺ 230 ⁺ 260 ⁾ .
يتم تعيين مجموع الهدف T في مثيل SSP إلى عدد صحيح مع "1" في البت الأقل أهمية في كل منطقة، أي (2 ⁰ +2 ¹ +...+2 ^3n-1 ).
إذا كان لنموذج 3DM تطابق مثالي ، فإن جمع الأعداد الصحيحة المقابلة في نموذج SSP ينتج عنه T بالضبط.
وعلى العكس من ذلك، إذا كان لمثال SSP مجموعة فرعية مجموعها T بالضبط، فبما أن المناطق كبيرة بما يكفي بحيث لا توجد "عمليات نقل" من منطقة إلى أخرى، فإن المجموع يجب أن يتوافق مع تطابق مثالي في مثال 3DM.

من المعروف أيضاً أن المتغيرات التالية تُصنف ضمن المسائل الصعبة من نوع NP:

يمكن أن تكون الأعداد الصحيحة المدخلة موجبة أو سالبة، ويكون المجموع المستهدف T = 0. يمكن إثبات ذلك بالاختزال من الصيغة ذات الأعداد الصحيحة الموجبة. لنرمز لتلك الصيغة بـ SubsetSumPositive وللصيغة الحالية بـ SubsetSumZero. بفرض وجود مجموعة ( S , T ) من SubsetSumPositive، ننشئ مجموعة SubsetSumZero بإضافة عنصر واحد قيمته -T . بفرض وجود حل لمجموعة SubsetSumPositive، فإن إضافة -T ينتج عنها حل لمجموعة SubsetSumZero. وبالعكس، بفرض وجود حل لمجموعة SubsetSumZero، يجب أن يحتوي على -T ( لأن جميع الأعداد الصحيحة في S موجبة)، لذا للحصول على مجموع يساوي صفرًا، يجب أن يحتوي أيضًا على مجموعة جزئية من S مجموعها + T ، وهو حل لمجموعة SubsetSumPositive.
الأعداد الصحيحة المدخلة موجبة، و T = مجموع ( S ) / 2. يمكن إثبات ذلك أيضًا عن طريق الاختزال من الصيغة العامة؛ انظر مسألة التقسيم .

تُعتبر مسألة العد المماثلة #SSP، التي تطلب تعداد عدد المجموعات الجزئية التي مجموعها يساوي الهدف، مسألة كاملة من النوع #P . ^{[ 4 ]}

خوارزميات الوقت الأسي

توجد عدة طرق لحل مسألة SSP في وقت أسي في n . ^{[ 5 ]}

الإدراج والاستبعاد

أبسط خوارزمية هي المرور على جميع المجموعات الجزئية المكونة من n عددًا، والتحقق لكل مجموعة جزئية مما إذا كان مجموعها يساوي العدد الصحيح. زمن التشغيل من رتبة $O(2^{n}\cdot n)$ ، نظراً لوجود $2^{n}$ المجموعات الفرعية، وللتحقق من كل مجموعة فرعية، نحتاج إلى جمع ما لا يزيد عن n عنصرًا.

يمكن تنفيذ الخوارزمية عن طريق البحث العميق أولاً في شجرة ثنائية : كل مستوى في الشجرة يُقابل رقمًا مُدخلاً؛ الفرع الأيسر يُقابل استبعاد الرقم من المجموعة، والفرع الأيمن يُقابل تضمين الرقم (ومن هنا جاء اسم "التضمين والاستبعاد"). الذاكرة المطلوبة هي $O(n)$ يمكن تحسين وقت التشغيل من خلال العديد من الطرق الاستدلالية: ^{[ 5 ]}

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

هورويتز وساهني

في عام 1974، نشر هورويتز وساهني ^[⁶^] خوارزمية أسرع تعمل في زمن أسي، والتي تعمل في زمن $O(2^{n/2})$ لكنها تتطلب مساحة أكبر بكثير - $O(2^{n/2})$ تقوم الخوارزمية بتقسيم العناصر n بشكل عشوائي إلى مجموعتين من $n/2$ لكل مجموعة من هاتين المجموعتين، يتم تخزين قائمة بمجموع كل $2^{n/2}$ المجموعات الفرعية الممكنة لعناصرها. ثم يتم فرز كل من هاتين القائمتين. حتى باستخدام أسرع خوارزمية فرز مقارنة ، فإن خوارزمية فرز الدمج لهذه الخطوة ستستغرق وقتًا $O(2^{n/2}n)$ ومع ذلك، بالنظر إلى قائمة مرتبة من المجاميع لـ $k$ يمكن توسيع القائمة، التي تحتوي على عناصر، إلى قائمتين مرتبتين بإضافة ( $k+1$ العنصر رقم )، ويمكن دمج هاتين القائمتين المرتبتين في الوقت المناسب $O(2^{k})$ وبالتالي، يمكن إنشاء كل قائمة بشكل مُرتب في الوقت المناسب $O(2^{n/2})$ بمعرفة القائمتين المرتبتين، يمكن للخوارزمية التحقق مما إذا كان مجموع عنصر من المصفوفة الأولى وعنصر من المصفوفة الثانية يساوي T في وقت $O(2^{n/2})$ لتحقيق ذلك، يمرّ البرنامج على المصفوفة الأولى بترتيب تنازلي (بدءًا من أكبر عنصر) وعلى المصفوفة الثانية بترتيب تصاعدي (بدءًا من أصغر عنصر). عندما يكون مجموع العنصر الحالي في المصفوفة الأولى والعنصر الحالي في المصفوفة الثانية أكبر من T ، ينتقل البرنامج إلى العنصر التالي في المصفوفة الأولى. إذا كان المجموع أقل من T ، ينتقل البرنامج إلى العنصر التالي في المصفوفة الثانية. إذا وُجد عنصران مجموعهما يساوي T ، يتوقف البرنامج. (تُعرف المسألة الفرعية المتعلقة بمجموع عنصرين باسم "المجموع الثنائي" ^{[ 7 ]} ).

شرويبل وشامير

في عام 1981، قدم شروبيل وشامير خوارزمية ^{[ 8 ]} تعتمد على هورويتز وسانهي، والتي تتطلب وقت تشغيل مماثل - $O(2^{n/2}\cdot (n/4))$ مساحة أقل بكثير - $O(2^{n/4})$ بدلاً من توليد وتخزين جميع المجموعات الفرعية المكونة من n /2 عنصرًا مسبقًا، يقومون بتقسيم العناصر إلى 4 مجموعات، كل منها مكونة من n /4 عنصرًا، ثم يولدون مجموعات فرعية من أزواج n /2 عنصرًا ديناميكيًا باستخدام كومة دنيا ، مما ينتج عنه تعقيدات الوقت والمساحة المذكورة أعلاه، حيث يمكن القيام بذلك في $O(k^{2}\log(k))$ والمساحة $O(k)$ لدينا 4 قوائم طول كل منها k.

نظراً لمتطلبات المساحة، فإن خوارزمية HS عملية لما يصل إلى حوالي 50 عدداً صحيحاً، وخوارزمية SS عملية لما يصل إلى 100 عدد صحيح. ^{[ 5 ]}

هاوغراف-غراهام وجو

في عام 2010، قدم هاوغراف-غراهام وجو ^{[ 9 ]} خوارزمية احتمالية تعمل بشكل أسرع من جميع الخوارزميات السابقة - من حيث الوقت $O(2^{0.337n})$ استخدام المساحة $O(2^{0.256n})$ إنها تحل مشكلة القرار فقط، ولا يمكنها إثبات عدم وجود حل لمجموع معين، ولا تعيد مجموع المجموعة الفرعية الأقرب إلى T.

تم توسيع تقنيات Howgrave-Graham وJoux لاحقًا ^{[ 10 ]} مما أدى إلى خفض التعقيد الزمني إلى $O(2^{0.291n})$ وقد أدى تعميم أحدث ^{[ 11 ]} إلى خفض التعقيد الزمني إلى $O(2^{0.283n})$ .

حلول البرمجة الديناميكية ذات الوقت شبه متعدد الحدود

يمكن حل مسألة SSP في وقت شبه متعدد الحدود باستخدام البرمجة الديناميكية . لنفترض أن لدينا التسلسل التالي من العناصر في حالة معينة:

x_{1},\ldots ,x_{N}

نُعرّف الحالة بأنها زوج ( i , s ) من الأعداد الصحيحة. تمثل هذه الحالة حقيقة أن

"هناك مجموعة فرعية غير فارغة من

x_{1},\ldots ,x_{i}

وهو ما يساوي

s

.

لكل حالة ( i ، s ) حالتان تالتان:

( i + 1, s )، مما يعني أن $x_{i+1}$ غير مدرج في المجموعة الفرعية؛
( i +1, s + $x_{i+1}$ )، مما يعني أن $x_{i+1}$ مدرج في المجموعة الفرعية.

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

زمن تشغيل هذه الخوارزمية خطي على الأكثر بالنسبة لعدد الحالات. عدد الحالات هو على الأكثر N ضعف عدد المجاميع الممكنة المختلفة. لنفترض أن $A$ هو مجموع القيم السالبة و $B$ هو مجموع القيم الموجبة؛ عدد المجاميع الممكنة المختلفة هو على الأكثر B - A ، لذا فإن زمن التشغيل الكلي هو $O(N\cdot (B-A))$ على سبيل المثال، إذا كانت جميع قيم المدخلات موجبة ومحدودة بثابت ما C ، فإن B تكون على الأكثر NC ، وبالتالي فإن الوقت المطلوب هو $O(N^{2}C)$ .

لا يُعتبر هذا الحل حلاً ذا زمن متعدد الحدود في نظرية التعقيد لأن $B-A$ لا تُعتبر هذه الخوارزمية متعددة الحدود بالنسبة لحجم المسألة ، أي عدد البتات المستخدمة لتمثيلها. بينما تُعتبر متعددة الحدود بالنسبة لقيم $A$ و $B$ ، والتي تُعتبر أسية بالنسبة لعدد بتاتها. مع ذلك، فإن خوارزمية مجموع المجموعات الجزئية المشفرة بنظام العد الأحادي تقع ضمن فئة P، لأن حجم التشفير في هذه الحالة يكون خطيًا بالنسبة لـ BA. لذا، فإن خوارزمية مجموع المجموعات الجزئية تُعتبر فقط NP-كاملة ضعيفة .

في حالة أن كل $x_{i}$ موجبة ومحدودة بثابت ثابت $C$ ، وفي عام 1999، وجد بيسينجر خوارزمية زمنية خطية ذات تعقيد زمني $O(NC)$ (لاحظ أن هذا ينطبق على نسخة المسألة التي لا يكون فيها المجموع المستهدف بالضرورة صفرًا، وإلا ستكون المسألة تافهة). ^{[ 12 ]} في عام 2015، وجد كويلياريس وشو حلاً حتميًا ${\tilde {O}}(T{\sqrt {N}})$ خوارزمية لحل مسألة مجموع المجموعات الجزئية حيث $T$ هو المجموع المطلوب إيجاده. ^{[ 13 ]} في عام 2017، وجد برينغمان خوارزمية عشوائية ${\tilde {O}}(T+N)$ خوارزمية الوقت. ^{[ 14 ]}

في عام 2014، وجد كورتيس وسانشيز تكرارًا بسيطًا قابلًا للتوسع بدرجة كبيرة في آلات SIMD التي $O(N(m-x_{\min })/p)$ الوقت و $O(N+m-x_{\min })$ المساحة، حيث يمثل $p$ عدد عناصر المعالجة، $m=\min(s,\sum x_{i}-s)$ و $x_{\min }$ هو أصغر عدد صحيح. ^{[ 15 ]} هذا هو أفضل تعقيد نظري متوازي معروف حتى الآن.

ناقش كورتيس وسانشيز مقارنة بين النتائج العملية وحل الحالات الصعبة لمسألة SSP. ^{[ 16 ]}

خوارزميات تقريبية متعددة الحدود

لنفترض أن جميع المدخلات موجبة. تهدف خوارزمية التقريب لمسألة SSP إلى إيجاد مجموعة جزئية من S يكون مجموعها على الأكثر T وعلى الأقل r ضعف المجموع الأمثل، حيث r هو عدد في (0،1) يسمى نسبة التقريب .

تقريب بسيط بمقدار 1/2

الخوارزمية البسيطة التالية لها نسبة تقريب تبلغ 1/2: ^{[ 17 ]}

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

عند انتهاء هذه الخوارزمية، إما أن تكون جميع المدخلات ضمن المجموعة الجزئية (وهو الخيار الأمثل بالطبع)، أو أن هناك مدخلاً لا يتناسب معها. يكون أول مدخل من هذا النوع أصغر من جميع المدخلات السابقة الموجودة في المجموعة الجزئية، ويكون مجموع المدخلات في المجموعة الجزئية أكبر من T /2. وإلا، فإن المدخل يكون أيضًا أصغر من T/2 ويتناسب مع المجموعة. من الواضح أن هذا المجموع الأكبر من T/2 أكبر من OPT/2.

مخطط تقريبي ذو زمن متعدد الحدود بالكامل

تحقق الخوارزمية التالية، لكل $\epsilon >0$ ، وهي نسبة تقريبية لـ $(1-\epsilon )$ زمن تشغيله متعدد الحدود في $n$ و $1/\epsilon$ تذكر أن n هو عدد المدخلات و T هو الحد الأعلى لمجموع المجموعة الفرعية.

قم بتهيئة قائمة L بحيث تحتوي على عنصر واحد هو 0. لكل i من 1 إلى n ، دع U _i تكون قائمة تحتوي على جميع العناصر y في L ، وجميع المجاميع x _i + y لجميع y في L. رتب U _i ترتيبًا تصاعديًا اجعل L فارغًا ليكن y أصغر عنصر في Uᵢ _، أضف y إلى L. لكل عنصر z من Uᵢ بترتيب تصاعدي، قم بما يلي: _// تقليص القائمة بحذف الأرقام المتقاربة // وحذف العناصر الأكبر من المجموع المستهدف T. إذا كان y + εT / n < z ≤ T ، فإن y = z. أضف z إلى L.أعد أكبر عنصر في L.

لاحظ أنه بدون خطوة التقليم (حلقة "for each" الداخلية)، ستحتوي القائمة L على مجموع كل $2^{n}$ مجموعات فرعية من المدخلات. تقوم خطوة التقليم بأمرين:

يضمن ذلك أن جميع المجاميع المتبقية في L أقل من T ، لذا فهي حلول ممكنة لمسألة مجموع المجموعات الفرعية.
يضمن ذلك أن تكون القائمة L "متفرقة"، أي أن الفرق بين كل مجموعين جزئيين متتاليين لا يقل عن $\epsilon T/n$ .

تضمن هذه الخصائص مجتمعة ألا تحتوي القائمة $L$ على أكثر من $n/\epsilon$ العناصر؛ لذلك فإن وقت التشغيل متعدد الحدود في $n/\epsilon$ .

عند انتهاء الخوارزمية، إذا كان المجموع الأمثل ضمن $المجموعة L$ ، فإنه يُعاد وتُعتبر العملية منتهية. وإلا، فإنه يكون قد أُزيل في خطوة تقليم سابقة. تُضيف كل خطوة تقليم خطأً إضافيًا لا يتجاوز $\epsilon T/n$ لذلك، فإنّ $n$ خطوة معًا تُدخل خطأً لا يتجاوز $\epsilon T$ لذلك، فإن الحل المُعاد هو على الأقل ${\text{OPT}}-\epsilon T$ وهو الأقل $(1-\epsilon ){\text{OPT}}$ .

تُقدّم الخوارزمية المذكورة أعلاه حلاً دقيقاً لمسألة SSP في حالة كون الأرقام المُدخلة صغيرة (وغير سالبة). إذا أمكن تحديد أي مجموع للأرقام باستخدام $P$ بت على الأكثر، فإن حل المسألة تقريباً باستخدام $\epsilon =2^{-P}$ يُعادل ذلك حلها بدقة. عندئذٍ، تتحول خوارزمية الوقت متعدد الحدود لمجموع المجموعات الجزئية التقريبي إلى خوارزمية دقيقة بوقت تشغيل متعدد الحدود في $n$ و $2^{P}$ (أي، أسية في $P$ ).

يقدم كل من Kellerer و Mansini و Pferschy و Speranza ^{[ 18 ]} و Kellerer و Pferschy و Pisinger ^{[ 19 ]} طرقًا أخرى لتحليل المجموعات الجزئية.

انظر أيضاً

مسألة حقيبة الظهر – مسألة في التحسين التوافقي – تعميم لمسألة الإحلال البسيط حيث يكون لكل عنصر من عناصر الإدخال قيمة ووزن. الهدف هو تعظيم القيمة مع مراعاة حد أقصى للوزن الإجمالي .
مسألة مجموع المجموعات الفرعية المتعددة – مسألة التحسين الرياضي صفحات تعرض أوصافًا قصيرة لأهداف إعادة التوجيه – تعميم لمسألة مجموع المجموعات الفرعية حيث يجب على المرء اختيار عدة مجموعات فرعية.
3SUM – مشكلة في نظرية التعقيد الحسابي
نظام تشفير حقيبة الظهر ميركل-هيلمان – شكل من أشكال التشفير بالمفتاح العام

مراجع

1 2 كلاينبرج، جون؛ تاردوس، إيفا (2006). تصميم الخوارزمية (الطبعة الثانية ). ص. 491 . رقم ISBN 0-321-37291-3.
↑ غودريتش، مايكل. "المزيد من مسائل NP الكاملة ومسائل NP الصعبة" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.
↑ غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية ( الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 . ، القسم 3.1 والمسألة SP1 في الملحق أ.3.1.
↑ فيلموس، يوفال (30 يناير 2016). إجابة على: " هل توجد خوارزمية سريعة معروفة لحساب جميع المجموعات الجزئية التي يكون مجموعها أقل من عدد معين؟ ". تبادل الأسئلة والأجوبة في علوم الحاسوب النظرية . تجدر الإشارة إلى أن الاستشهاد الذي قدمه فيلموس لدعم ادعائه (فاليسزوسكي، بيوتر؛ هيماسباندرا، لين (2009). "تعقيد مقارنة مؤشر القوة". علوم الحاسوب النظرية . إلسيفير. 410 : 101-107. DOI 10.1016/j.tcs.2008.09.034 ) لا يثبت الادعاء في الواقع، بل يحيل القراء إلى استشهاد آخر ( باباديميتريو، كريستوس (1994). التعقيد الحسابي . أديسون-ويسلي: ريدينغ، ماساتشوستس. الفصل9. ISBN 0-201-53082-1 (عبر أرشيف الإنترنت )، وهو ما لا يثبت الادعاء صراحةً أيضًا. مع ذلك، فإن برهان باباديميتريو على أن مسألة SSP هي مسألة NP-كاملة عبر اختزال مسألة 3SAT ، يُعمم ليشمل اختزالًا من مسألة #3SAT إلى مسألة #SSP.
1 2 3 كورف، ريتشارد إي .؛ شرايبر، إيثان إل.؛ موفيت، مايكل دي. (2014). "التقسيم الأمثل للأرقام المتسلسلة متعددة الاتجاهات" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.
↑ هورويتز، إليس؛ ساهني، سرتاج (1974). "حساب التقسيمات مع تطبيقات على مسألة الحقيبة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 21 ( 2): 277-292 . doi : 10.1145/321812.321823 . hdl : 1813/5989 . MR 0354006. S2CID 16866858. مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.
↑ "مسألة المجموع الثنائي" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.
↑ شرويبل، ريتشارد؛ شامير، عدي (1981-08-01). " خوارزمية $T$ $=$ $O$ $(2$ $n$ $/2$ $)$ ، $S$ $=$ $O$ $(2$ $n$ $/4$ $)$ لبعض مسائل NP-كاملة" . مجلة SIAM للحوسبة . 10 (3): 456-464 . doi : 10.1137/0210033 . ISSN 0097-5397 .
↑ هاوغريف-غراهام، نيك؛ جو، أنطوان (2010). "خوارزميات عامة جديدة لحقائب الظهر الصلبة". في: جيلبرت، هنري (محرر). التطورات في علم التشفير - يورو كريبت 2010. سلسلة محاضرات في علوم الحاسوب. المجلد 6110. برلين، هايدلبرغ: سبرينغر. الصفحات 235-256 . doi : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.
^ بيكر ، أنجا. كورون، جان سيباستيان؛ جو، أنطوان (2011). “تحسين الخوارزميات العامة لحقائب الظهر الصلبة”. في باترسون، كينيث (محرر). التقدم في علم التشفير – EUROCRYPT 2011 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 6632. برلين، هايدلبرغ: سبرينغر. الصفحات من 364 إلى 385. دوى : 10.1007/978-3-642-20465-4_21 . رقم ISBN 978-3-642-20465-4.
↑ بونتان، كزافييه؛ بريكو، ريمي؛ شروتينلوهر، أندريه؛ شين، ييكسين (2020). "خوارزميات كلاسيكية وكمومية محسّنة لمجموع المجموعات الجزئية". في: مورياي، شيهو؛ وانغ، هواكسيونغ (محرران). التطورات في علم التشفير - آسيا كريبت 2020. سلسلة محاضرات في علوم الحاسوب. المجلد 12492. برلين، هايدلبرغ: سبرينغر. الصفحات 633-666 . doi : 10.1007/978-3-030-64834-3_22 . ISBN 978-3-030-64833-6.
↑ بيسينجر، ديفيد (1999). "خوارزميات زمنية خطية لمسائل حقيبة الظهر ذات الأوزان المحدودة". مجلة الخوارزميات . 33 (1): 1-14 . doi : 10.1006/jagm.1999.1034 . MR 1712690 .
^ كولياريس، كونستانتينوس. شو ، تشاو (2015/07/08). “خوارزمية زمنية زائفة أسرع لمجموع المجموعة الفرعية”. أرخايف : 1507.02318 [ cs.DS ].
↑ برينغمان، كارل (2017). "خوارزمية شبه خطية ذات زمن متعدد الحدود الزائف لحساب مجموع المجموعات الجزئية". في: كلاين، فيليب ن. (محرر). وقائع الندوة السنوية الثامنة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA 2017) . SIAM. الصفحات 1073-1084 . arXiv : 1610.04712 . doi : 10.1137/1.9781611974782.69 . ISBN 978-1-61197-478-2.
↑ كورتيس، في في؛ سانشيز، سي إيه إيه (يناير 2016). "حل فعال لمسألة مجموع المجموعات الجزئية على وحدة معالجة الرسومات: حل فعال لمسألة مجموع المجموعات الجزئية على وحدة معالجة الرسومات". التزامن والحوسبة: الممارسة والتجربة . 28 (1): 95-113 . doi : 10.1002/cpe.3636 . S2CID 20927927 .
↑ كورتيس، في في؛ سانشيز، سي إيه إيه (يوليو 2017). "خوارزمية منخفضة المساحة لمسألة مجموع المجموعات الجزئية على وحدة معالجة الرسومات". الحوسبة وبحوث العمليات . 83 : 120-124 . doi : 10.1016/j.cor.2017.02.006 .
↑ كابرارا، ألبرتو؛ كيليرر، هانز؛ بفيرشي، أولريش (2000-02-01). "مسألة مجموع المجموعات الفرعية المتعددة" . مجلة SIAM للتحسين . 11 (2): 308-319 . doi : 10.1137/S1052623498348481 . ISSN 1052-6234 .
↑ كيليرر، هانز؛ مانسيني، ريناتا؛ بفيرشي، أولريش؛ سبيرانزا، ماريا غراتسيا (1 مارس 2003). "مخطط تقريب متعدد الحدود فعال لمسألة مجموع المجموعات الجزئية". مجلة علوم الحاسوب والأنظمة . 66 (2): 349-370 . doi : 10.1016/S0022-0000(03)00006-0 . ISSN 0022-0000 .
^ هانز كيلير. أولريش فيرشي؛ ديفيد بيسنجر (2004). مشاكل الحقيبة . سبرينغر. ص. 97. ردمك 9783540402862.

للمزيد من القراءة

كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "35.5: مسألة مجموع المجموعات الجزئية". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ISBN 0-262-03293-7.
مايكل ر. غاري وديفيد س. جونسون (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. ISBN 0-7167-1045-5.A3.2: SP13، صفحة 223.
لاغارياس، ج. س.؛ أودليزكو، أ. م. (1985-01-01). "حل مسائل مجموع المجموعات الفرعية منخفضة الكثافة" . مجلة ACM . 32 (1): 229-246 . doi : 10.1145/2455.2461 . ISSN 0004-5411 . S2CID 885632 .
مارتيلو، سيلفانو؛ توث، باولو (1990). "مسألة مجموع المجموعات الجزئية" . مسائل حقيبة الظهر: الخوارزميات والتفسيرات الحاسوبية . وايلي-إنترساينس. ص 105-136 . ISBN 0-471-92420-2MR 1086874 .

[kleinberg2006p491-1] 1 2 كلاينبرج، جون؛ تاردوس، إيفا (2006). تصميم الخوارزمية (الطبعة الثانية ). ص. 491 . رقم ISBN 0-321-37291-3.

[2] غودريتش، مايكل. "المزيد من مسائل NP الكاملة ومسائل NP الصعبة" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.

[garey79-3] غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية ( الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 . ، القسم 3.1 والمسألة SP1 في الملحق أ.3.1.

[4] فيلموس، يوفال (30 يناير 2016). إجابة على: " هل توجد خوارزمية سريعة معروفة لحساب جميع المجموعات الجزئية التي يكون مجموعها أقل من عدد معين؟ ". تبادل الأسئلة والأجوبة في علوم الحاسوب النظرية . تجدر الإشارة إلى أن الاستشهاد الذي قدمه فيلموس لدعم ادعائه (فاليسزوسكي، بيوتر؛ هيماسباندرا، لين (2009). "تعقيد مقارنة مؤشر القوة". علوم الحاسوب النظرية . إلسيفير. 410 : 101-107. DOI 10.1016/j.tcs.2008.09.034 ) لا يثبت الادعاء في الواقع، بل يحيل القراء إلى استشهاد آخر ( باباديميتريو، كريستوس (1994). التعقيد الحسابي . أديسون-ويسلي: ريدينغ، ماساتشوستس. الفصل9. ISBN 0-201-53082-1 (عبر أرشيف الإنترنت )، وهو ما لا يثبت الادعاء صراحةً أيضًا. مع ذلك، فإن برهان باباديميتريو على أن مسألة SSP هي مسألة NP-كاملة عبر اختزال مسألة 3SAT ، يُعمم ليشمل اختزالًا من مسألة #3SAT إلى مسألة #SSP.

[:0-5] 1 2 3 كورف، ريتشارد إي .؛ شرايبر، إيثان إل.؛ موفيت، مايكل دي. (2014). "التقسيم الأمثل للأرقام المتسلسلة متعددة الاتجاهات" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.

[6] هورويتز، إليس؛ ساهني، سرتاج (1974). "حساب التقسيمات مع تطبيقات على مسألة الحقيبة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 21 ( 2): 277-292 . doi : 10.1145/321812.321823 . hdl : 1813/5989 . MR 0354006. S2CID 16866858. مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.

[7] "مسألة المجموع الثنائي" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.

[8] شرويبل، ريتشارد؛ شامير، عدي (1981-08-01). " خوارزمية $T$ $=$ $O$ $(2$ $n$ $/2$ $)$ ، $S$ $=$ $O$ $(2$ $n$ $/4$ $)$ لبعض مسائل NP-كاملة" . مجلة SIAM للحوسبة . 10 (3): 456-464 . doi : 10.1137/0210033 . ISSN 0097-5397 .

[9] هاوغريف-غراهام، نيك؛ جو، أنطوان (2010). "خوارزميات عامة جديدة لحقائب الظهر الصلبة". في: جيلبرت، هنري (محرر). التطورات في علم التشفير - يورو كريبت 2010. سلسلة محاضرات في علوم الحاسوب. المجلد 6110. برلين، هايدلبرغ: سبرينغر. الصفحات 235-256 . doi : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.

[10] بيكر ، أنجا. كورون، جان سيباستيان؛ جو، أنطوان (2011). “تحسين الخوارزميات العامة لحقائب الظهر الصلبة”. في باترسون، كينيث (محرر). التقدم في علم التشفير – EUROCRYPT 2011 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 6632. برلين، هايدلبرغ: سبرينغر. الصفحات من 364 إلى 385. دوى : 10.1007/978-3-642-20465-4_21 . رقم ISBN 978-3-642-20465-4.

[11] بونتان، كزافييه؛ بريكو، ريمي؛ شروتينلوهر، أندريه؛ شين، ييكسين (2020). "خوارزميات كلاسيكية وكمومية محسّنة لمجموع المجموعات الجزئية". في: مورياي، شيهو؛ وانغ، هواكسيونغ (محرران). التطورات في علم التشفير - آسيا كريبت 2020. سلسلة محاضرات في علوم الحاسوب. المجلد 12492. برلين، هايدلبرغ: سبرينغر. الصفحات 633-666 . doi : 10.1007/978-3-030-64834-3_22 . ISBN 978-3-030-64833-6.

[Pisinger09-12] بيسينجر، ديفيد (1999). "خوارزميات زمنية خطية لمسائل حقيبة الظهر ذات الأوزان المحدودة". مجلة الخوارزميات . 33 (1): 1-14 . doi : 10.1006/jagm.1999.1034 . MR 1712690 .

[13] كولياريس، كونستانتينوس. شو ، تشاو (2015/07/08). “خوارزمية زمنية زائفة أسرع لمجموع المجموعة الفرعية”. أرخايف : 1507.02318 [ cs.DS ].

[14] برينغمان، كارل (2017). "خوارزمية شبه خطية ذات زمن متعدد الحدود الزائف لحساب مجموع المجموعات الجزئية". في: كلاين، فيليب ن. (محرر). وقائع الندوة السنوية الثامنة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA 2017) . SIAM. الصفحات 1073-1084 . arXiv : 1610.04712 . doi : 10.1137/1.9781611974782.69 . ISBN 978-1-61197-478-2.

[15] كورتيس، في في؛ سانشيز، سي إيه إيه (يناير 2016). "حل فعال لمسألة مجموع المجموعات الجزئية على وحدة معالجة الرسومات: حل فعال لمسألة مجموع المجموعات الجزئية على وحدة معالجة الرسومات". التزامن والحوسبة: الممارسة والتجربة . 28 (1): 95-113 . doi : 10.1002/cpe.3636 . S2CID 20927927 .

[16] كورتيس، في في؛ سانشيز، سي إيه إيه (يوليو 2017). "خوارزمية منخفضة المساحة لمسألة مجموع المجموعات الجزئية على وحدة معالجة الرسومات". الحوسبة وبحوث العمليات . 83 : 120-124 . doi : 10.1016/j.cor.2017.02.006 .

[:1-17] كابرارا، ألبرتو؛ كيليرر، هانز؛ بفيرشي، أولريش (2000-02-01). "مسألة مجموع المجموعات الفرعية المتعددة" . مجلة SIAM للتحسين . 11 (2): 308-319 . doi : 10.1137/S1052623498348481 . ISSN 1052-6234 .

[18] كيليرر، هانز؛ مانسيني، ريناتا؛ بفيرشي، أولريش؛ سبيرانزا، ماريا غراتسيا (1 مارس 2003). "مخطط تقريب متعدد الحدود فعال لمسألة مجموع المجموعات الجزئية". مجلة علوم الحاسوب والأنظمة . 66 (2): 349-370 . doi : 10.1016/S0022-0000(03)00006-0 . ISSN 0022-0000 .

[knapsack-19] هانز كيلير. أولريش فيرشي؛ ديفيد بيسنجر (2004). مشاكل الحقيبة . سبرينغر. ص. 97. ردمك 9783540402862.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 18 ]

[ 19 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗