— بيروت 📱 حمّل التطبيق
عاجل
عاجل: ولايتي: هذه الفجوة في البحرين لن ترممها المظلّة الأمنية الأميركية المتهالكة ولا سراب التطبيع مع “إسرائيل”عاجل: القوات المسلحة اليمنية: نعلن ان المركز المالي في مدينة الملك عبدالله الاقتصادية في عاصمة العدوان السعودي الرياض هدفا عسكريا لقواتناعاجل: ولايتي: في الخطاب الإسلامي الأصيل تنبع الأصالة والشرعية السياسية من إرادة الشعب ولا يمكن أن تستمر دون رضاهعاجل: القوات المسلحة اليمنية: ردا على استهداف العدوان السعودي لمحطتي صعدة والمخا الكهربائيتين نعلن أن محطة الشقيق الكهربائية ستكون هدفا مشروعا لقواتنا في الساعات القادمةعاجل: مصادر فلسطينية: شهيدة وإصابتان جراء قصف مدفعي للاحتلال استهدف منزلًا شرقي مخيم المغازي وسط قطاع غزةعاجل: مصادر يمنية: غارة لطيران العدوان السعودي على محطة الكهرباء بمدينة المخاعاجل: مراسل المنار في غزة: إصابة خطيرة جراء قصف دبابة اسرائيلية شقة سكنية شمال مخيم المغازي وسط القطاععاجل: القوات المسلحة اليمنية تعلن ان ميناء جدة وجميع موانئ العدوان السعودي في ساحل البحر الأحمر ستكون هدفا لقواتها في حال نفذ العدو تهديداته بقصف ميناء الحديدة
العلوم و التكنولوجيا

عالم الكمبيوتر يدفع خوارزمية عام 1996 إلى ما هو أبعد من حدودها الطويلة الأمد

عالم الكمبيوتر يدفع خوارزمية عام 1996 إلى ما هو أبعد من حدودها الطويلة الأمد

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

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

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

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

لماذا تطغى الشبكات الضخمة على أجهزة الكمبيوتر؟

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

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

في عام 1996، قدم دور وهالبرين وزويك طريقة مؤثرة توصلت إلى “تقريب 2” في الوقت الأمثل تقريبًا. ولن يتجاوز تقديرها ضعف أقصر مسافة حقيقية. إذا كان هناك موقعان يفصل بينهما مسافة 10 كيلومترات (6.2 ميل)، على سبيل المثال، فإن المسافة المبلغ عنها ستتراوح بين 10 و20 كيلومترًا (6.2 و12.4 ميلًا).

اختصار سريع مع نقطة عمياء

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

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

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

قدم مانوج جوبتا، الأستاذ المشارك في المعهد الهندي للتكنولوجيا جانديناجار، حلاً جديدًا في الندوة السنوية السادسة والستين حول أسس علوم الكمبيوتر (FOCS 2025).

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

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

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

أسس أقوى للأنظمة المتصلة

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

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

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

المرجع: “تحسين أقصر المسارات التقريبية لأزواج القمم القريبة” بقلم مانوج جوبتا، 14-17 ديسمبر 2025، الندوة السنوية السادسة والستون لـ IEEE لعام 2025 حول أسس علوم الكمبيوتر (FOCS).
دوى: 10.1109/FOCS63196.2025.00065

لا تفوت أي اختراق: انضم إلى النشرة الإخبارية SciTechDaily.
تابعونا على جوجل و أخبار جوجل.

المصدر:
scitechdaily.com
بقلم

فريق التحرير

حساب النشر الجماعي لموقع بتوقيت بيروت، الذي تديره The Verificat Agency بإدارة محمد قاسم. ينشر الأخبار والمتابعات المنسوبة إلى مصادرها، ويستخدم أدوات مساعدة في الجلب والترجمة والنشر. هذه التسمية لا تشير إلى صحافي فرد. معلومات الإدارة وسياسة التحرير والتواصل والتصحيحات متاحة في صفحة فريق التحرير.

جميع مقالات الكاتب ←
↑
الخروج من نسخة الجوال