3SUM

مشكلة لم تُحل في علوم الحاسوب

هل توجد خوارزمية لحل مسألة 3SUM في وقت زمني

O(n^{2-\epsilon })

بالنسبة للبعض

\epsilon >0

؟

في نظرية التعقيد الحسابي ، تسأل مسألة 3SUM عما إذا كانت مجموعة معينة من $n$ الأعداد الحقيقية تتكون من ثلاثة عناصر مجموعها يساوي صفرًا. صيغة معممة، $k$ -SUM، يطرح نفس السؤال على $k$ يمكن حل مسألة 3SUM بسهولة باستخدام عدد من العناصر، وليس فقط 3. $O(n^{2})$ الوقت، والمطابقة $\Omega (n^{\lceil k/2\rceil })$ تُعرف الحدود الدنيا في بعض النماذج المتخصصة للحساب ( إريكسون 1999 ) .

وقد تم التكهن بأن أي خوارزمية حتمية لمسألة 3SUM تتطلب $\Omega (n^{2})$ في عام 2014، تم دحض فرضية 3SUM الأصلية من قبل آلان غرونلوند وسيث بيتي، اللذين قدما خوارزمية حتمية لحل 3SUM في $O(n^{2}/({\log n}/{\log \log n})^{2/3})$ الوقت. ^{[ 1 ]} بالإضافة إلى ذلك، أظهر غرونلوند وبيتيه أن تعقيد شجرة القرار الخطي 4 لـ 3SUM هو $O(n^{3/2}{\sqrt {\log n}})$ تم تحسين هذه الحدود لاحقًا. ^{[ 2 ]}^{[ 3 ]}^{[ 4 ]} أفضل خوارزمية معروفة حاليًا لحساب مجموع 3SUM تعمل في $O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})$ ^{[ 4 ]} أظهر كل من كين ولوفيت وموران أن تعقيد شجرة القرار الخطية السداسية لـ 3SUM هو $O(n{\log ^{2}n})$ [ ⁵^] الحد الأخير دقيق (حتى عامل لوغاريتمي). ولا يزال يُعتقد أن مسألة 3SUM غير قابلة للحل ^في $O(n^{2-\أوميغا (1)})$ الوقت المتوقع. ^{[ 6 ]}

عندما تكون العناصر أعدادًا صحيحة في النطاق $[-N,\dots ,N]$ يمكن حل مسألة 3SUM في $O(n+N\log N)$ الوقت من خلال تمثيل مجموعة المدخلات $S$ كمجموعة متجهات ثنائية ، حساب المجموعة $S+S$ لجميع المجاميع الزوجية كملفة منفصلة باستخدام تحويل فورييه السريع ، وأخيرًا مقارنة هذه المجموعة بـ $S$ [ ⁷^]

خوارزمية تربيعية

لنفترض أن مصفوفة الإدخال هي $S[0..n-1]$ في نماذج الحوسبة ذات الأعداد الصحيحة ( ذاكرة الوصول العشوائي للكلمات )، يمكن حل مسألة 3SUM في $O(n^{2})$ الوقت في المتوسط عن طريق إدخال كل رقم $S[i]$ في جدول تجزئة ، ثم، لكل فهرس $i$ و $j$ ، التحقق مما إذا كان جدول التجزئة يحتوي على العدد الصحيح $-(S[i]+S[j])$ .

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

فرز(S)؛ من أجل i = 0 إلى n - 2 نفّذ أ = S[i]؛ البداية = i + 1؛ النهاية = ن - 1؛ بينما (البداية < النهاية) نفّذ ب = S[بداية] ج = S[نهاية]؛ إذا كان (أ + ب + ج == 0) فقم بإخراج أ، ب، ج؛ // استمر في البحث عن جميع تركيبات الثلاثيات التي مجموعها يساوي صفرًا. // نحتاج إلى تحديث كل من النهاية والبداية معًا لأن قيم المصفوفة متميزة. البداية = البداية + 1؛ النهاية = النهاية - 1؛ وإلا إذا كان ( أ + ب + ج > 0) النهاية = النهاية - 1؛ آخر البداية = البداية + 1؛ نهاية نهاية

