مشكلة التقسيم

في نظرية الأعداد وعلوم الحاسوب ، _تُعرف مسألة التقسيم ، أو تقسيم الأعداد ، ^{[ 1 ]} بأنها مهمة تحديد ما إذا كان بالإمكان تقسيم مجموعة متعددة S من الأعداد الصحيحة الموجبة إلى مجموعتين جزئيتين S1 و S2 بحيث يكون مجموع الأعداد في S1 _{مساويًا} لمجموع الأعداد في _{S2 .} على الرغم من أن مسألة التقسيم مصنفة ضمن مسائل NP- كاملة ، إلا أن هناك حلًا لها باستخدام البرمجة الديناميكية في زمن شبه متعدد الحدود ، كما توجد طرق استدلالية لحل المسألة في كثير من الحالات، إما بشكل أمثل أو تقريبي. لهذا السبب، تُسمى "أسهل مسألة صعبة". ^{[ 2 ] [ 3 ]}

توجد نسخة مُحسَّنة من مسألة التقسيم، وهي تقسيم المجموعة المتعددة S إلى مجموعتين جزئيتين S1 _و S2 بحيث يتم تقليل الفرق بين مجموع عناصر S1 ومجموع عناصر S2 . تُصنَّف النسخة المُحسَّنة ضمن _{المسائل الصعبة} حسابيًا (NP-hard) _، ولكن يمكن حلها بكفاءة في التطبيق العملي. ^{[ 4 ]}

تُعتبر مسألة التقسيم حالة خاصة من مسألتين مرتبطتين:

• في مسألة مجموع المجموعة الجزئية ، يكون الهدف هو إيجاد مجموعة جزئية من S يكون مجموعها هو رقم هدف معين T معطى كمدخل (مسألة التقسيم هي الحالة الخاصة التي يكون فيها T نصف مجموع S ).
• في تقسيم الأعداد متعددة الاتجاهات ، يوجد معلمة عددية صحيحة k ، والهدف هو تحديد ما إذا كان من الممكن تقسيم S إلى k مجموعات فرعية متساوية المجموع (مشكلة التقسيم هي الحالة الخاصة التي يكون فيها k = 2).

مع ذلك، يختلف هذا الأمر تمامًا عن مسألة التقسيم الثلاثي : ففي تلك المسألة، لا يُحدد عدد المجموعات الجزئية مسبقًا، بل يجب أن يكون | S |/3، حيث يجب أن تحتوي كل مجموعة جزئية على 3 عناصر بالضبط. وتُعدّ مسألة التقسيم الثلاثي أصعب بكثير من مسألة التقسيم، إذ لا يوجد لها خوارزمية ذات زمن شبه متعدد الحدود إلا إذا كانت P = NP . ^{[ 5 ]}

إذا كانت S = {3,1,1,2,2,1}، _فإن أحد الحلول الصحيحة لمسألة التقسيم هو المجموعتان S1 = {1,1,1,2} و _{S2 = {2,3}. مجموع المجموعتين يساوي 5، وهما تقسمان S. هذا الحل ليس وحيدًا. S1 =} { 3,1,1 } و S2 = { 2,2,1 _} حل آخر.

ليس لكل مجموعة متعددة من الأعداد الصحيحة الموجبة تقسيم إلى مجموعتين جزئيتين متساويتين في المجموع. مثال على هذه المجموعة هو S = {2,5}.

تُعدّ مسألة التقسيم من المسائل الصعبة حسابيًا (NP-hard). ويمكن إثبات ذلك بالاختزال من مسألة مجموع المجموعات الجزئية . ^{[ 6 ]} تتكون حالة من مسألة مجموع المجموعات الجزئية من مجموعة S من الأعداد الصحيحة الموجبة ومجموع مستهدف T ؛ والهدف هو تحديد ما إذا كانت هناك مجموعة جزئية من S مجموعها يساوي T تمامًا . 

بالنظر إلى هذه الحالة ، قم بإنشاء حالة من خوارزمية التقسيم (Partition) حيث تحتوي مجموعة الإدخال على المجموعة الأصلية بالإضافة إلى عنصرين: _{z1 و} z2، مع كون z1 = مجموع (S) و z2 = 2T _. مجموع مجموعة الإدخال هذه _هو مجموع ( S ) + _z1 + z2 = 2 مجموع ( S ) ₊ 2T ، لذا فإن مجموع الهدف لخوارزمية التقسيم هو مجموع ( S ) + T.              

