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

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

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

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

في هالمقالة، بدي أحكيلكم عن هالبطلة، خوارزمية A*، وكيف حوّلت الفوضى في مشروعنا لنظام دقيق وفعّال.

ما هي خوارزمية A* بالضبط؟ (القصة مش سحر، القصة علم)

ببساطة شديدة، خوارزمية A* هي خوارزمية بحث عن المسار، هدفها تلاقي أقصر وأفضل طريق بين نقطة بداية ونقطة نهاية على خريطة أو شبكة (بنسميها في علم الحاسوب “رسم بياني” أو Graph). ما يميز A* عن غيرها من الخوارزميات (مثل Dijkstra أو Breadth-First Search) هو أنها “خوارزمية بحث مُعلَمة” (Informed Search Algorithm).

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

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

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

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

خلينا نفصصها حبة حبة، زي ما بنفصص حبات الرمان:

g(n): التكلفة الحقيقية (المشي اللي مشيناه)

هذا الجزء هو الأسهل. g(n) يمثل التكلفة الفعلية للمسار من نقطة البداية إلى النقطة الحالية n. ممكن تفكر فيها كعداد التاكسي. كل خطوة بتمشيها، العداد بيزيد. في مثال الدرونز تبعنا، كانت هاي التكلفة هي المسافة المقطوعة أو استهلاك البطارية الفعلي للوصول لهالنقطة.

h(n): التكلفة المتوقعة أو “الهيوريستك” (الحدس الذكي)

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

أشهر طريقتين لحساب الهيوريستك:

• مسافة مانهاتن (Manhattan Distance): مناسبة للشبكات المربعة (زي المدن اللي شوارعها متعامدة). بتحسب المسافة بجمع الفروقات على محور X ومحور Y. كأنك بتمشي بين البنايات وممنوع تمشي بشكل قطري.
• المسافة الإقليدية (Euclidean Distance): هي المسافة المستقيمة بين نقطتين (الخط الواصل بينهم). “As the crow flies” زي ما بقولوا الخواجات. مناسبة للخرائط المفتوحة اللي ما فيها عوائق كثيرة.

f(n): التكلفة الإجمالية (القرار النهائي)

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

مثال عملي: خلينا نمشي مع الخوارزمية خطوة بخطوة

تخيل عنا هاي الشبكة البسيطة. بدنا نلاقي أقصر طريق من (S) البداية إلى (E) النهاية، مع وجود جدار (W) كعائق.

. . . . E
. W W W .
. . . . .
S . . . .

1. البداية: نبدأ عند S. نضعها في “القائمة المفتوحة” (Open List)، وهي قائمة النقاط المرشحة للاستكشاف.
2. الخطوة الأولى: نأخذ S من القائمة المفتوحة ونضعها في “القائمة المغلقة” (Closed List – النقاط اللي زرناها وخلصنا منها). ننظر إلى جيرانها. نحسب لكل جار قيم g, h, f ونضيفهم للقائمة المفتوحة.
3. الخطوة الثانية: نختار من القائمة المفتوحة النقطة التي تملك أقل قيمة f. نكرر العملية: ننقلها للقائمة المغلقة، ونفحص جيرانها، ونحدّث القائمة المفتوحة.
4. الاستمرار: نواصل تكرار هذه العملية – اختيار الأفضل من القائمة المفتوحة، استكشاف جيرانه، وتحديث القوائم – حتى نصل إلى نقطة النهاية E.
5. النهاية: بمجرد ما نوصل لـ E، الخوارزمية بتتوقف. ولأنها دائمًا بتختار المسار الأفضل، بنكون ضامنين (إذا كان الهيوريستك مقبول) إن المسار اللي لقيناه هو الأمثل.

مثال برمجي: A* بلغة بايثون (لأنه الكود بحكي ألف كلمة)

الحكي النظري حلو، بس إحنا المبرمجين بنحب نشوف الكود. هي مثال مبسط جدًا لخوارزمية A* بلغة بايثون، بيستخدم مكتبة heapq عشان نعمل “القائمة المفتوحة” بشكل فعال جدًا (Priority Queue).

import heapq

