كانت توصيات المسار لدينا كارثية: كيف أنقذتنا خوارزمية A* من جحيم الطرق غير الفعالة؟

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

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

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

لماذا فشلت محاولاتنا الأولى؟ فهم أساسيات إيجاد المسار

قبل أن نتحدث عن البطل A*، من المهم أن نفهم لماذا كانت حلولنا الأولية سيئة للغاية. عالم إيجاد المسار في علوم الحاسوب يعتمد على مفهوم يسمى “نظرية المخططات” (Graph Theory). ببساطة، يمكننا تمثيل أي خريطة على شكل:

• العُقد (Nodes): هي النقاط المهمة على الخريطة (تقاطعات الشوارع، مواقع، بداية ونهاية الطريق).
• الأضلاع (Edges): هي المسارات التي تربط بين هذه العُقد (الشوارع نفسها)، ولكل ضلع “وزن” أو “تكلفة” (Cost) تمثل المسافة، أو وقت الرحلة، أو حتى استهلاك الوقود.

مهمتنا هي إيجاد سلسلة من الأضلاع التي تربط عقدة البداية بعقدة النهاية بأقل تكلفة إجمالية.

الخوارزميات “العمياء” ومشاكلها

في البداية، اعتمدنا على خوارزميات بسيطة مثل البحث بأولوية العرض (Breadth-First Search – BFS). هذه الخوارزمية جيدة في إيجاد أقصر مسار من حيث عدد الخطوات (الأضلاع)، لكنها تتجاهل تمامًا تكلفة هذه الخطوات. بالنسبة لها، طريق سريع طوله 10 كيلومترات هو نفس خطوة طريق ترابي طوله كيلومتر واحد، وهذا لا يصلح في العالم الحقيقي.

ثم تطورنا قليلاً واستخدمنا خوارزمية “ديكسترا” (Dijkstra’s Algorithm). كانت هذه خطوة كبيرة إلى الأمام. ديكسترا خوارزمية ممتازة وتضمن إيجاد المسار الأقل تكلفة. تعمل عن طريق استكشاف العُقد الأقرب إلى نقطة البداية بشكل منهجي، وتحديث المسارات باستمرار.

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

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

تقديم البطل: خوارزمية A* (إيه ستار)

خوارزمية A* هي الحل السحري الذي يجمع بين أفضل ما في العالمين: دقة خوارزمية ديكسترا، مع إضافة “ذكاء” استكشافي. إنها خوارزمية “مُستنيرة” (Informed Search Algorithm) لأنها تستخدم معلومات إضافية لتوجيه بحثها نحو الهدف.

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

يكمن سر A* في هذه المعادلة البسيطة والعبقرية التي تقيّم كل عقدة (n) تفكر في زيارتها:

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

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

مفتاح النجاح: دالة الاستدلال (Heuristic Function)

قوة A* تعتمد بشكل كبير على جودة الدالة h(n). لكي تضمن A* إيجاد المسار الأمثل، يجب أن تلتزم دالة الاستدلال بشرطين:

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

أشهر دالتي استدلال نستخدمهما في الخرائط ثنائية الأبعاد هما:

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

مثال عملي بسيط

تخيل شبكة بسيطة. أنت في النقطة (أ) وتريد الوصول إلى (ي). هناك طريقان:

• المسار 1: (أ) -> (ب) -> (ج) -> (ي). تكلفة كل خطوة هي 10. التكلفة الإجمالية g(n) = 30.
• المسار 2: (أ) -> (د) -> (هـ). تكلفة كل خطوة هي 10. التكلفة الإجمالية g(n) = 20.

