يا أهلاً وسهلاً فيكم يا جماعة. اسمي أبو عمر، وبشتغل في عالم البرمجة والذكاء الاصطناعي من سنين طويلة، شفت فيها الحلو والمر، و”أكلت المقلوبة من إيدين كل الخوارزميات” زي ما بنقول. اليوم بدي أحكيلكم قصة صارت معي قبل فترة، قصة عن الفوضى، والتكلفة العالية، وعن خوارزمية بسيطة وعبقرية أنقذت الموقف.
كنت بشتغل مع شركة ناشئة صغيرة في مجال التوصيل واللوجستيات. شغلهم كان بيعتمد على توصيل بضائع من مستودع مركزي لعدة نقاط في المدينة. في البداية، كان عدد الطلبات قليل، وكان السواق “أبو فلان” يعتمد على خبرته في الشوارع ويختار طريقه “على البركة”. لكن مع الوقت، كبرت الشركة وزادت الطلبات، وهون بلشت المشاكل.
صارت الشكاوى تزيد: “الطلب اتأخر”، “السواق ضيّع الطريق”، “وصلت البضاعة متأخرة”. والأهم من كل هاد، فاتورة البنزين والصيانة لسيارات التوصيل صارت “تكسر الظهر”. قعدت مع مدير الشركة، وكان ماسك راسه وبيقول: “يا أبو عمر، مش عارفين شو نعمل، بنخمن تخمين، وكل يوم بنخسر مصاري ووقت. السواقين كل واحد ماشي على كيفه!”.
وقتها، لمعت في بالي أيام الجامعة ومحاضرات هياكل البيانات اللي كان الدكتور يشرحها على لوح أخضر مغبر. تذكرت رسمات الدوائر والخطوط، وتذكرت اسم غريب رن في أذني: “دكسترا”. قلت للمدير: “الحل موجود، مش بالسحر ولا بالشعوذة، الحل في خوارزمية عمرها أكثر من 60 سنة!”. نظر إلي نظرة غريبة، لكني كنت واثقًا أننا وجدنا بداية الخيط.
ما هي “الجرافز” (Graphs) يا جماعة؟
قبل ما نحكي عن البطل “دكسترا”، لازم نفهم الملعب اللي بيلعب فيه. هذا الملعب اسمه “الجراف” أو المخطط البياني (Graph). ببساطة شديدة، الجراف هو مجرد مجموعة من النقاط (Nodes أو Vertices) متصلة ببعضها عن طريق خطوط (Edges).
تخيلها معي هيك:
- النقاط (Nodes): ممكن تكون مدن على خريطة، أجهزة كمبيوتر في شبكة، أشخاص في شبكة اجتماعية، أو حتى محطات في مشروع توصيل زي مشروع صاحبنا.
- الخطوط (Edges): هي العلاقات اللي بتربط هاي النقاط. ممكن تكون طرق بين المدن، كوابل بين أجهزة الكمبيوتر، أو الشوارع اللي بتوصل بين المستودع ونقاط التسليم.
لكن القصة ما بتخلص هون. في معظم الأحيان، هاي الخطوط إلها “وزن” أو “تكلفة” (Weight). هاي التكلفة ممكن تكون المسافة بالكيلومترات، أو الوقت اللازم لقطع الطريق، أو حتى تكلفة نقل البيانات في شبكة. وهون بصير اسمه “جراف موزون” (Weighted Graph)، وهو النوع اللي بهمنا اليوم. زي ما بنقول، كل الطرق بتأدي للطاحونة… بس مش كل الطرق بنفس الطول والتكلفة!
لقاء البطل: خوارزمية دكسترا (Dijkstra)
بعد ما جهزنا الملعب، صار وقت ندخل البطل: خوارزمية دكسترا. هذه الخوارزمية، اللي ابتكرها العالم الهولندي إدسخر دكسترا عام 1956، هي أداة رائعة لإيجاد أقصر مسار بين نقطة بداية (Source) وكل النقاط الأخرى في جراف موزون (بشرط مهم راح نحكيه بعدين).
كيف تشتغل الخوارزمية “بالبلدي”؟
فكرة دكسترا بسيطة بشكل مدهش. تخيل إنك واقف في بيتك (نقطة البداية) وبدك تعرف أقصر طريق لكل مكان في المدينة. الخوارزمية بتشتغل كالتالي:
- التحضير: بتعمل جدول تسجل فيه أقصر مسافة معروفة من بيتك لكل مكان في المدينة. في البداية، المسافة لبيتك هي صفر، والمسافة لأي مكان ثاني هي “ما لا نهاية” (لأنك لسا ما بتعرف أي طريق).
- البداية: ابدأ من بيتك. شوف كل الأماكن المتصلة فيه مباشرة (الجيران). احسب المسافة لكل جار وسجلها في الجدول.
- الخطوة الذكية: من كل الأماكن اللي لسا ما “زرتها” بشكل نهائي، اختار المكان اللي عنده أقصر مسافة مسجلة في جدولك.
- التحديث: روح على هاد المكان الجديد، وشوف جيرانه. لكل جار، احسب المسافة الإجمالية من بيتك (مرورًا بالمكان اللي أنت فيه الآن). إذا كانت هاي المسافة الجديدة أقصر من المسافة المسجلة في الجدول لهذا الجار، حدثها فورًا!
- التكرار: كرر الخطوتين 3 و 4. في كل مرة، بتختار أقرب نقطة لم تُستكشف بالكامل، وتُحدّث مسافات جيرانها. استمر في العملية حتى تزور كل الأماكن اللي بدك ياها.
بالنهاية، جدولك راح يحتوي على أقصر مسار من بيتك لكل نقطة في الجراف. بسيطة وعبقرية!
مثال عملي: من مدينة “أ” إلى مدينة “هـ”، أقصر طريق لو سمحت!
حكي بدون تطبيق زي الشاي بدون نعنع، ما إله طعم. خلينا ناخد مثال بسيط. عنا شبكة من 6 مدن (أ, ب, ج, د, هـ, و)، والمسافات (التكلفة) بينهم موضحة في هاي الصورة (تخيل معي الرسمة):
- أ -> ب (7)
- أ -> ج (9)
- أ -> و (14)
- ب -> ج (10)
- ب -> د (15)
- ج -> د (11)
- ج -> و (2)
- د -> هـ (6)
- و -> هـ (9)
بدنا نلاقي أقصر طريق من “أ” إلى “هـ”.
خطوة 1: نبدأ من “أ”. المسافة إلى “أ” هي 0. المسافة لكل المدن الأخرى هي ∞.
خطوة 2: نختار “أ”. جيرانها هم “ب”، “ج”، “و”. نحدث المسافات:
- المسافة إلى “ب” = 7
- المسافة إلى “ج” = 9
- المسافة إلى “و” = 14
خطوة 3: من المدن غير المزارة (ب, ج, و, د, هـ)، نختار الأقرب. هي “ب” بمسافة 7. نعتبرها “مُزارة”.
خطوة 4: من “ب”، ننظر إلى جيرانها (أ, ج, د). “أ” تمت زيارتها.
- المسافة إلى “ج” عبر “ب”: 7 (من أ إلى ب) + 10 (من ب إلى ج) = 17. المسافة الحالية لـ”ج” هي 9. بما أن 17 > 9، لا نغير شي.
- المسافة إلى “د” عبر “ب”: 7 + 15 = 22. نسجل 22 كأقصر مسافة معروفة لـ”د”.
خطوة 5: من المدن غير المزارة (ج, و, د, هـ)، نختار الأقرب. هي “ج” بمسافة 9. نعتبرها “مُزارة”.
خطوة 6: من “ج”، ننظر إلى جيرانها (أ, ب, د, و). “أ” و “ب” تمت زيارتهم.
- المسافة إلى “د” عبر “ج”: 9 (من أ إلى ج) + 11 (من ج إلى د) = 20. المسافة الحالية لـ”د” هي 22. بما أن 20 < 22، نحدّث المسافة لـ"د" لتصبح 20.
- المسافة إلى “و” عبر “ج”: 9 + 2 = 11. المسافة الحالية لـ”و” هي 14. بما أن 11 < 14، نحدّث المسافة لـ"و" لتصبح 11.
نستمر هكذا…
في النهاية، سنجد أن أقصر مسار من “أ” إلى “هـ” هو: أ -> ج -> و -> هـ بتكلفة إجمالية 20 (9 + 2 + 9). بينما الطريق الآخر الذي بدا ممكنًا (أ -> ج -> د -> هـ) تكلفته 26.
الكود يا مبرمج: لنكتب خوارزمية دكسترا مع بعض
الحكي النظري ممتاز، لكن “الشغل نظيف” لما نشوف الكود. خلينا نطبق هذا الكلام بلغة بايثون، لأنها سهلة وواضحة.
تجهيز البيئة: تمثيل الجراف في بايثون
أفضل طريقة لتمثيل جراف موزون هي باستخدام قاموس (Dictionary) حيث يكون المفتاح هو النقطة، والقيمة هي قاموس آخر يحتوي على الجيران والتكلفة.
# تمثيل الجراف الخاص بمثالنا
graph = {
'أ': {'ب': 7, 'ج': 9, 'و': 14},
'ب': {'أ': 7, 'ج': 10, 'د': 15},
'ج': {'أ': 9, 'ب': 10, 'د': 11, 'و': 2},
'د': {'ب': 15, 'ج': 11, 'هـ': 6},
'و': {'أ': 14, 'ج': 2, 'هـ': 9},
'هـ': {'د': 6, 'و': 9}
}
كود الخوارزمية خطوة بخطوة
سنستخدم مكتبة heapq في بايثون، والتي توفر لنا “طابور أولوية” (Priority Queue) فعال جدًا. هذا يجعل الخوارزمية أسرع بكثير لأنه يساعدنا دائمًا في العثور على النقطة ذات المسافة الأقل بكفاءة عالية.
import heapq
def dijkstra(graph, start_node):
# 1. التحضير
# قاموس لتخزين أقصر مسافة معروفة لكل نقطة
distances = {node: float('infinity') for node in graph}
distances[start_node] = 0
# قاموس لتتبع المسار
previous_nodes = {node: None for node in graph}
# طابور الأولوية، نخزن فيه (المسافة, النقطة)
priority_queue = [(0, start_node)]
while priority_queue:
# 2. الخطوة الذكية: اختيار أقرب نقطة
current_distance, current_node = heapq.heappop(priority_queue)
# إذا وجدنا مسار أقصر بالفعل، نتجاهل هذا المسار
if current_distance > distances[current_node]:
continue
# 3. التحديث: استكشاف الجيران
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# إذا وجدنا مسارًا جديدًا أقصر...
if distance '.join(shortest_path)}")
مش بس خرائط وجوجل مابس: وين كمان بنستخدم دكسترا؟
“المبرمج الشاطر مش اللي حافظ أكواد، المبرمج الشاطر اللي بعرف أي أداة يستخدم ومتى.” – من كيس أبو عمر
خوارزمية دكسترا مش مجرد تمرين أكاديمي. هي قلب نابض في كثير من الأنظمة اللي بنستخدمها كل يوم:
- توجيه الشبكات (Network Routing): بروتوكولات مثل OSPF تستخدم دكسترا لتحديد أسرع مسار لإرسال حزم البيانات عبر الإنترنت.
- الخدمات اللوجستية والتوصيل: مثل قصة صاحبنا، تُستخدم لتحسين مسارات السائقين وتوفير الوقت والوقود.
- أنظمة الطيران: لإيجاد أرخص أو أسرع مسار للرحلات الجوية (مع الأخذ بالاعتبار تكلفة الرحلات بين المطارات).
- الشبكات الاجتماعية: يمكن استخدامها لإيجاد “أقصر سلسلة من المعارف” بين شخصين.
- الذكاء الاصطناعي وتخطيط المسار للروبوتات: لمساعدة الروبوت على التنقل في بيئته بأقل تكلفة ممكنة (زمن، طاقة).
نصائح من “الختيار”: خبايا الشغل مع دكسترا
بعد سنين من الشغل، تعلمت كم شغلة عن دكسترا بحب أشاركها معكم:
- احذر من الأوزان السالبة: دكسترا تفترض أن كل تكاليف المسارات (الأوزان) إيجابية. لو عندك وزن سالب (مثلاً، مسار بيعطيك طاقة بدل ما يستهلكها)، دكسترا راح “تتخربط” وممكن تدخل في حلقة لا نهائية. في هاي الحالة، لازم تستخدم خوارزمية ثانية مثل Bellman-Ford.
- هياكل البيانات هي المفتاح: استخدام قائمة عادية بدل طابور الأولوية (Priority Queue) راح يخلي خوارزميتك بطيئة جداً مع الجرافات الكبيرة. الفرق في الأداء هائل، فدائماً استخدم الأداة الصح.
- العالم الحقيقي أعقد: دكسترا بتعطيك أقصر مسار بناءً على تكلفة ثابتة. في الواقع، تكلفة الطريق (الوقت) بتتغير بسبب زحمة السير. هنا تأتي خوارزميات أكثر تطوراً مثل A* (A-Star)، التي هي في جوهرها نسخة محسنة من دكسترا تستخدم “حدسًا” (Heuristic) لتوجيه البحث بشكل أذكى.
الخلاصة: من التخمين إلى اليقين 💡
نرجع لقصة الشركة الناشئة. بعد ما طبقنا نظام بسيط يعتمد على خوارزمية دكسترا لتحديد مسارات التوصيل اليومية، كانت النتائج مذهلة. انخفضت تكاليف الوقود بنسبة تقارب 20%، زاد رضا العملاء بشكل ملحوظ بسبب دقة مواعيد التسليم، والأهم من كل هذا، ارتاحت الإدارة من صداع التخمين اليومي.
ما فعلناه لم يكن سحراً، بل كان تطبيقاً لمبدأ أساسي في علوم الحاسوب. هذا هو جمال الخوارزميات: تحويل مشكلة فوضوية ومعقدة إلى مسألة منطقية لها حل مثالي. فهم هذه الأدوات الأساسية هو ما يميز المبرمج الذي يحل المشاكل عن مجرد كاتب أكواد.
فهم الخوارزميات مش رفاهية، هو أساس شغلنا وقوتنا كمطورين. يلا، شدوا حيلكم يا شباب، وخلينا نبني أشياء عظيمة. 💪
