خوارزمية جديدة تجعل العثور على أقصر المسارات أسرع

النسخة الأصلية ل هذه القصة ظهرت في مجلة كوانتا.

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

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

قال ميكيل ثوروب، عالم الكمبيوتر في جامعة كوبنهاجن: «أقصر المسارات مشكلة جميلة يمكن لأي شخص في العالم أن يتعامل معها.

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

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

وقال روبرت تارجان، عالم الكمبيوتر في جامعة برينستون: “كان المؤلفون جريئين في التفكير في أنهم قادرون على كسر هذا الحاجز”. “إنها نتيجة مذهلة.”

حدود المعرفة

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

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