خوارزمية ديكسترا قد تبدأ باستكشاف المسار 1. لكن A*، عند النقطة (ب)، ستحسب g(ب) = 10، ثم تحسب h(ب) (المسافة المستقيمة من ‘ب’ إلى ‘ي’) والتي قد تكون كبيرة. بينما عند النقطة (د)، ستحسب g(د) = 10، لكن h(د) ستكون أصغر بكثير لأن ‘د’ أقرب جغرافيًا إلى الهدف ‘ي’. نتيجة لذلك، سيكون f(د) أقل من f(ب)، وستختار الخوارزمية بذكاء استكشاف المسار 2 أولاً، موفرةً وقتاً وجهداً كبيراً.

من النظرية إلى التطبيق: كود A*

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

import heapq # سنستخدم هذه المكتبة لتطبيق طابور الأولوية بكفاءة

class Node:
    def __init__(self, position, parent=None):
        self.position = position
        self.parent = parent
        self.g = 0 # التكلفة من البداية
        self.h = 0 # التكلفة المقدرة للهدف
        self.f = 0 # التكلفة الإجمالية

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

    def __lt__(self, other):
        return self.f < other.f

def astar(grid, start, end):
    """
    Returns a list of tuples as a path from the given start to the given end in the given grid
    """

    start_node = Node(start)
    end_node = Node(end)

    open_list = []
    closed_list = set()

    # نستخدم heapq ليكون open_list طابور أولوية
    heapq.heappush(open_list, start_node)

    while len(open_list) > 0:
        # احصل على العقدة ذات أقل قيمة f
        current_node = heapq.heappop(open_list)
        closed_list.add(current_node.position)

        # وصلنا للهدف
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1] # اعكس المسار ليكون من البداية للنهاية

        # استكشف الجيران
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # الجيران الأربعة
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

            # تأكد أن الجار داخل حدود الشبكة وأنه ليس جدارًا
            if node_position[0] > (len(grid) - 1) or node_position[0]  (len(grid[0]) - 1) or node_position[1]  open_node.g):
                continue
            
            # أضف الجار إلى القائمة المفتوحة
            heapq.heappush(open_list, new_node)
            
    return None # لم يتم العثور على مسار

نصائح من خبير: خلاصة تجربتي مع A*

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

1. بنية البيانات هي الملك: استخدام قائمة عادية للـ open_list والبحث فيها عن أقل عنصر f في كل مرة هو أمر كارثي من حيث الأداء (تعقيد O(n)). استخدام “طابور الأولوية” (Priority Queue)، والذي يمكن تطبيقه بسهولة في بايثون عبر مكتبة heapq، يحسن الأداء بشكل هائل (تعقيد O(log n)) وهو أمر لا غنى عنه.
2. دالة الاستدلال فن وعلم: اختيار الدالة الاستدلالية الصحيحة يعتمد على طبيعة مشكلتك. في خرائط المدن، قد لا تكون المسافة الإقليدية هي الأفضل دائمًا بسبب المباني والشوارع. أحيانًا، دالة هجينة أو دالة محسوبة مسبقًا (pre-computed) يمكن أن تعطي نتائج أفضل. لا تخف من التجربة.
3. العالم الحقيقي أكثر تعقيدًا: الخرائط الحقيقية ليست شبكات بسيطة. هناك تكاليف مختلفة للطرق (طريق سريع مقابل طريق داخلي)، وهناك شوارع باتجاه واحد، وتقاطعات يُمنع فيها الانعطاف. يمكنك نمذجة كل هذا عن طريق تعديل كيفية بناء المخطط (Graph) وتحديد تكلفة الانتقال (g(n)) بين العُقد. على سبيل المثال, تكلفة الانتقال في شارع باتجاه واحد تكون لانهائية في الاتجاه الخاطئ.
4. A* ليست الحل دائمًا: A* رائعة للخرائط الثابتة. لكن في بيئات تتغير باستمرار (مثل الروبوتات التي تستكشف منطقة مجهولة)، قد تكون هناك خوارزميات أفضل مثل D* Lite، التي تتخصص في إعادة التخطيط بكفاءة عند اكتشاف تغييرات في الخريطة.

الخلاصة: من الفوضى إلى النظام بفضل معادلة بسيطة

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

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