المهارات الرقمية، الصف الثاني عشر · الذكاء الاصطناعي

ورقة مراجعة: تجنّب تكرار الحالات واختيار طريقة البحث (BFS وA*)

أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.

أهم الأفكار

  1. نسيان التاريخ وتكرار الحالات قد تواجه شجرة البحث مسارات متكررة، أي إمكانية الوصول إلى النقطة نفسها بطرق مختلفة، فتتضخم المسارات ويتحوّل الحل من سهل إلى مستعصٍ. معنى القول «الخوارزميات التي تنسى تاريخها محكوم عليها بتكراره»: الخوارزمية التي لا تتذكّر الحالات التي زارتها ستعيد توسيعها وتفحصها مرارًا، فتضيع الوقت والذاكرة وقد لا تنتهي. تجنّب ذلك بأن تحتفظ الخوارزمية بسجل بالحالات التي زارتها، وتتجاهل أي حالة موجودة فيه عند توليدها من جديد.
  2. البحث في العرض أولًا يعمل BFS هكذا: نقارن الحالة الابتدائية بالهدف؛ فإن لم تكن هدفًا ننتقل إلى المستوى الثاني ونفحص عقده من اليسار إلى اليمين، ثم إلى المستوى الثالث، وهكذا حتى نجد الهدف. في لعبة الأرقام الثمانية وصل إلى الهدف في المستوى الرابع بعد فحص العقد A ثم B وC وD ثم E وF وG ثم H وI. لأنه يفحص المستويات القريبة أولًا فهو يجد أقرب حالة هدف إلى الجذر؛ وإذا كانت كل خطوة بتكلفة واحدة فهذا الحل بأقل عدد خطوات.
  3. متى نختار BFS؟ نختاره حين تكون كل الخطوات بالتكلفة نفسها (مسارات متساوية الطول) ويكون الهدف قريبًا من البداية، كروبوت في متاهة بسيطة: يفحص الأماكن المجاورة ثم التي تليها بالترتيب فيصل إلى الخروج دون التعمّق في مسارات طويلة لا داعي لها.
  4. الحل الأمثل بأقل تكلفة حين تختلف تكاليف الإجراءات لا يكفي عدد الخطوات، ونحتاج خوارزمية تأخذ التكلفة في الحسبان. البحث الشامل بالأفضلية A* يجمع التكلفة الفعلية المقطوعة g والتكلفة المقدّرة المتبقية h في الاقتران f(n) = g(n) + h(n) ويوسّع العقدة صاحبة أصغر f، ويجد الحل الأمثل بأقل تكلفة إذا تحقق شرطا القبول (h لا يبالغ في تقدير التكلفة) والاتساق. لذلك جواب «أي خوارزمية تجد الحل الأمثل بأقل تكلفة» هو A* مع التعليل بهذين الأمرين.

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

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

من اُدرُس: odrosai.com/ar/subjects/JO-DIGI-G12/units/4/digi12-u4_l2_search_choice_more

بدك تتأكد إنك فاهم؟

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