الدرس 3 من 9

تلخيص درس تجنّب تكرار الحالات واختيار طريقة البحث (BFS وA*)

الدرس باختصار

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

مصطلحات الدرس

كل مصطلحات الدرس بصفحة وحدة · راجعها ببطاقات

المسارات المتكررة (Redundant Paths)
طرق مختلفة توصل إلى النقطة نفسها في شجرة البحث، وقد تحوّل مشكلة قابلة للحل إلى مشكلة مستعصية.
الحدود (Frontier) أو القائمة المفتوحة
مجموعة العقد المتاحة للتوسّع في نقطة معيّنة من البحث.
البحث في العرض أولًا (BFS)
يستكشف جميع عقد كل مستوى من الشجرة قبل الانتقال إلى المستوى التالي.
خوارزمية A*
بحث مستنير يجمع تكلفة المسار الفعلية g والتكلفة المقدّرة h فيكون f = g + h، وتعطي الحل الأمثل إذا كان h مقبولًا ومتسقًا.

أهم الأفكار

ورقة مراجعة للطباعة

نسيان التاريخ وتكرار الحالات

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

البحث في العرض أولًا

يعمل BFS هكذا: نقارن الحالة الابتدائية بالهدف؛ فإن لم تكن هدفًا ننتقل إلى المستوى الثاني ونفحص عقده من اليسار إلى اليمين، ثم إلى المستوى الثالث، وهكذا حتى نجد الهدف. في لعبة الأرقام الثمانية وصل إلى الهدف في المستوى الرابع بعد فحص العقد A ثم B وC وD ثم E وF وG ثم H وI. لأنه يفحص المستويات القريبة أولًا فهو يجد أقرب حالة هدف إلى الجذر؛ وإذا كانت كل خطوة بتكلفة واحدة فهذا الحل بأقل عدد خطوات.

متى نختار BFS؟

نختاره حين تكون كل الخطوات بالتكلفة نفسها (مسارات متساوية الطول) ويكون الهدف قريبًا من البداية، كروبوت في متاهة بسيطة: يفحص الأماكن المجاورة ثم التي تليها بالترتيب فيصل إلى الخروج دون التعمّق في مسارات طويلة لا داعي لها.

الحل الأمثل بأقل تكلفة

حين تختلف تكاليف الإجراءات لا يكفي عدد الخطوات، ونحتاج خوارزمية تأخذ التكلفة في الحسبان. البحث الشامل بالأفضلية A* يجمع التكلفة الفعلية المقطوعة g والتكلفة المقدّرة المتبقية h في الاقتران f(n) = g(n) + h(n) ويوسّع العقدة صاحبة أصغر f، ويجد الحل الأمثل بأقل تكلفة إذا تحقق شرطا القبول (h لا يبالغ في تقدير التكلفة) والاتساق. لذلك جواب «أي خوارزمية تجد الحل الأمثل بأقل تكلفة» هو A* مع التعليل بهذين الأمرين.

أمثلة محلولة

مثال 1: معنى القول المأثور

«الخوارزميات التي تنسى تاريخها محكوم عليها بتكرار هذا التاريخ». أوضّح المقصود وكيف نتجنّب ذلك.

اعرض الحل
  1. المقصود: الخوارزمية التي لا تسجّل الحالات التي زارتها تكرّر فحصها عبر مسارات متكررة، فتضيع الجهد وقد تدور بلا نهاية.
  2. التجنّب: نحتفظ بسجل بالحالات المزارة ونتجاهل أي حالة مكرّرة عند توليدها، فنفحص كل حالة مرة واحدة.

الجواب: نحتفظ بسجل للحالات المزارة ونتجاهل المكرر

اختبر حالك

1. ما الطريقة التي تفحص جميع عقد المستوى قبل المستوى التالي؟

2. ما الخوارزمية التي تجد الحل الأمثل بأقل تكلفة عندما يكون h مقبولًا؟

3. كيف نمنع الخوارزمية من تكرار فحص الحالة نفسها؟

باقي الدرس للمسجّلين، ومجاناً

  • 3 أمثلة محلولة كمان
  • 3 أخطاء شائعة وكيف تتجنّبها
  • إجابات «اختبر حالك» مع الشرح
سجّل مجاناً وشوف الدرس كامل

جاهز تتدرّب؟

3 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.

تدرّب على 3 سؤال من هالدرس مجانًا