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

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

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

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

في هاي المقالة، بدي آخذكم معي في الرحلة اللي خضتها لفهم وتطبيق هاي الخوارزمية العبقرية، وكيف ممكن تنقذ مشاريعكم أنتم كمان.

ما هي خوارزمية A* (A-Star) وليش هي “الحجّة” في عالم البحث؟

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

طيب شو اللي بميزها عن غيرها من الخوارزميات زي Dijkstra أو البحث بالعرض أولاً (BFS)؟

الجواب بكلمة واحدة: الذكاء. خوارزمية A* ما بتمشيش عمياني. هي بتجمع بين طريقتين في التفكير:

1. ما نعرفه بالفعل: بتتبع التكلفة الحقيقية للمسار اللي قطعته حتى الآن.
2. أفضل تخمين لدينا: بتقدر بشكل “حدسي” التكلفة المتبقية للوصول إلى الهدف.

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

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

كل سحر A* يكمن في هاي المعادلة البسيطة. خلينا نفصصها حبة حبة، زي ما بنفصص حبة الجوز عشان نطلع باللب الزاكي.

تخيل إنه الخوارزمية واقفة عند نقطة معينة على الخريطة اسمها ‘n’ وبدها تقرر وين تروح بعدين. عشان تقرر، بتحسب “درجة أفضلية” لكل نقطة مجاورة إلها باستخدام المعادلة هاي:

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

g(n): تكلفة المشوار اللي قطعناه (The Cost of the Journey So Far)

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

h(n): حدسنا للمستقبل (The Heuristic Function)

هون بيجي دور الذكاء والـ “حدس”. h(n) هي دالة التخمين أو الـ “heuristic”. وظيفتها تقدّر التكلفة من النقطة الحالية ‘n’ إلى نقطة النهاية. لاحظ إني حكيت “تقدّر”، يعني مش شرط تكون دقيقة 100%، لكن كل ما كان تقديرها أقرب للواقع، كل ما كانت الخوارزمية أسرع وأكفأ.

أشهر مثال على دالة heuristic هو “المسافة الجوية” أو المسافة الإقليدية (Euclidean Distance) – يعني خط مستقيم من النقطة الحالية للهدف. هذا التقدير مفيد لأنه، في الواقع، مستحيل يكون المسار الفعلي أقصر من الخط المستقيم.

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

f(n): النتيجة النهائية اللي بتحدد قرارنا (The Final Score)

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

يلا نوسّخ إيدينا: مثال عملي خطوة بخطوة

تخيل معنا هاي الخريطة البسيطة (شبكة). بدنا نلاقي أقصر طريق من A إلى B، مع وجود جدار (X) ما بنقدر نمر من خلاله. تكلفة الحركة الأفقية أو العمودية هي 10، والحركة القطرية هي 14 (تقريب لجذر 2 ضرب 10).

  (A) . . . .
  .   . X . .
  .   . X . .
  .   . X . (B)
  .   . . . .

1. الخطوة 1: نبدأ من A. ما في إشي قبلها، فـ g(A) = 0. نحسب h(A) (المسافة التقديرية لـ B) ونحسب f(A). نضع A في القائمة المفتوحة (Open List).
2. الخطوة 2: نطلع A من القائمة المفتوحة ونضيفها للقائمة المغلقة (Closed List). نشوف كل جيرانها. خلينا نقول جارتها اللي على يمينها اسمها ‘N1’.
3. الخطوة 3: نحسب التكاليف لـ ‘N1’:
   • g(N1) = تكلفة الوصول لـ A (اللي هي 0) + تكلفة الحركة من A لـ N1 (اللي هي 10). إذن g(N1) = 10.
   • h(N1) = نحسب المسافة التقديرية من N1 إلى B.
   • f(N1) = g(N1) + h(N1).

   نكرر هذا لكل جيران A ونضيفهم كلهم للقائمة المفتوحة.

