خوارزميات البحث

التنقل عبر متاهة التحوط

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

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

خوارزميات البحث

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

شروط

دعونا نبدأ بتوضيح المصطلحات مفتاح الضرورية لفهم خوارزميات البحث.

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

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

• الحالة الابتدائية: هي الوضع الابتدائي للمشكلة. في المتاهة، هذا هو وضع البداية. أما في الشطرنج، فهي الوضع الابتدائي القياسي، حيث تكون جميع القطع مرتبة في مواقعها الافتراضية في بداية اللعبة.

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

• الانتقال: الانتقال هو الانتقال من حالة إلى أخرى، كما هو الحال في الانتقال من تقاطع إلى آخر في متاهة. في الشطرنج، يحدث الانتقال عندما يتحرك اللاعب، مما يؤدي إلى تغيير شكل الرقعة من حالة إلى أخرى.

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

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

بحث A*

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

يعتمد جوهر خوارزمية A* على دالة التكلفة التي تجمع بين عنصرين رئيسيين:

• G-score (التكلفة من البداية): تكلفة المسار من عقدة البداية إلى العقدة الحالية.

• النتيجة H (التكلفة التقريبية للهدف): التكلفة المقدرة من العقدة الحالية إلى عقدة الهدف.

دالة التكلفة

دالة التكلفة الإجمالية، F-score ، تعطى بواسطة:

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

أين:

$f(n)$ ...