مانوج غوبتا يتجاوز عائقًا يعود إلى 1996 في خوارزميات أقصر المسارات

طوّر الباحث مانوج غوبتا من المعهد الهندي للتكنولوجيا في غاندي ناغار (IIT Gandhinagar) خوارزمية تقدّر المسافات في الشبكات الضخمة بدقة أكبر ودون زيادة زمن الحساب. ويتجاوز هذا العمل قيدًا ظل يعيق التقدم في هذا المجال من علوم الحاسوب منذ عام 1996.

مسألة APSP والعائق القديم

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

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

أخذ العينات متعدد المقاييس

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

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

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