4. الخطوة 4: الآن، ننظر إلى القائمة المفتوحة ونختار النقطة اللي عندها أقل قيمة f. نخرجها من القائمة المفتوحة، نضيفها للمغلقة، ونستكشف جيرانها.
5. الخطوة 5: نستمر في هذه العملية. إذا وصلنا لنقطة كانت موجودة أصلاً في القائمة المفتوحة ولكن من مسار جديد تكلفته g أقل، نقوم بتحديثها. هذا يعني أننا وجدنا طريقاً أفضل للوصول إليها.
6. الخطوة 6: نتوقف عندما نُخرج النقطة B (الهدف) من القائمة المفتوحة. وقتها، نكون قد وجدنا أقصر مسار! كل ما علينا فعله هو تتبع “آباء” كل نقطة بشكل عكسي من B إلى A.

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

من الحكي للكود: تطبيق بسيط باستخدام بايثون

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

class Node():
    """A node class for A* Pathfinding"""

    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position

        self.g = 0
        self.h = 0
        self.f = 0

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

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

    # Create start and end node
    start_node = Node(None, start)
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)
    end_node.g = end_node.h = end_node.f = 0

    # Initialize both open and closed list
    open_list = []
    closed_list = []

    # Add the start node
    open_list.append(start_node)

    # Loop until you find the end
    while len(open_list) > 0:

        # Get the current node (the one with the lowest f value)
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index

        # Pop current off open list, add to closed list
        open_list.pop(current_index)
        closed_list.append(current_node)

        # Found the goal
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1] # Return reversed path

        # Generate children
        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # Adjacent squares

            # Get node position
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

            # Make sure within range and walkable
            # (This part depends on your maze representation)
            # ...

            # Create new node
            new_node = Node(current_node, node_position)

            # Append
            children.append(new_node)

        # Loop through children
        for child in children:

            # Child is on the closed list
            if child in closed_list:
                continue

            # Create the f, g, and h values
            child.g = current_node.g + 1
            # Heuristic: simple Euclidean distance (squared to avoid sqrt)
            child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)
            child.f = child.g + child.h

            # Child is already in the open list
            if child in open_list:
                # Check if this path is better
                # ...
                continue

            # Add the child to the open list
            open_list.append(child)

نصائح من “الختيار”: كيف تستخدم A* زي المحترفين

بعد سنين من التعامل مع هاي الخوارزمية وغيرها، اسمحولي أعطيكم كم نصيحة عملية:

• دالة التخمين (Heuristic) هي كل إشي: نجاح أو فشل A* يعتمد بشكل هائل على جودة دالة h(n). استثمر وقت في تصميم دالة تخمين ذكية ومناسبة لمشكلتك. كل ما كانت أقرب للواقع (مع الحفاظ على شرط “التساهل”)، كل ما كانت الخوارزمية أسرع بآلاف المرات.
• هياكل البيانات هي مفتاح الأداء: في الكود أعلاه، استخدمت قائمة بسيطة للـ Open List وبحثت فيها عن أقل عنصر. هذا بطيء جداً (O(n)). في التطبيقات الحقيقية، لازم تستخدم “طابور أولوية” (Priority Queue)، اللي غالباً ما يتم بناؤه باستخدام هيكل بيانات اسمه Min-Heap. هذا بخلي عملية إيجاد العنصر الأقل تكلفة سريعة جداً (O(log n)).
• مش دايماً A* هي الحل: نعم، قرأتها صح. إذا كانت الخريطة عندك بسيطة جداً وما فيها تكاليف مختلفة للحركة، يمكن خوارزمية زي البحث بالعرض أولاً (BFS) تكون كافية وأسهل في التطبيق. A* تلمع لما تكون التكاليف مختلفة والمساحة كبيرة.
• انتبه للذاكرة: خوارزمية A* ممكن تستهلك ذاكرة كبيرة لأنها بتحفظ كل النقاط اللي زارتها في القائمتين المفتوحة والمغلقة. في الخرائط الضخمة جداً (زي خرائط الألعاب الحديثة)، قد تحتاج للنظر في بدائل مثل IDA* (Iterative Deepening A*) أو JPS (Jump Point Search) اللي بتحسن استخدام الذاكرة.

الخلاصة: المسار مش مجرد خط، هو قصة نجاح 💡

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

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

الله يوفقكم في مساراتكم، سواء كانت في الكود أو في الحياة. 🚀