يوضح المثال التالي تنفيذ هذه الخوارزمية على مصفوفة صغيرة مرتبة . تظهر القيم الحالية لـ a باللون الأحمر، بينما تظهر قيم b و c باللون الأرجواني.

-25 -10 -7 -3 2 4 8 10 (أ + ب + ج = -25) -25 -10 -7 -3 2 4 8 10 (أ + ب + ج = -22) ... -25 -10 -7 -3 2 4 8 10 (أ + ب + ج = -7) -25 -10 -7 -3 2 4 8 10 (أ + ب + ج = -7) -25 -10 -7 -3 2 4 8 10 (أ + ب + ج = -3) -25 -10 -7 -3 2 4 8 10 (أ + ب + ج == 2) -25 -10 -7 -3 2 4 8 10 (a+b+c==0)

يمكن إثبات صحة الخوارزمية كما يلي: لنفترض أن لدينا حلاً للمعادلة a + b + c = 0. بما أن المؤشرات تتحرك في اتجاه واحد فقط، يمكننا تشغيل الخوارزمية حتى يشير المؤشر الأيسر إلى a. ثم نشغل الخوارزمية حتى يشير أحد المؤشرين المتبقيين إلى b أو c، أيهما يحدث أولاً. بعد ذلك، تستمر الخوارزمية في العمل حتى يشير المؤشر الأخير إلى الحد المتبقي، مما يعطي الحل الصحيح.

المتغيرات

مجموع غير صفري

بدلاً من البحث عن أعداد مجموعها يساوي صفرًا، يمكن البحث عن أعداد مجموعها أي ثابت C. وأبسط طريقة هي تعديل الخوارزمية الأصلية للبحث في جدول التجزئة عن العدد الصحيح . $(C-(S[i]+S[j]))$ ⁠ .

طريقة أخرى:

اطرح C /3 من جميع عناصر مصفوفة الإدخال.
في المصفوفة المعدلة، ابحث عن 3 عناصر مجموعها يساوي 0.

على سبيل المثال، إذا كانت A=[1,2,3,4] وطُلب منك إيجاد مجموع 3 للمصفوفة C = 4، فاطرح 4/3 من جميع عناصر A، ثم حل المسألة بالطريقة المعتادة لحساب مجموع 3، أي : $(aC/3)+(bC/3)+(cC/3)=0$ ⁠ .

ثلاث مصفوفات مختلفة

بدلاً من البحث عن الأرقام الثلاثة في مصفوفة واحدة، يمكننا البحث عنها في ثلاث مصفوفات مختلفة. أي، إذا كانت لدينا ثلاث مصفوفات X و Y و Z، فأوجد ثلاثة أرقام $a \in X و b \in Y و c \in Z$ بحيث $a+b+c=0$ . سمِّ المتغير ذو المصفوفة الواحدة 3SUM × 1 والمتغير ذو المصفوفة الثلاثية 3SUM × 3.

إذا توفرت لدينا خوارزمية لحل مسألة 3SUM × 1، فيمكن حل مسألة 3SUM × 3 بالطريقة التالية (بافتراض أن جميع العناصر أعداد صحيحة):

