🎛️ دييكسترا أثناء العمل
نقطة الانطلاق هي A، والهدف هو H. انقر على «خطوة» لمشاهدة الخوارزمية تستكشف المبيان رأسًا برأس. تتحدّث المسافات الدنيا في الزمن الحقيقي.
الخطوة
0
الرأس الحالي
—
المسافة A→H
∞
ابدأ بـ A عند المسافة 0، وكل الرؤوس الأخرى عند ∞. انقر «خطوة» للاستكشاف.
☕ 1956: دييكسترا ومقهاه في أمستردام
إدسخر فيبه دييكسترا (1930-2002)، عالم حاسوب هولندي، يروي بنفسه ولادة خوارزميته: صباح يوم من عام 1956، في مقهى بأمستردام، كان عليه أن يُبيّن لصحفيين ما يستطيع ARMAC (أحد أوائل الحواسيب الهولندية) القيام به. فاختار أن يحسب أقصر طريق بين مدينتين في هولندا.
يقول إنه صمّم الخوارزمية في 20 دقيقة، دون ورق ولا قلم. ولم تُنشر إلا في عام 1959 في مقال من 3 صفحات، وأصبحت إحدى أكثر الخوارزميات استعمالًا في العالم.
🎯 المسألة: طريق بوزن أدنى
لِيُعطَ مبيان موزون (كل حافة لها وزن ≥ 0، مثلًا مسافة أو زمن). انطلاقًا من رأس انطلاق s، نريد إيجاد الطريق ذي الوزن الإجمالي الأدنى نحو كل رأس آخر.
🧠 الفكرة المركزية: الاستكشاف بمسافة متزايدة
تحتفظ خوارزمية دييكسترا بمجموعتين: الرؤوس «النهائية» (المسافة الدنيا المعروفة بيقين) والرؤوس «قيد الانتظار» (بتقدير مؤقت). في كل خطوة:
- اختيار الرأس قيد الانتظار ذي أصغر تقدير.
- تعليمه كرأس نهائي.
- لكل جار من جيرانه لا يزال قيد الانتظار، نقوم بـالتخفيف:
إذا كان dist[u] + poids(u, v) < dist[v]، فإن dist[v] = dist[u] + poids(u, v). - نعيد الكرّة حتى يُعلَّم الوجهة كرأس نهائي.
الشيفرة الزائفة (Pseudo-code)
dist[s] = 0; dist[v] = ∞ pour tout v ≠ s
Q = ensemble de tous les sommets
tant que Q non vide :
u = sommet de Q minimisant dist[u]
retirer u de Q
pour chaque voisin v de u :
si dist[u] + poids(u,v) < dist[v] :
dist[v] = dist[u] + poids(u,v)
prédécesseur[v] = u
🛡️ لماذا تعمل: ثابتة دييكسترا
عندما نُخرج رأسًا u من الكومة (ذا أصغر تقدير)، فإن هذا التقدير هو في الواقع المسافة الدنيا الحقيقية. برهان حدسي: أي طريق آخر نحو u يجب أن يمرّ عبر رأس لا يزال في Q (أي بمسافة ≥ dist[u]) زائدَ حافة بوزن موجب. إذن أطول. إنها شرط الأوزان الموجبة أو المنعدمة هو ما يجعل دييكسترا صحيحة.
بالنسبة للأوزان السالبة، قد تخطئ دييكسترا. عندئذٍ نستعمل بلمان-فورد (1958، أبطأ: O(VE)) أو جونسون (يجمع بينهما لجميع الأزواج).
⚡ التعقيد: O((V + E) log V)
بتنفيذ جيد (طابور الأولوية = كومة ثنائية)، تشتغل دييكسترا في O((V + E) log V) حيث V = الرؤوس، E = الحواف. بالنسبة لمبيان طرقي أوروبي (~50 مليون رأس، ~150 مليون حافة)، يُحسَب ذلك في بضع ميلي ثانية.
بـكومة فيبوناتشي (فريدمان-تارجان 1984)، ننزل إلى O(E + V log V). رائعة نظريًا، لكن عمليًا الكومة الثنائية أسرع بسبب الثوابت المخفية.
🚀 تطبيقات ضخمة
- نظام تحديد المواقع والملاحة: خرائط غوغل، وويز، وخرائط آبل، وتومتوم، وOpenStreetMap كلها تستعمل صيغًا مشتقة من دييكسترا (غالبًا مُعزَّزة بـ A* بمساعدة استدلال جغرافي).
- توجيه الإنترنت: بروتوكول OSPF (Open Shortest Path First)، المستعمَل من قِبل معظم موجِّهات IP، يحسب الطرق المثلى عبر دييكسترا. وكذلك بروتوكول IS-IS (المستعمَل من قِبل مزودي الخدمة من الدرجة الأولى).
- ألعاب الفيديو: تتبع المسار للشخصيات غير اللاعبة، والذكاء الاصطناعي للاستراتيجيات. ستار كرافت، وسيفيلايزيشن، وإيج أوف إمبايرز، وماين كرافت، وGTA — كلها تعتمد على دييكسترا أو A* (صيغة مشتقة).
- الروبوتيك: الروبوتات الذاتية، والطائرات المسيّرة، والسيارات ذاتية القيادة. تخطيط المسارات في فضاء مُجزَّأ.
- الشبكات الاجتماعية: حساب «المسافة» بين شخصين (نظرية الدرجات الست). يعرض لينكدإن طريقك نحو أي جهة اتصال.
- الشبكات الهاتفية: توجيه المكالمات بالمرور عبر المقاسم الأقل تحميلًا.
- اللوجستيك: تحسين جولات التوصيل (UPS، وFedEx، وأمازون)، وتخطيط الرحلات الجوية، وجدولة المهام.
- البيولوجيا: محاذاة تسلسلات الحمض النووي ADN، وأقصر طريق في الأشجار التطورية، وطيّ البروتينات.
- المالية: كشف فرص المراجحة في مبيانات العملات (مدمجًا مع بلمان-فورد للدورات السالبة).
- المترجمات: تحسين الشيفرة، وتحليل تدفق المعطيات.
🚀 صيغ ومُحسّنات
- A* (هارت، ونيلسون، ورافائيل 1968): تضيف استدلالًا (مثلًا المسافة الجوية نحو الهدف) لتوجيه البحث. أسرع بكثير في المبيانات الجغرافية.
- ثنائية الاتجاه: تُطلق دييكسترا اثنتين في آن واحد، إحداهما من A، والأخرى من B، وتتوقف عندما تلتقيان. تقسم الزمن على 2 في المتوسط.
- التسلسلات الهرمية للانكماش (Contraction Hierarchies) (2008، جامعة كارلسروه): حساب مسبق للمبيان الطرقي يجعل الاستعلامات أسرع بـ 10000 مرة. مستعمَل من قِبل OpenStreetMap.
- ALT (A* + معالم + متباينة مثلثية): استدلال متطور للمبيانات الكبيرة جدًا.
- متعدد الأهداف: إيجاد التوازن بين الزمن/المسافة/الرسوم. صعب من نوع NP عمومًا، لكنه مُقرَّب عمليًا.
🎓 دييكسترا الإنسان: عقل لاذع
لم يتوقف دييكسترا عند خوارزميته. فقد نال جائزة تورينغ عام 1972 (ما يعادل نوبل في علوم الحاسوب). وهو أيضًا صاحب أقوال أسطورية:
- «اختبار البرامج يمكنه أن يُثبت وجود العلل، لا غيابها أبدًا.»
- «مسألة معرفة ما إذا كان الحاسوب يستطيع التفكير ليست أكثر إثارة للاهتمام من مسألة معرفة ما إذا كانت الغواصة تستطيع السباحة.»
- «GO TO considered harmful» (1968) — مقال أزال تعليمة goto من البرمجة الحديثة.
- «الجمال مهنتنا» (شعار قسم علوم الحاسوب بإيندهوفن).
📐 الرابط مع برنامجك الدراسي
- الخوارزميات: دييكسترا هي النموذج الأصلي للخوارزميات الجشعة (gloutons) التي تقوم في كل خطوة بالاختيار الأمثل محليًا وتحصل على الأمثل الشامل. إنها إحدى الاستراتيجيات الخوارزمية الأساسية.
- التراجع والثوابت: يعتمد برهان الصحة على ثابتة حلقة، وهي تقنية مرئية في البرهان بالترجع (برنامج TS).
- طوابير الأولوية: بنية معطيات مرئية في الأقسام التحضيرية للمعلوميات.
- المتباينات المثلثية: الخاصية d(s, v) ≤ d(s, u) + poids(u, v) هي نظير المبيان للمتباينة المثلثية في الهندسة.
- الأمثلة (التحسين): دييكسترا حالة خاصة من البرمجة الديناميكية على مبيان لا دوري. مفهوم مركزي في بحوث العمليات.