تم إخفاء خوارزمية جديدة لفحص التقاطعات في الرسوم البيانية على مرأى من الجميع

وجد اثنان من علماء الكمبيوتر فكرة في مكان غير متوقع للغاية والتي كانت مفيدة لهم فقط لتحقيق اختراق في نظرية الرسم البياني

في أكتوبر 2019، يعقوب هولم و إيفا روتنبرغ و أثناء تصفحي عمل كانت قد نشرت قبل بضعة أشهر - وأدركت فجأة أنها قد عثر عليها شيء خطير.



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



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



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



قال جوزيبي إيتاليانو ، عالم الكمبيوتر بجامعة لويس ، المؤلف المشارك لورقة بحثية عام 1996 تصف الآن ثاني أسرع خوارزمية: "الخوارزمية الجديدة بارعة حقًا" . "عندما شاركت في كتابة هذا العمل ، لم أكن أعتقد أن هذا يمكن أن يحدث".



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



في عام 1913 ، ظهرت الرسوم البيانية المستوية في لغز "مجتمعي" معقد حول ثلاثة منازل ، نُشر في مجلة The Strand Magazine. طلب المنشور من القراء وضع اتصالات لثلاثة منازل ، وربط كل منها بثلاث حاملات للطاقة - الماء والغاز والكهرباء - حتى لا تتقاطع الاتصالات مع بعضها البعض. لا يستغرق الأمر وقتًا طويلاً حتى ندرك أن هذه المهمة لا يمكن التغلب عليها.



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



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



قال هولم: "إنه أفضل بكثير من فحص كل شيء من البداية في كل مرة ، ولكنه ليس مثاليًا".



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



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



على سبيل المثال ، يمكن تغيير الشكل أ إلى الشكل ب عن طريق قلب المثلث الذي يشكل الرؤوس 1 و 2 و 3 بالنسبة إلى الحافة التي تربط بين الرؤوس 2 و 3. ويمكن أيضًا قلب قمة الشكل ب بالنسبة إلى الرؤوس 4 و 5 ، مما يؤدي إلى الشكل ج. بشكل مختلف ، ولكن تشير إلى نفس الرسم البياني.







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







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



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



"لقد أدركنا بسرعة كبيرة أنه من خلال هذا التحليل الجديد يمكن حل المشكلة

قال هولم: "خوارزمية بسيطة للغاية من حيث المفهوم".





Jacob Holm و Eva Rothenberg تقوم



الخوارزمية الجديدة بعكس اتجاه واحد في كل مرة بحثًا عن حل. نتيجة لذلك ، يحدث أحد أمرين: إما أن تجد الخوارزمية طريقة لإدخال الحافة المطلوبة ، أو أن الوجه التالي يلغي السابقة - وبعد ذلك تستنتج الخوارزمية أنه لا توجد طريقة لإضافة حافة جديدة.



أوضح روتنبرغ: "نسمي هذه الخوارزمية بالجشع الكسول". "يقوم فقط بإجراء التغييرات اللازمة لاستيعاب الضلع الجديد."



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



لكن بالنسبة إلى هولم وروثنبرغ ، فإن سرعة الخوارزمية ليست بنفس أهمية الأفكار التي سرعتها. قال روتنبرغ: "هناك عواقب فورية من هذا الفهم".



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



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