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