العلماء ينشئون أفضل خوارزمية لاجتياز الخريطة

وقال إريك ديمين، عالم الكمبيوتر في معهد ماساتشوستس للتكنولوجيا: “إنها خوارزمية رائعة”. “إنه سريع جدًا وبسيط وسهل التنفيذ.”

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

استخدمت ورقة ديكسترا بنية بيانات بسيطة تركت مجالًا للتحسين. وفي العقود التالية، طور الباحثون أكوامًا أفضل، أطلقوا عليها اسم «الأكوام»، حيث يسهل العثور على عناصر معينة أكثر من غيرها. إنهم يستفيدون من حقيقة أن خوارزمية Dijkstra تحتاج فقط إلى إزالة الإدخال الخاص بأقرب قمة متبقية. قال فاتسلاف روزهون، الباحث في معهد علوم الكمبيوتر والذكاء الاصطناعي والتكنولوجيا (INSAIT) في صوفيا، بلغاريا: “الكومة هي في الأساس بنية بيانات تسمح لك بالقيام بذلك بسرعة كبيرة”.

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

أفضل سلوك

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

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