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

حكاية “الجندي الغبي” الذي كاد أن يدمر مشروعنا

قبل عدة سنوات، كنت وفريقي الصغير نعمل على لعبة استراتيجية بسيطة. كان كل شيء يسير على ما يرام، التصاميم رائعة، والميكانيكيات الأساسية تعمل… إلا “شغلة” واحدة صغيرة كانت تُفقدنا صوابنا: حركة الجنود. أردنا أن يجد الجندي أقصر طريق من النقطة (أ) إلى النقطة (ب) متفادياً العقبات كالأشجار والمباني.

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

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

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

ما هو الجحيم الذي كنا فيه؟ مشكلة البحث الأعمى

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

• البحث بالعرض أولاً (BFS): استكشف كل الجيران، ثم جيران الجيران، وهكذا طبقة بعد طبقة. هي تضمن إيجاد أقصر مسار إذا كانت تكلفة كل خطوة متساوية، لكنها كارثية من حيث الأداء في المساحات الكبيرة.
• البحث بالعمق أولاً (DFS): انطلق في مسار واحد حتى النهاية، ثم ارجع خطوة واستكشف مساراً آخر. هي سريعة من حيث الذاكرة، لكنها نادراً ما تجد المسار الأمثل، وقد تعلق في مسارات لا نهائية.

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

المنقذ A*: الخوارزمية التي تملك “حدساً” رياضياً

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

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

قد تبدو المعادلة مخيفة، لكن دعونا نفككها ببساطة يا جماعة:

g(n): تكلفة الماضي (ما قطعناه بالفعل)

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

h(n): تكلفة المستقبل (أفضل تخمين للوصول)

هنا يكمن السحر كله! h(n) هي دالة التخمين أو “الهيوريستك” (Heuristic Function). إنها تقدير ذكي ومبني على معرفة مسبقة لتكلفة الوصول من النقطة الحالية n إلى نقطة الهدف. إنها ليست التكلفة الفعلية (لأننا لم نصل بعد ولا نعرف العقبات)، بل هي “تخمين متعلم”.

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

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

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

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

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

لنفترض أن لدينا هذه الخريطة الصغيرة، حيث (S) هي البداية، (E) هي النهاية، و (X) هي جدار لا يمكن عبوره. كل خطوة أفقية أو عمودية تكلف 10.

. . . . .
. S . . .
. X X X .
. . . E .
. . . . .

ستعمل الخوارزمية كالتالي:

1. قائمتان: نبدأ بقائمتين، Open List (للنقاط التي سنزورها) و Closed List (للنقاط التي زرناها وانتهينا منها).
2. نقطة البداية: نضع النقطة S في Open List.
   • g(S) = 0 (لم نتحرك بعد)
   • h(S) = نحسب مسافة مانهاتن من S إلى E (مثلاً 3 خطوات أفقية وخطوة عمودية = 4 * 10 = 40)
   • f(S) = 0 + 40 = 40
3. الحلقة الرئيسية:
   • نختار النقطة ذات أقل قيمة f من Open List (وهي S حالياً). ننقلها إلى Closed List.
   • ننظر إلى جيران S (أعلى، أسفل، يمين، يسار).
   • لكل جار (لنسمه P)، نحسب قيمه:
     • g(P) = g(S) + 10 = 10
     • h(P) = نحسب مسافة مانهاتن من P إلى E.
     • f(P) = g(P) + h(P)

     ونضيفه إلى Open List.

   • في الدورة التالية، نختار مرة أخرى النقطة ذات أقل قيمة f من كل النقاط الموجودة في Open List. هذه النقطة هي التي تبدو أقرب إلى الحل.
4. النهاية: نستمر في هذه العملية، ننقل النقاط من Open إلى Closed ونضيف جيراناً جدداً، حتى نصل إلى نقطة الهدف E. حينها، نعيد تتبع المسار للخلف من E إلى S عبر “الآباء” (parent nodes) التي حفظناها لكل نقطة.

النتيجة؟ الخوارزمية تتجاهل بذكاء المسارات التي تبتعد عن الهدف (لأن قيمة h فيها تكون عالية) وتركز على الممرات الواعدة. لن تذهب لاستكشاف أعلى الخريطة إذا كان الهدف في الأسفل.

مثال كود بسيط بلغة Python

هذا الكود ليس كاملاً، لكنه يوضح الفكرة الأساسية لكيفية تنظيم البيانات. ستحتاج إلى استخدام “طابور الأولوية” (Priority Queue) لتطبيق Open List بكفاءة.

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

        self.g = 0 # التكلفة من البداية
        self.h = 0 # التكلفة المقدرة للهدف (Heuristic)
        self.f = 0 # التكلفة الإجمالية

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

# الدالة الرئيسية للخوارزمية
def astar(grid, 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:
        
        # 1. إيجاد العقدة ذات أقل قيمة f في القائمة المفتوحة
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f  open_node.g:
                    continue
            
            # إضافة الجار إلى القائمة المفتوحة
            open_list.append(child)

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

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

الخلاصة: من البحث الأعمى إلى البصيرة الثاقبة 👍

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

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