def heuristic(a, b):
    # هيوريستك مسافة مانهاتن
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(grid, start, goal):
    # قائمة النقاط المرشحة للاستكشاف (priority queue)
    open_list = []
    heapq.heappush(open_list, (0, start)) # (f_score, position)
    
    # قاموس لتتبع المسار
    came_from = {}
    
    # قاموس لتخزين تكلفة g لكل نقطة
    g_score = {node: float('inf') for row in grid for node in row}
    g_score[start] = 0
    
    # قاموس لتخزين تكلفة f لكل نقطة
    f_score = {node: float('inf') for row in grid for node in row}
    f_score[start] = heuristic(start, goal)

    while open_list:
        # خذ النقطة اللي عندها أقل f_score من القائمة المفتوحة
        current = heapq.heappop(open_list)[1]

        if current == goal:
            # وصلنا للهدف، قم بإعادة بناء المسار
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1] # اعكس المسار ليصبح من البداية للنهاية

        # استكشف الجيران
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            neighbor = (current[0] + dx, current[1] + dy)
            
            # تحقق من أن الجار داخل حدود الشبكة وليس عائقًا
            if not (0 <= neighbor[0] < len(grid[0]) and 0 <= neighbor[1] < len(grid) and grid[neighbor[1]][neighbor[0]] != 1):
                continue

            # تكلفة الانتقال من النقطة الحالية للجار (هنا نفترضها 1)
            tentative_g_score = g_score[current] + 1

            if tentative_g_score < g_score.get(neighbor, float('inf')):
                # هذا المسار للجار أفضل من أي مسار سابق، سجله
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                if neighbor not in [i[1] for i in open_list]:
                    heapq.heappush(open_list, (f_score[neighbor], neighbor))

    return None # لم يتم العثور على مسار

# مثال للاستخدام
# grid: 0 يعني مسار مفتوح, 1 يعني جدار/عائق
# يجب تعريف كل النقاط في الشبكة
# هذا الكود هو هيكل أساسي ويحتاج إلى تهيئة كاملة للشبكة والنقاط ليعمل

نصائح من خبرة أبو عمر

بعد شغل وسنين مع هاي الخوارزمية وغيرها، جمعت كم نصيحة من الكيس، بتمنى تفيدكم:

• الهيوريستك هو مفتاح السر: اختيارك لدالة الهيوريستك (h) هو أهم قرار. إذا كان الهيوريستك دقيق جدًا (قريب من القيمة الحقيقية)، ستكون A* سريعة جدًا. إذا كان سيئًا أو مبالغًا فيه (غير مقبول)، ممكن الخوارزمية تعطيك مسار غلط أو تصير أبطأ من السلحفاة. “ما تكون أهبل وتعطيها تقديرات خيالية”.
• هياكل البيانات مهمة: استخدام قائمة عادية (list) لـ “القائمة المفتوحة” والبحث فيها عن أقل قيمة في كل مرة هو “شغل مبتدئين” وغير فعال إطلاقًا في الشبكات الكبيرة. تعلم استخدام الـ Priority Queue (أو Min-Heap)، مكتبة heapq في بايثون بتعمل هالشغل بكفاءة عالية.
• الموازنة بين الأداء والدقة: أحيانًا، في الألعاب مثلاً، ما بتحتاج “أقصر مسار” بالضبط. ممكن تحتاج مسار “جيد بما فيه الكفاية” بس بسرعة. في هاي الحالة، ممكن تضرب قيمة الهيوريستك برقم أكبر من 1 (مثلاً 1.5). هذا بخلي الخوارزمية “طماعة” أكتر وتتجه للهدف أسرع، لكن ممكن ما تلاقي المسار الأمثل 100%.
• لا تخترع العجل من جديد: قبل ما تكتب A* من الصفر لمشروعك الإنتاجي، شوف المكتبات الجاهزة. في أغلب لغات البرمجة ومحركات الألعاب، في تطبيقات جاهزة ومحسّنة لخوارزمية A*. لكن الأهم، “افهمها بالأول، بعدين استعمل الجاهز”. فهمك للمبدأ بخليك تعرف تختار المكتبة الصح وتعدل عليها لو لزم.

الخلاصة والزبدة 🏁

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

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

أتمنى تكونوا استفدتوا. والله يعطيكم العافية.