يا مية أهلا وسهلا فيكم يا جماعة. اسمي أبو عمر، وبدي أحكيلكم قصة صارت معي قبل كم سنة، يوم كنا شغالين على مشروع طموح شوي. كنا بنبني نظام توصيل باستخدام طائرات بدون طيار (درونز) صغيرة، والحلم كان كبير: نوصل الطلبات بين الأحياء بسرعة وبدون زحمة السير. بس زي ما بقولوا، “مش كلشي بالتمني”.
في البداية، استخدمنا خوارزمية بسيطة عشان الطيارة تلاقي طريقها من المستودع لبيت الزبون. كانت الطيارات المسكينة “بتتخبط”؛ مرات بتلف وبتدور في أماكن غريبة، ومرات بتختار أطول طريق ممكن، كأنها بتستمتع بالمشوار على حساب البطارية! كنا بنشوفها على الخريطة وبنتحسر، وواحد من الشباب صاح فيي مرة: “يا أبو عمر، الدرون تبعنا شكله ضايع زي الأطرش بالزفة!”. كانت معنويات الفريق بالأرض، والمشروع على وشك الفشل. يومها، قعدت مع حالي، وفنجان القهوة السادة بإيدي، وتذكرت أيام الجامعة ومادة الذكاء الاصطناعي… تذكرت “البطل المنسي”، خوارزمية كانت دايماً تبهرني بذكائها: خوارزمية A*.
ما هي مشكلة البحث عن المسار أصلاً؟
قبل ما نغوص في الحل، خلينا نتفق على المشكلة. مشكلة “البحث عن المسار” (Pathfinding) هي ببساطة إيجاد أفضل طريق بين نقطة بداية (أ) ونقطة نهاية (ب). فكر فيها زي لعبة المتاهة، أو لما تستخدم خرائط جوجل عشان تروح على مكان جديد. الهدف مش بس توصل، الهدف توصل بأقصر وقت، أو بأقل تكلفة (بنزين، وقت، طاقة بطارية، إلخ).
في عالم البرمجة، بنمثل الخريطة عادة على شكل “رسم بياني” (Graph) مكون من نقاط (Nodes) ووصلات بينها (Edges)، وكل وصلة إلها “وزن” أو “تكلفة”. والنقاط ممكن تكون تقاطعات شوارع، مربعات في لعبة، أو مواقع جغرافية.
قبل A*: جولة في الخوارزميات “العمياء”
قبل ما أقرر أستخدم A*، كنا جربنا خوارزميات أخرى، ولكل واحدة كانت مشكلتها.
خوارزمية البحث بالاتساع أولاً (Breadth-First Search – BFS)
هذه الخوارزمية مثل الشخص المنظم جدًا اللي ببحث عن مفاتيحه. بيبدأ من نقطة البداية، وبيتفحص كل النقاط المجاورة مباشرة (على بعد خطوة واحدة)، بعدين كل النقاط اللي على بعد خطوتين، وهكذا. هي بتضمنلك تلاقي أقصر طريق من ناحية “عدد الخطوات”، لكنها بتتجاهل “تكلفة” الخطوات. يعني لو في طريق مختصر بس تكلفته أعلى (مثلاً طريق جبلي وعر)، هي رح تتجاهله وتختار الطريق السهل الأطول. مشكلتها الأكبر؟ إنها بطيئة جدًا في الخرائط الكبيرة لأنها بتستكشف كل الاتجاهات بالتساوي.
خوارزمية دكسترا (Dijkstra’s Algorithm)
هون الوضع تحسن شوي. دكسترا أذكى من BFS، لأنها بتاخذ “تكلفة” المسار بعين الاعتبار. هي دايماً بتختار الطريق اللي تكلفته التراكمية أقل حتى الآن. بتضمنلك تلاقي الطريق الأفضل والأقل تكلفة… لكنها لا تزال “عمياء”! كيف يعني؟ يعني ما عندها فكرة وين الهدف موجود. هي بتتمدد في كل الاتجاهات زي بقعة الزيت، وبتضيع وقت وجهد في استكشاف طرق واضحة إنها بتبعدنا عن الهدف. وهذا بالضبط اللي كان يصير مع طياراتنا، كانت تستكشف طرق في شمال المدينة مع إنه بيت الزبون في الجنوب!
نصيحة من أبو عمر: دكسترا ممتازة جدًا لما تكون ما بتعرف وين وجهتك النهائية، وبدك تحسب أقصر طريق من نقطة لكل النقاط الأخرى في الخريطة. لكن لو عندك هدف محدد، فهي مش الخيار الأكفأ.
ولادة البطل: خوارزمية A* (نجمة A)
وهون بيجي دور المنقذ، خوارزمية A*. اللي بيميز A* إنها مش بس بتشوف الطريق اللي قطعته، لأ، هي كمان عندها “حدس” أو “تخمين” عن الطريق المتبقي. هي بتجمع بين دقة دكسترا و”بصيرة” بتوجهها نحو الهدف. هي خوارزمية “مُطّلعة” (Informed Search).
المعادلة السحرية: f(n) = g(n) + h(n)
كل سحر A* يكمن في هذه المعادلة البسيطة. لما الخوارزمية تفكر تنتقل لنقطة جديدة (خلينا نسميها n)، هي بتحسبلها قيمة اسمها f(n) عشان تقرر هل هي خيار جيد أو لا. المعادلة مكونة من جزأين:
- g(n): هي التكلفة الفعلية اللي مشيناها من نقطة البداية لحد النقطة الحالية
n. هذا الجزء هو اللي بتعمله خوارزمية دكسترا. هو يمثل الماضي، الطريق اللي بنعرفه بالتأكيد. - h(n): هي التكلفة “المُقدّرة” أو “المُخمّنة” من النقطة الحالية
nلحد نقطة النهاية. هذا الجزء هو اللي بنسميه “دالة التكهن” أو الـ Heuristic. هو يمثل المستقبل، مجرد تخمين ذكي بيوجهنا.
f(n) هي ببساطة مجموعهم: التكلفة الكلية المُقدّرة للمسار إذا مر من خلال النقطة n. خوارزمية A* في كل خطوة بتختار النقطة اللي عندها أقل قيمة f، يعني النقطة اللي “بتبدو واعدة أكثر”.
كيف نختار دالة التكهن (Heuristic)؟
هذا هو قلب A* النابض. دالة التكهن هي اللي بتعطي الخوارزمية “الإحساس بالاتجاه”. لازم تكون سريعة في الحساب، والأهم، لازم تكون “مقبولة” (Admissible)، يعني لازم لا تبالغ أبداً في تقدير التكلفة. لو قدرت التكلفة بأكثر من الحقيقة، ممكن A* تتجاهل الطريق الأمثل وتختار طريق أسوأ.
أشهر دالتين للتكهن في الخرائط الشبكية:
- مسافة مانهاتن (Manhattan Distance): بنستخدمها لما تكون الحركة مسموحة فقط أفقيًا وعموديًا (زي المشي في شوارع مدينة نيويورك). هي ببساطة مجموع الفرق في الإحداثيات السينية (x) والصادية (y).
- المسافة الإقليدية (Euclidean Distance): هي المسافة المستقيمة بين نقطتين (“كما يطير الغراب”). بنستخدمها لما تكون الحركة مسموحة في كل الاتجاهات.
شوية كود يا جماعة
عشان الصورة توضح أكثر، خلينا نشوف كيف ممكن يبدو شكل خوارزمية A* بالكود (هذا شبه كود بلغة بايثون للتوضيح).
# هذه مجرد بنية توضيحية، وليست كود كامل للنسخ واللصق
def a_star_search(start_node, goal_node):
# قائمة النقاط المفتوحة (اللي لسا ما زرناها بس بنفكر نزورها)
# بنستخدم "طابور أولوية" عشان دايماً نسحب النقطة اللي f(n) تبعها أقل
open_list = PriorityQueue()
open_list.put(start_node, 0)
# قاموس لتتبع المسار
came_from = {}
# قاموس لتخزين تكلفة g(n) لكل نقطة
g_score = {node: float('inf') for node in grid}
g_score[start_node] = 0
# قاموس لتخزين تكلفة f(n) لكل نقطة
f_score = {node: float('inf') for node in grid}
f_score[start_node] = heuristic(start_node, goal_node)
while not open_list.empty():
current = open_list.get() # اسحب النقطة ذات الأولوية القصوى (أقل f_score)
if current == goal_node:
return reconstruct_path(came_from, current) # وجدنا الطريق!
for neighbor in current.get_neighbors():
# g_score المؤقت هو تكلفة الوصول للنقطة الحالية + تكلفة الانتقال للجار
tentative_g_score = g_score[current] + distance(current, neighbor)
# إذا كان هذا المسار للجار أفضل من أي مسار سابق
if tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal_node)
# إذا الجار مش في القائمة المفتوحة، ضيفه
if neighbor not in open_list:
open_list.put(neighbor, f_score[neighbor])
# لم نجد مسارًا
return None
نصيحة من أبو عمر: أهم جزء في تطبيق A* هو استخدام هيكل بيانات مناسب للقائمة المفتوحة (Open List). استخدام قائمة عادية والبحث فيها عن العنصر الأقل في كل مرة هو أمر كارثي من ناحية الأداء. استخدم دائمًا “طابور أولوية” (Priority Queue) أو (Min-Heap)، فهذا سيحدث فرقًا هائلاً في السرعة.
الخلاصة: من المتاهة إلى الطريق السريع 💡
لما طبقنا خوارزمية A* في مشروع الدرونز، كانت النتيجة مثل السحر. الطيارات صارت بتتحرك بـ”ذكاء”، بتتجنب الطرق الطويلة بشكل استباقي، وبتسلك مسارات شبه مثالية نحو أهدافها. تحولت الخرائط من متاهات محبطة إلى طرق سريعة وواضحة. وفرنا في طاقة البطارية، وقللنا وقت التوصيل، والأهم، رجعت الثقة للفريق والمشروع.
خوارزمية A* هي مثال رائع على كيف يمكن لمفهوم رياضي أنيق أن يحل مشاكل عملية معقدة. هي حجر أساس في تطوير الألعاب (لتحريك الأعداء والشخصيات)، وفي الروبوتات، واللوجستيات، وحتى في توجيه حزم البيانات عبر الشبكات.
لهيك نصيحتي إلكم: لا تستهينوا بقوة الخوارزميات الأساسية. افهموها جيدًا، اعرفوا متى تستخدمون كل واحدة منها، وما تخافوا من “شوية” رياضيات. يلا يا جماعة، ما تخلوا مشاريعكم تضيع في المتاهة. استخدموا عقلكم وحدسكم، زي ما بتعمل A* بالضبط. ويعطيكم ألف عافية! 💪
