تعمل خوارزمية جديدة على حل النقطة العمياء التي كانت تتحدى علماء الكمبيوتر منذ عام 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مشاهدة عالم الكمبيوتر يدفع خوارزمية عام 1996 إلى ما هو أبعد من حدودها الطويلة الأمد
يذكر بـأن الموضوع التابع لـ عالم الكمبيوتر يدفع خوارزمية عام 1996 إلى ما هو أبعد من حدودها الطويلة الأمد قد تم نشرة ومتواجد على قد تم نشرة اليوم ( ) ومتواجد على بتوقيت بيروت_ beiruttime ( لبنان ) وقد قام فريق التحرير في برس بي بالتاكد منه وربما تم التعديل علية وربما قد يكون تم نقله بالكامل اوالاقتباس منه ويمكنك قراءة ومتابعة مستجدادت هذا الخبر او الموضوع من مصدره الاساسي.
التفاصيل من المصدر - اضغط هنا :::
وختاما نتمنى ان نكون قد قدمنا لكم من موقع Pressbee تفاصيل ومعلومات، عالم الكمبيوتر يدفع خوارزمية عام 1996 إلى ما هو أبعد من حدودها الطويلة الأمد.
في الموقع ايضا :