لكل عنصر في X و Y و Z ، اضبط : $X[i]\gets X[i]*10+1$ ، $Y[i]\gets Y[i]*10+2$ ، $Z[i]\gets Z[i]*10-3$ ⁠ .
ليكن S عبارة عن سلسلة من المصفوفات X و Y و Z.
استخدم أداة 3SUM × 1 لإيجاد ثلاثة عناصر $a'\in S,\ b'\in S,\ c'\in S$ بحيث $a'+b'+c'=0$ ⁠ .
العودة $a\gets (a'-1)/10,\ b\gets (b'-2)/10,\ c\gets (c'+3)/10$ ⁠ .

من خلال الطريقة التي قمنا بها بتحويل المصفوفات، من المؤكد أن $a \in X ، b \in Y ، c \in Z$ . ^{[ 9 ]}

مجموع الالتفاف

بدلاً من البحث عن عناصر عشوائية في المصفوفة بحيث:

S[k]=S[i]+S[j]

تبحث مسألة مجموع الالتفاف الثلاثي (Conv3SUM) عن العناصر في مواقع محددة : ^{[ 10 ]}

S[i+j]=S[i]+S[j]

الاختزال من Conv3SUM إلى 3SUM

إذا توفرت لدينا خوارزمية لحل مسألة 3SUM، فيمكن حل مسألة Conv3SUM بالطريقة التالية. ^{[ 10 ]}

عرّف مصفوفة جديدة T ، بحيث يكون لكل فهرس i : $T[i]=2nS[i]+i$ (حيث n هو عدد العناصر في المصفوفة، وتتراوح الفهارس من 0 إلى n -1).
حل مسألة 3SUM على المصفوفة T.

إثبات صحة الإثبات:

إذا كان في المصفوفة الأصلية ثلاثية تحتوي على $S[i+j]=S[i]+S[j]$ ، ثم $T[i+j]=2nS[i+j]+i+j=(2nS[i]+i)+(2nS[j]+j)=T[i]+T[j]$ لذلك سيتم إيجاد هذا الحل بواسطة 3SUM على T.
وعلى العكس من ذلك، إذا كان في المصفوفة الجديدة ثلاثية مع $T[k]=T[i]+T[j]$ ، ثم $2nS[k]+k=2n(S[i]+S[j])+(i+j)$ . لأن $i+j<2n$ بالضرورة $S[k]=S[i]+S[j]$ و $k=i+j$ لذا فهذا حل صالح لـ Conv3SUM على S.

الاختزال من 3SUM إلى Conv3SUM

إذا توفرت لدينا خوارزمية لحل مسألة Conv3SUM، فيمكن حل مسألة 3SUM بالطريقة التالية. ^{[ 6 ]}^{[ 10 ]}

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

h(x+y)=h(x)+h(y)

لنفترض أن جميع العناصر أعداد صحيحة في النطاق: 0... N −1، وأن الدالة h تربط كل عنصر بعنصر في نطاق الفهارس الأصغر: 0... n −1 . أنشئ مصفوفة جديدة T وأرسل كل عنصر من S إلى قيمة التجزئة الخاصة به في T ، أي لكل x في S ( $\forall x\in S$ ) :

T[h(x)]=x

لنفترض مبدئيًا أن عمليات الربط فريدة (أي أن كل خلية في T تقبل عنصرًا واحدًا فقط من S ). حل مسألة Conv3SUM على T. الآن:

إذا كان هناك حل لمسألة 3SUM: $z=x+y$ ، ثم: $T[h(z)]=T[h(x)]+T[h(y)]$ و $h(z)=h(x)+h(y)$ لذلك سيتم إيجاد هذا الحل بواسطة محلل Conv3SUM على T.
وعلى العكس من ذلك، إذا تم العثور على Conv3SUM على T ، فمن الواضح أنه يتوافق مع حل 3SUM على S لأن T هو مجرد تبديل لـ S.

هذا الحل المثالي غير فعال، لأن أي دالة تجزئة قد تربط عدة عناصر مختلفة من S بنفس الخلية في T. يكمن الحل في إنشاء مصفوفة . $T^{*}$ عن طريق اختيار عنصر عشوائي واحد من كل خلية من خلايا T ، وتشغيل Conv3SUM عليه . $T^{*}$ إذا تم العثور على حل، فهو حل صحيح لمسألة مجموع 3 على المجموعة S. إذا لم يتم العثور على حل، فقم بإنشاء مجموعة عشوائية مختلفة . $T^{*}$ ثم حاول مرة أخرى. لنفترض أن هناك على الأكثر R عنصرًا في كل خلية من T. عندئذٍ، فإن احتمال إيجاد حل (إن وُجد حل) هو احتمال أن يختار الاختيار العشوائي العنصر الصحيح من كل خلية، وهو $(1/R)^{3}$ عن طريق تشغيل Conv3SUM $R^{3}$ في بعض الأحيان، سيتم إيجاد الحل باحتمالية عالية.

لسوء الحظ، لا نمتلك تجزئة خطية مثالية، لذلك علينا استخدام دالة تجزئة شبه خطية ، أي دالة h بحيث:

h(x+y)=h(x)+h(y)

أو

h(x+y)=h(x)+h(y)+1

يتطلب هذا تكرار عناصر S عند نسخها إلى T ، أي وضع كل عنصر $x\in S$ كلاهما في $T[h(x)]$ (كما كان من قبل) وفي $T[h(x)]-1$ إذن، ستحتوي كل خلية على عنصرين R ، وسيتعين علينا تشغيل Conv3SUM $(2R)^{3}$ مرات.

صلابة 3SUM

تُسمى المسألة "صعبة من نوع 3SUM" إذا كان حلها في زمن أقل من التربيعي يستلزم وجود خوارزمية لحلها في زمن أقل من التربيعي. وقد قدم غاجينتان وأوفرمارس (1995) مفهوم صعوبة 3SUM ، حيث أثبتا أن فئة واسعة من مسائل الهندسة الحسابية تُصنف ضمن هذه الصعوبة، بما في ذلك المسائل التالية. (يُقر المؤلفان بأن العديد من هذه المسائل قد ساهم فيها باحثون آخرون).

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

توجد الآن العديد من المشكلات الأخرى التي تندرج ضمن هذه الفئة. ومن الأمثلة على ذلك مسألة فرز X + Y بصيغة القرار : إذا كانت لدينا مجموعتان من الأعداد $X$ و $Y$ ، كل منهما تحتوي على $n$ عنصرًا، فهل يوجد $n² من$ $x + y$ المتميزين حيث $x \in X و y \in Y$ ؟ ^{[ 11 ]}

انظر أيضاً

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

ملحوظات

↑ غرونلوند وبيتيه 2018 .
↑ فروند 2017 .
↑ الذهب والشرير 2017 .
1 2 Chan 2020 .
↑ كين، لوفيت وموران 2018 .
1 2 كوبيلويتز، تسفي؛ بيتي، سيث؛ بورات، إيلي (2014)، "صعوبة 3SUM في هياكل البيانات (الديناميكية)"، arXiv : 1407.6756 [ cs.DS ]{{cite arXiv}}: CS1 maint: overridden setting ( link )
^ كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين ، كليفورد (2009) [1990]، مقدمة للخوارزميات ( الطبعة الثالثة)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، ISBN 0-262-03384-4مثال 30.1–7، ص 906.
↑ رسوم بيانية للرؤية ومجموع 3 من تأليف مايكل هوفمان
↑ للحصول على اختزال في الاتجاه الآخر، انظر متغيرات مسألة المجموع الثلاثي .
1 2 3 باتراسكو، م. (2010)، "نحو حدود دنيا متعددة الحدود للمسائل الديناميكية"، وقائع الندوة الثانية والأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة - STOC '10 ، الصفحات 603-610 ، doi : 10.1145/1806689.1806772 ، ISBN 9781450300506
↑ ديمين، إريك ؛ إريكسون، جيف؛ أورورك، جوزيف (20 أغسطس 2006)، "المسألة 41: فرز X + Y (مجموعات ثنائية)" ، مشروع المسائل المفتوحة ، تم الاطلاع عليه في 23 سبتمبر 2014

مراجع

كين، دانيال م.؛ لوفيت، شاشار؛ موران، شاي (2018)، "أشجار القرار الخطية شبه المثلى لمسألة k-SUM والمسائل ذات الصلة"، وقائع الندوة السنوية الخمسين لجمعية ACM SIGACT حول نظرية الحوسبة ، الصفحات 554-563 ، arXiv : 1705.01720 ، doi : 10.1145/3188745.3188770 ، ISBN 9781450355599، S2CID 30368541
تشان، تيموثي م. (2020)، "تحسينات إضافية في عامل اللوغاريتم لخوارزمية 3SUM، والالتفاف (الوسيط،+)، وبعض مسائل 3SUM الهندسية الصعبة"، معاملات ACM في الخوارزميات ، 16 (1) 7: 1-23، doi : 10.1145/3363541 ، MR 4060405
غرونلوند، آلان؛ بيتي، سيث (2018)، "العلاقات الثلاثية، والمنحرفون، ومثلثات الحب"، مجلة ACM ، 65 (4) 22: 1-25 ، arXiv : 1404.0799 ، doi : 10.1145/3185378 ، MR 3795516
فروند، آري (2017)، "تحسين خوارزمية 3SUM شبه التربيعية"، Algorithmica ، 44 (2): 440-458 ، doi : 10.1007/s00453-015-0079-6 ، S2CID 253979651 .
الذهب، عمر؛ شارير، ميشا (2017)، "تحسين الحدود لـ 3SUM، $k$ -SUM، والانحطاط الخطي"، في كيرك بروهس؛ سوهلر، كريستيان (محرران)، الندوة الأوروبية السنوية الخامسة والعشرون حول الخوارزميات، وكالة الفضاء الأوروبية 2017، 4-6 سبتمبر 2017، فيينا، النمسا ، LIPics، المجلد. 87، شلوس داغستوهل – Leibniz-Zentrum für Informatik، الصفحات 42:1–42:13، دوى : 10.4230/LIPICS.ESA.2017.42 ، ISBN 978-3-95977-049-1، S2CID 691387
باران، إيليا؛ ديمين، إريك د . Pătraşcu، Mihai (2008)، “خوارزميات دون التربيعية لـ 3SUM” ، الخوارزمية ، 50 (4): 584–596 ، دوى : 10.1007 / s00453-007-9036-3 ، S2CID 9855995 .
ديمين، إريك د .؛ ميتشل، جوزيف إس بي ؛ أورورك، جوزيف (يوليو 2005)، "المسألة 11: مسائل 3SUM الصعبة" ، مشروع المسائل المفتوحة ، تم الاطلاع عليه بتاريخ 2008-09-02{{citation}}: CS1 maint: deprecated archiveal service ( link ) .
إريكسون، جيف (1999)، "الحدود الدنيا لمسائل الإرضاء الخطي" ، مجلة شيكاغو لعلوم الحاسوب النظرية ، 1999 ، مطبعة معهد ماساتشوستس للتكنولوجيا.
غاجينتان، أنكا؛ أوفرمارس، مارك هـ. (1995)، "حول فئة من مسائل O( n² ⁾ في الهندسة الحسابية"، الهندسة الحسابية: النظرية والتطبيقات ، 5 (3): 165-185 ، doi : 10.1016/0925-7721(95)00022-2 ، hdl : 1874/17058.
كينغ، جيمس (2004)، مسح للمسائل الصعبة من نوع 3SUM (ملف PDF).

[FOOTNOTEGrønlundPettie2018-1] غرونلوند وبيتيه 2018 .

[FOOTNOTEFreund2017-2] فروند 2017 .

[FOOTNOTEGoldSharir2017-3] الذهب والشرير 2017 .

[FOOTNOTEChan2020-4] 1 2 Chan 2020 .

[FOOTNOTEKaneLovettMoran2018-5] كين، لوفيت وموران 2018 .

[kpp14-6] 1 2 كوبيلويتز، تسفي؛ بيتي، سيث؛ بورات، إيلي (2014)، "صعوبة 3SUM في هياكل البيانات (الديناميكية)"، arXiv : 1407.6756 [ cs.DS ]{{cite arXiv}}: CS1 maint: overridden setting ( link )

[7] كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين ، كليفورد (2009) [1990]، مقدمة للخوارزميات ( الطبعة الثالثة)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، ISBN 0-262-03384-4مثال 30.1–7، ص 906.

[8] رسوم بيانية للرؤية ومجموع 3 من تأليف مايكل هوفمان

[9] للحصول على اختزال في الاتجاه الآخر، انظر متغيرات مسألة المجموع الثلاثي .

[patrascu10-10] 1 2 3 باتراسكو، م. (2010)، "نحو حدود دنيا متعددة الحدود للمسائل الديناميكية"، وقائع الندوة الثانية والأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة - STOC '10 ، الصفحات 603-610 ، doi : 10.1145/1806689.1806772 ، ISBN 9781450300506

[11] ديمين، إريك ؛ إريكسون، جيف؛ أورورك، جوزيف (20 أغسطس 2006)، "المسألة 41: فرز X + Y (مجموعات ثنائية)" ، مشروع المسائل المفتوحة ، تم الاطلاع عليه في 23 سبتمبر 2014

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

5

[ 6 ]

7

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]