• لنفترض وجود حل S ′ لمسألة SubsetSum. إذن، sum( S ′ ) = T ، وبالتالي sum(S ′ ∪ z1 ₎ = sum( S ) + T ، لذا فإن _S ′ ∪ z1 هو حل لمسألة Partition.        
• على النقيض، لنفترض وجود حل S ' ' لمسألة التقسيم. عندئذٍ، يجب أن يحتوي S ' ' إما _{على z1} أو z2 ، وليس _كليهما ، لأن مجموعهما أكبر من مجموع S + T. إذا كان S '' يحتوي على z1 _، فإنه يجب أن يحتوي على عناصر من S مجموعها يساوي T بالضبط ، وبالتالي فإن S '' ناقص z1 هو حل لمسألة مجموع المجموعات الفرعية. إذا كان S _' ' يحتوي على _z2 ، فإنه يجب أن يحتوي على عناصر من S مجموعها يساوي مجموع S - T بالضبط ، وبالتالي فإن العناصر الأخرى في S هي حل لمسألة مجموع المجموعات الفرعية.     

كما ذُكر سابقًا، تُعدّ مسألة التقسيم حالةً خاصةً من التقسيم متعدد الاتجاهات ومسألة مجموع المجموعات الجزئية. لذا، يُمكن حلّها باستخدام خوارزميات مُطوّرة لكلٍّ من هاتين المسألتين. تشمل الخوارزميات المُطوّرة لتقسيم الأعداد متعدد الاتجاهات ما يلي:

• تجزئة الأعداد الجشعة - تمر على الأعداد، وتضع كل عدد في المجموعة التي يكون مجموعها الحالي هو الأصغر. إذا لم تكن الأعداد مرتبة، فإن زمن التشغيل هو O( n ) ونسبة التقريب لا تتجاوز 3/2 (نسبة التقريب تعني المجموع الأكبر في مخرجات الخوارزمية مقسومًا على المجموع الأكبر في التجزئة المثلى). يؤدي ترتيب الأعداد إلى زيادة زمن التشغيل إلى O( n  log n ) وتحسين نسبة التقريب إلى 7/6. إذا كانت الأعداد موزعة بانتظام في [0,1]، فإن نسبة التقريب لا تتجاوز ${\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}$من شبه المؤكد ، و${\textstyle 1+O\left({\frac {1}{n}}\right)}$في انتظار ذلك.
• تقوم طريقة أكبر فرق (وتُسمى أيضًا خوارزمية كارماركار-كارب ) بترتيب الأرقام تنازليًا، ثم تستبدل الأرقام بشكل متكرر بفروقها. يبلغ تعقيد وقت التشغيل O( n  log n ). في أسوأ الحالات، تكون نسبة التقريب مماثلة - 7/6 على الأكثر . مع ذلك، في الحالة المتوسطة، يكون أداؤها أفضل بكثير من الخوارزمية الجشعة : فعندما تكون الأرقام موزعة بانتظام في [0,1]، تكون نسبة التقريب على الأكثر ${\textstyle 1+1/n^{\Theta (\log n)}}$كما أنه يحقق أداءً أفضل في تجارب المحاكاة.
• تستخدم خوارزمية التوفيق المتعدد البحث الثنائي مع خوارزمية لتعبئة الصناديق . وفي أسوأ الحالات، تبلغ نسبة التقريب 8/7 .
• تحتوي مسألة مجموع المجموعة الجزئية على خوارزمية FPTAS يمكن استخدامها لمسألة التقسيم أيضًا، وذلك عن طريق تعيين المجموع المستهدف إلى sum( S )/2.

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

• يستغرق تقسيم العدد في وقت شبه متعدد الحدود${\textstyle O(n^{2}m)}$الوقت والاحتياجات${\textstyle O(nm)}$الذاكرة، حيث يمثل m أكبر رقم في المدخلات.
• تعتمد خوارزمية الجشع الكاملة (CGA) على بناء شجرة ثنائية لدراسة جميع التقسيمات . يُمثل كل مستوى في الشجرة رقمًا مُدخلًا، حيث يُمثل الجذر أكبر رقم، والمستوى الذي يليه يُمثل الرقم الذي يليه في الحجم، وهكذا. يُمثل كل فرع مجموعة مختلفة يُمكن وضع الرقم الحالي فيها. يتطلب اجتياز الشجرة بترتيب البحث العمقي أولًا فقط${\textstyle O(n)}$مساحة، ولكن قد يستغرق الأمر بعض الوقت${\textstyle O(2^{n})}$يمكن تحسين وقت التشغيل باستخدام خوارزمية جشعة: في كل مستوى، يتم أولاً تطوير الفرع الذي يُوضع فيه العدد الحالي في المجموعة ذات أصغر مجموع. تجد هذه الخوارزمية أولاً الحل الذي تم التوصل إليه بواسطة تجزئة الأعداد الجشعة ، ثم تبحث عن حلول أفضل. بعض الاختلافات في هذه الفكرة هي مخططات تقريبية ذات وقت متعدد الحدود بالكامل لمسألة مجموع المجموعات الجزئية، وبالتالي لمسألة التجزئة أيضًا. ^{[ 7 ] [ 8 ]}
• تعتمد خوارزمية كارماركار-كارب الكاملة (CKK) على بناء شجرة ثنائية لدراسة جميع التقسيمات. يُمثل كل مستوى زوجًا من الأرقام. يُشير الفرع الأيسر إلى وضع هذه الأرقام في مجموعات فرعية مختلفة (أي استبدالها بفرقها)، بينما يُشير الفرع الأيمن إلى وضعها في نفس المجموعة الفرعية (أي استبدالها بمجموعها). تبدأ هذه الخوارزمية بإيجاد الحل الذي تم التوصل إليه باستخدام طريقة أكبر فرق ، ثم تنتقل إلى إيجاد حلول أفضل. تعمل هذه الخوارزمية بسرعة أكبر بكثير من خوارزمية CGA على الحالات العشوائية. وتزداد ميزتها بشكل ملحوظ عند وجود تقسيم متساوٍ، وقد تصل إلى عدة مراتب. عمليًا، يُمكن حل مسائل ذات أحجام عشوائية باستخدام CKK إذا كانت الأرقام تحتوي على 12 رقمًا معنويًا على الأكثر . ^{[ 9 ]} كما يُمكن تشغيل CKK كخوارزمية فورية : حيث تجد حل كارماركار-كارب أولًا، ثم تجد حلولًا أفضل تدريجيًا كلما سمح الوقت بذلك (قد يتطلب ذلك وقتًا أُسّيًا للوصول إلى الحل الأمثل، في أسوأ الحالات). ^{[ 1 ]}$على)$مساحة، ولكن في أسوأ الأحوال قد يستغرق الأمر$O(2^{n})$وقت.

