مساراتي كانت عشوائية ومكلفة: كيف أنقذتني خوارزمية A* (A-Star) من جحيم التخطيط غير الفعال؟

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

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

في ليلة من الليالي، وأنا بقلّب في أوراقي وكتبي القديمة، وقعت عيني على اسم خوارزمية كنت درستها زمان في الجامعة: A* (A-Star). تذكرت وقتها إنها خوارزمية مخصصة لإيجاد أقصر المسارات. قلت لحالي “خلينا نجرب، ما إحنا خسرانين إشي”. قضيت الليلة أقرأ عنها وأطبقها، وفي اليوم التالي، كانت اللحظة الحاسمة. شغّلت “زيتون” بالكود الجديد… يا الله! تحرك بخطوات واثقة، كأنه يعرف الطريق من أول. تجنب العوائق بذكاء، وسلك أقصر طريق ممكن للهدف مباشرة. وقتها عرفت إني وجدت الكنز المفقود. هذه الخوارزمية لم تنقذ مشروعي فقط، بل فتحت عيوني على عالم كامل من البحث والتخطيط الذكي.

ما هي خوارزمية A* (A-Star)؟ وليش هي “نجمة” الخوارزميات؟

خلونا نبسط الأمور. تخيل إنك في مدينة كبيرة وبدك تروح من بيتك (نقطة البداية) لمكتبة (نقطة الهدف)، وعندك خريطة. كيف بتختار طريقك؟

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

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

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

1. ما قطعته حتى الآن: كم المسافة اللي مشيتها فعلًا من بيتك.
2. ما أتوقع أن أقطعه: كم المسافة المتبقية *تقريبًا* للوصول إلى المكتبة (كخط مستقيم مثلًا).

بدمج هذين العاملين، تستطيع A* اتخاذ قرارات ذكية جدًا، وتجاهل المسارات الواضح أنها سيئة، والتركيز على المسارات الواعدة. لهذا السبب هي مستخدمة بكثرة في ألعاب الفيديو (لتحريك الأعداء والوحدات)، أنظمة الملاحة (زي خرائط جوجل)، الروبوتات، والعديد من تطبيقات الذكاء الاصطناعي.

المعادلة السحرية: كيف تفكر A*؟

قلب خوارزمية A* النابض هو معادلة بسيطة لكن عبقرية. لكل نقطة (أو مربع في الخريطة) تريد الخوارزمية تقييمها، تحسب لها قيمة اسمها f(n):

f(n) = g(n) + h(n)

يا لطيف! شو هالحكي؟ ولا يهمك، بسيطة جدًا. خلينا نفصصها حبة حبة:

g(n): التكلفة الفعلية من البداية (المشوار اللي قطعته)

الـ g(n) هي ببساطة التكلفة الحقيقية للمسار من نقطة البداية إلى النقطة الحالية n. لو كل خطوة في المتاهة تبعتنا تكلفتها 1، والنقطة n تبعد 5 خطوات عن البداية، إذن g(n) = 5. هذا الجزء يضمن أن الخوارزمية تأخذ بعين الاعتبار المسافة التي قطعتها بالفعل، تمامًا مثل خوارزمية Dijkstra.

h(n): التكلفة التقديرية للوصول للهدف (التخمين الذكي)

هنا يكمن سحر A* وذكاؤها. الـ h(n) هي دالة الحدس (Heuristic Function). وظيفتها هي تقدير التكلفة من النقطة الحالية n إلى نقطة الهدف. هذا مجرد تخمين، لكن يجب أن يكون تخمينًا ذكيًا. أشهر طريقتين لحسابها هما:

• مسافة مانهاتن (Manhattan Distance): مناسبة للخرائط الشبكية التي لا تسمح بالحركة القطرية (فقط فوق، تحت، يمين، يسار). تحسبها ببساطة: |x1 - x2| + |y1 - y2|. كأنك تمشي في شوارع مدينة نيويورك المربعة.
• المسافة الإقليدية (Euclidean Distance): مناسبة إذا كانت الحركة القطرية مسموحة. هي المسافة المستقيمة بين نقطتين: sqrt((x1-x2)^2 + (y1-y2)^2).

نصيحة من أبو عمر: أهم شرط في دالة الحدس h(n) هو أن تكون “مقبولة” (Admissible)، يعني أنها لا تبالغ أبدًا في تقدير التكلفة. يجب أن تكون قيمتها دائمًا أقل من أو تساوي التكلفة الحقيقية للوصول للهدف. ليش؟ لأنه لو بالغت في التقدير (كنت متفائلًا أكثر من اللازم بشأن طريق معين)، قد تتجاهل الخوارزمية المسار الأمثل الحقيقي لأنه سيبدو “أغلى” بناءً على تخمينك الخاطئ. باختصار، خليك متواضع في تخميناتك!

