كانت خرائطنا تبحث في كل شارع: كيف أنقذتنا خوارزمية A* من جحيم البحث الشامل؟

يا جماعة الخير، السلام عليكم ورحمة الله. معكم أخوكم أبو عمر.

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

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

المشكلة: الكابوس المسمى “البحث الشامل”

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

هناك خوارزميات مثل بحث العمق أولاً (DFS) وبحث العرض أولاً (BFS) تقوم بذلك. وهناك نسخة أفضل قليلاً وهي خوارزمية ديكسترا (Dijkstra’s Algorithm).

خوارزمية ديكسترا: الجار الطيب ولكن الأعمى

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

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

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

دخول البطل: خوارزمية A* (A-Star)

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

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

المعادلة السحرية: f(n) = g(n) + h(n)

هذه المعادلة البسيطة هي قلب وروح خوارزمية A*. دعونا نفككها “حبة حبة”:

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

ببساطة، A* تبحث عن المسار الذي يبدو واعداً أكثر، بناءً على ما قطعته بالفعل وما تتوقع أن تقطعه في المستقبل.

كيف تفكر خوارزمية A* عملياً؟

لفهم الأمر، دعنا نتخيل أن الخوارزمية لديها قائمتان:

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

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

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

وهكذا تستمر العملية، حيث تتوسع الخوارزمية بشكل ذكي وموجه نحو الهدف، بدلاً من الانتشار العشوائي.

الدالة التجريبية (Heuristic): سر الطبخة

قوة A* تكمن في الدالة h(n). ولكن اختيار هذه الدالة له شروط. أهم شرط هو أن تكون “مقبولة” (Admissible)، وهذا يعني أنها يجب ألا تبالغ في تقدير التكلفة الحقيقية. يجب أن تكون دائماً متفائلة.

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

أشهر دالتين Heuristic في الخرائط الشبكية (Grids):

• مسافة مانهاتن (Manhattan Distance): تستخدم عندما يكون التحرك مسموحاً فقط أفقياً وعمودياً (مثل شوارع مدينة نيويورك).
  
  h = abs(current.x - goal.x) + abs(current.y - goal.y)
• المسافة الإقليدية (Euclidean Distance): هي المسافة المستقيمة “الخط الجوي”. تستخدم عندما يكون التحرك مسموحاً في كل الاتجاهات.
  
  h = sqrt((current.x - goal.x)^2 + (current.y - goal.y)^2)

شوية كود عشان نفهم أكثر (Python Pseudocode)

هذا ليس كوداً كاملاً، بل هو هيكل أساسي بلغة تشبه بايثون ليوضح الفكرة الرئيسية لخوارزمية A*.

# A* Pseudocode

function A_Star(start_node, goal_node):
    # قائمة العقد التي لم تتم زيارتها بعد
    open_list = []
    # قائمة العقد التي تمت زيارتها
    closed_list = []

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

    while open_list is not empty:
        # ابحث عن العقدة ذات أقل قيمة f في open_list
        current_node = find_node_with_lowest_f_cost(open_list)

        # انقل العقدة الحالية من open_list إلى closed_list
        open_list.remove(current_node)
        closed_list.append(current_node)

        # إذا وصلنا للهدف، انتهينا!
        if current_node == goal_node:
            return reconstruct_path(current_node) # دالة لإعادة بناء المسار

        # تفقد كل الجيران
        for neighbor in current_node.neighbors:
            # تجاهل الجار إذا كان في القائمة المغلقة
            if neighbor in closed_list:
                continue

            # g_cost: المسافة من البداية إلى الجار عبر العقدة الحالية
            g_cost_to_neighbor = current_node.g + distance(current_node, neighbor)

            # إذا كان المسار الجديد للجار أقصر أو لم تتم زيارة الجار بعد
            if g_cost_to_neighbor < neighbor.g or neighbor not in open_list:
                # قم بتحديث قيم الجار
                neighbor.g = g_cost_to_neighbor
                neighbor.h = calculate_heuristic(neighbor, goal_node)
                neighbor.f = neighbor.g + neighbor.h
                neighbor.parent = current_node # مهم لتتبع المسار

                # أضف الجار إلى القائمة المفتوحة إذا لم يكن موجوداً
                if neighbor not in open_list:
                    open_list.append(neighbor)
    
    # إذا انتهت الحلقة ولم نجد الهدف، فهذا يعني لا يوجد مسار
    return None

الخلاصة ونصيحة من أبو عمر 💡

يا جماعة، خوارزمية A* ليست مجرد كود، بل هي طريقة تفكير. هي تعلمنا كيف نوازن بين المعلومات المؤكدة التي لدينا (المسافة المقطوعة g) والتوقعات الذكية للمستقبل (التقدير للوصول h). هذا التوازن هو ما يجعل أنظمتنا فعالة وذكية.

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

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

ودمتم سالمين ومبدعين. 😉