تتضمن الخوارزميات المطورة لحساب مجموع المجموعات الجزئية ما يلي:

• هورويتز وسانحي - يسيران في الوقت المحدد$O(2^{n/2}\cdot (n/2))$لكن ذلك يتطلب$O(2^{n/2})$فضاء.
• شرويبل وشامير - يسيران في الوقت المناسب $O(2^{n/2}\cdot (n/4))$ويتطلب مساحة أقل بكثير –${\textstyle O(2^{n/4})}$.
• هاوغريف-غراهام وجوكس – يركضان في الوقت المناسب${\textstyle O(2^{n/3})}$، لكنها خوارزمية عشوائية تحل مشكلة القرار فقط (وليس مشكلة التحسين).

تميل المجموعات التي تحتوي على قسم واحد فقط، أو لا تحتوي على أي أقسام، إلى أن تكون الأصعب (أو الأكثر تكلفة) في الحل مقارنةً بأحجام مدخلاتها. عندما تكون القيم صغيرة مقارنةً بحجم المجموعة، يكون احتمال وجود أقسام مثالية أكبر. من المعروف أن المشكلة تمر بـ " انتقال طوري "؛ حيث تكون محتملة لبعض المجموعات وغير محتملة لمجموعات أخرى. إذا كان m هو عدد البتات اللازمة للتعبير عن أي رقم في المجموعة، و n هو حجم المجموعة، فإن${\displaystyle m/n<1}$يميل إلى أن يكون له حلول عديدة و${\displaystyle m/n>1}$يميل هذا إلى امتلاك حلول قليلة أو معدومة. ومع ازدياد قيمتي n و m، فإن احتمال وجود تقسيم مثالي يقترب من 1 أو 0 على التوالي. وقد تم الاستدلال على ذلك في الأصل بناءً على أدلة تجريبية من قبل جينت ووالش، ^{[ 10 ]} ثم باستخدام أساليب من الفيزياء الإحصائية من قبل ميرتنز، ^{[ 11 ] [ 12 ]} وأثبته لاحقًا بورغز ، تشايز ، وبيتل . ^{[ 13 ]}

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

التقسيم ذو العدد المتساوي هو نوع من التقسيم حيث يجب أن يحتوي كلا الجزأين على عدد متساوٍ من العناصر، بالإضافة إلى تساوي مجموعهما. هذا النوع من التقسيم صعب حسابيًا (NP-hard) أيضًا. ^{[ 5 ] :} برهان ^SP12 . بفرض وجود تقسيم قياسي يحتوي على n عددًا، قم بإنشاء تقسيم ذي عدد متساوٍ من العناصر بإضافة n أصفار. من الواضح أن التقسيم الجديد يحتوي على تقسيم ذي عدد متساوٍ من العناصر ومجموع متساوٍ إذا وفقط إذا كان التقسيم الأصلي يحتوي على تقسيم ذي مجموع متساوٍ. انظر أيضًا: تقسيم الأعداد المتوازن .