خطوات عمل الخوارزمية: من نقطة “ألف” إلى نقطة “ياء”

لفهم كيفية عملها، تستخدم A* قائمتين رئيسيتين:

• القائمة المفتوحة (Open List): تحتوي على كل النقاط التي تم اكتشافها ولكن لم تتم زيارتها وتقييمها بعد. هذه هي النقاط “المرشحة” للزيارة.
• القائمة المغلقة (Closed List): تحتوي على كل النقاط التي تمت زيارتها وتقييمها بالفعل. لن نعود إليها مرة أخرى.

والخطوات كالتالي:

1. ضع نقطة البداية في القائمة المفتوحة.
2. ادخل في حلقة (loop) تستمر طالما أن القائمة المفتوحة ليست فارغة.
3. داخل الحلقة، ابحث عن النقطة التي تملك أقل قيمة f(n) في القائمة المفتوحة. لنسميها current.
4. انقل current من القائمة المفتوحة إلى القائمة المغلقة (لقد قمنا بزيارتها).
5. إذا كانت current هي نقطة الهدف، مبروك! لقد وجدت المسار. يمكنك الآن تتبع “الآباء” (parent nodes) من نقطة النهاية إلى البداية للحصول على المسار الكامل.
6. إذا لم تكن هي الهدف، تفحص كل “جيرانها” (النقاط المجاورة لها).
7. لكل جار:
   • إذا كان الجار عائقًا أو موجودًا في القائمة المغلقة، تجاهله.
   • احسب تكلفة g مؤقتة للوصول لهذا الجار عبر النقطة current.
   • إذا كان هذا المسار الجديد للجار أفضل (g أقل) من أي مسار سابق له، أو إذا كان الجار ليس في القائمة المفتوحة:
     • حدّث قيم g, h, و f للجار.
     • اجعل current هي “الأب” (parent) لهذا الجار.
     • إذا لم يكن الجار في القائمة المفتوحة، أضفه إليها.

قد تبدو الخطوات كثيرة، لكنها منطقية جدًا عند التطبيق. أنت دائمًا تختار المرشح الأفضل (أقل f)، وتفحصه، ثم تحدث معلومات جيرانه بناءً على ما اكتشفته.

مثال عملي بالكود (Python)

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

# تعريف عقدة (نقطة) في الخريطة
class Node():
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position

        self.g = 0  # التكلفة من البداية
        self.h = 0  # التكلفة التقديرية للهدف
        self.f = 0  # المجموع: g + h

    def __eq__(self, other):
        return self.position == other.position

# دالة خوارزمية A*
def astar(maze, start, end):
    """ترجع قائمة من الإحداثيات كمسار من البداية للنهاية"""

    # إنشاء عقدة البداية والنهاية
    start_node = Node(None, start)
    end_node = Node(None, end)

    # تهيئة القائمة المفتوحة والمغلقة
    open_list = []
    closed_list = []

    # إضافة عقدة البداية
    open_list.append(start_node)

    # الدخول في الحلقة حتى تجد النهاية
    while len(open_list) > 0:

        # إيجاد العقدة الحالية (ذات أقل قيمة f)
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f  (len(maze) - 1) or node_position[0]  (len(maze[len(maze)-1]) -1) or node_position[1]  open_node.g]) > 0:
                continue

            # إضافة الجار للقائمة المفتوحة
            open_list.append(child)

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

خلاصة الحكي ونصيحة من القلب ❤️

من الآخر، خوارزمية A* هي مثال رائع على كيف يمكن لمفهوم بسيط وأنيق أن يحل مشاكل معقدة بكفاءة مذهلة. هي التوازن المثالي بين الدقة والسرعة، بين استكشاف ما هو معروف (g) وتوقع ما هو قادم (h). بالنسبة لي، لم تكن مجرد أداة برمجية، بل كانت درسًا في التفكير المنطقي وحل المشاكل.

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

لا تخف من “إعادة اختراع العجلة” بهدف التعلم. جرب تطبيق A* بنفسك. اصنع متاهة بسيطة، وحاول أن تجعل شخصية تتحرك فيها. هذا التمرين سيعمق فهمك أكثر من قراءة مئة مقال. وعندما تتقنها، ستجد أنك تستطيع تطبيق منطقها في العديد من المجالات الأخرى. بالتوفيق يا وحوش البرمجة! 💪