تُعرف عملية تقسيم المنتج بأنها تقسيم مجموعة من الأعداد الصحيحة إلى مجموعتين لهما نفس المنتج (بدلاً من نفس المجموع). وتُصنف هذه المسألة ضمن المسائل الصعبة للغاية من نوع NP . ^{[ 14 ]}

يناقش كوفاليوف وبيش ^{[ 15 ]} نهجًا عامًا لإثبات صعوبة NP لمشاكل نوع التقسيم.

يُستخدم أحد تطبيقات مسألة التقسيم في التلاعب بالانتخابات . لنفترض وجود ثلاثة مرشحين (أ، ب، ج). يُراد انتخاب مرشح واحد باستخدام قاعدة تصويت تعتمد على نظام النقاط، كقاعدة الفيتو (حيث يستخدم كل ناخب حق النقض ضد مرشح واحد، ويفوز المرشح الحاصل على أقل عدد من عمليات الفيتو). إذا أراد ائتلاف ضمان انتخاب ج، فعليه تقسيم أصواته بين أ و ب بحيث يحصل كل منهما على أقل عدد ممكن من عمليات الفيتو. إذا كانت الأصوات مُرجّحة، فيمكن اختزال المسألة إلى مسألة التقسيم، وبالتالي يمكن حلها بكفاءة باستخدام خوارزمية CKK. وينطبق الأمر نفسه على أي قاعدة تصويت أخرى تعتمد على نظام النقاط. ^{[ 16 ]}

• بورغز، كريستيان؛ تشايز، جينيفر؛ بيتيل، بوريس (2001)، "الانتقال الطوري وتوسيع النطاق المحدود لمسألة تقسيم الأعداد الصحيحة"، الهياكل والخوارزميات العشوائية ، 19 ( 3-4 ): 247-288 ، CiteSeerX 10.1.1.89.9577 ، doi : 10.1002/rsa.10004 ، S2CID 6819493  
• جنت، إيان؛ والش، توبي (أغسطس 1996). "التحولات الطورية والنظريات المُلدّنة: تجزئة الأعداد كدراسة حالة". في: فولفغانغ والستر (محرر). وقائع المؤتمر الأوروبي الثاني عشر للذكاء الاصطناعي . ECAI-96. جون وايلي وأولاده. ص 170-174 . CiteSeerX 10.1.1.2.4475 .  
• جنت، إيان؛ والش، توبي (1998)، "تحليل الطرق الاستدلالية لتقسيم الأعداد"، الذكاء الحسابي ، 14 (3): 430-451 ، CiteSeerX 10.1.1.149.4980 ، doi : 10.1111/0824-7935.00069 ، S2CID 15344203  
• كورف، ريتشارد إي. (1998)، "خوارزمية كاملة لتقسيم الأرقام في أي وقت"، الذكاء الاصطناعي ، 106 (2): 181-203 ، CiteSeerX 10.1.1.90.993 ، doi : 10.1016/S0004-3702(98)00086-1 ، ISSN 0004-3702  
• ميرتنز، ستيفان (نوفمبر 1998)، "الانتقال الطوري في مسألة تقسيم الأعداد"، رسائل المراجعة الفيزيائية ، 81 (20): 4281-4284 ، arXiv : cond-mat/9807077 ، Bibcode : 1998PhRvL..81.4281M ، doi : 10.1103/PhysRevLett.81.4281 ، S2CID 119541289 
• ميرتنز، ستيفان (2001)، "مقاربة فيزيائية لتقسيم الأعداد"، علوم الحاسوب النظرية ، 265 ( 1-2 ): 79-108 ، arXiv : cond-mat/0009230 ، doi : 10.1016/S0304-3975(01)00153-0 ، S2CID 16534837 
• ميرتنز، ستيفان (2006). "أسهل مشكلة صعبة: تجزئة الأعداد" . في: ألون بيركوس؛ غابرييل إسترات؛ كريستوفر مور (محررون). التعقيد الحسابي والفيزياء الإحصائية . الولايات المتحدة الأمريكية: مطبعة جامعة أكسفورد. الصفحات 125-140 . arXiv : cond-mat/0310317 . Bibcode : 2003cond.mat.10317M . ISBN  9780195177374.
• ميرتنز، ستيفان (1999)، "خوارزمية كاملة في أي وقت لتقسيم الأعداد المتوازنة"، arXiv : cs/9903011