أقيم تعلُّمي
المعرفة: أستخدم ما تعلمْتُه من معارف في هذا الدرس للإجابة عن الأسئلة الآتية:
السؤال الأوَّل: يُمثِّل الشكل التالي شجرة البحث للعبة ( X-O ). أجد مسار الحَلِ باستخدام خوارزمية البحث في العرض أَوَّلًا ، علما بأنَّ فوز أحد اللاعبيْْنِ يعني انتهاء اللعبة
نبحث مستوى- بمستوى مع ترتيب العُقَد يسار ← يمين، ونتوقَّف عند أوَّل حالة فوز؛ لأنَّها حالة هدف نهائية.
ترتيب التوسُّع حسب المستويات:
•المستوى 1 : 1 (الجذر) – لا فوز.
•المستوى 4 ، 3 ، 2 : 2 – لا فوز.
•المستوى 7 ، 6 ، 5 : 3.
عند العُُقدة 7 نجد أول حالة هدف فوز (X)، فيتوقَّف BFS فورًًا.
مسار الحلِِّ الأمثل(أقصر عدد نقلات) : 7 → 3 → 1
بما أن النقلات جميعها متكافئة الكلفة، فإنَّ BFS يضمن الوصول إلى أقرب فوز، وبالتالي فهذا المسار هو أيضًا الأقلُّ تكلفة/ الأقصر.
مسار البحث بحسب خوارزميَّة البحث في العرض أولًًاَّ:
7- 6- 5- 4- 3- 2- 1
السؤال الثاني: أُحدِّد الحالات التي تُستخدم فيها خوارزميات البحث المستنير (الاستدلالي).
1. إذا كانت المشكلة معقَّدة.
2. إذا كانت حيز الحالة كبير الحجم
السؤال الثالث: أدرس الحالات الآتية، ثمََّ أُُحدِِّد طريقة البحث الفُُضلى للوصول إلى الحََلِِّ:
1. "روبوت يحاول الخروج من متاهة بسيطة، والمسارات كلها متساوية في الطول، والهدف قريب من نقطة البداية".
خوارزميّة البحث في العرض أوّلًا؛ لأنَّ المسارات جميعها متساوية في الطول. ولا نختار خوارزمية البحث في العمق أولًا ؛ لأنَّ الهدف قريب من نقطة البداية.
2. "لعبة تتطلب الوصول إلى نتيجة مُعينة، لكنّها بحاجة إلى خطوات كثيرة جدا، والمسارات الطويلة كثيرة".
الخطوات كثيرة جدا، والمسارات الطويلة كثيرة؛ لذلك ألجأ إلى خوارزمية البحث التكراري بالأفضلية؛ لأنَّ ذاكرة الحاسوب محدودة، وأنَّه من الممكن استخدام خوارزمية المستعمرات النملية، أو الشبكات العصبية
3. "لاعب يبحث عن أقصر مسار لحَلِّ لغز يتطلب التحرُّك بين حالات عديدة بتكاليف مختلفة (بعض التحرُّكات أصعب من غيرها)"
بما أنَّ بعض التكاليف أصعب من غيرها فإنَّه يُفضل استخدام خوارزمية ( A* البحث بالأفضلية) ؛ لأنَّ التكاليف مختلفة .
المهارات: أُُوظِِّف مهارات التفكير الناقد والبحث الرقمي والتواصل في الإجابة عن الأسئلة الآتية:
السؤال الأول: يقال: "إنََّ الخوارزميات التي تنسى تاريخها محكوم عيلها بتكرار هذا التاريخ".
أُُوضِِّح المقصود بهذا القول، ثمَّ أُبين كيف يُمكن تجنُّب ذلك.
يُقصد بذلك أنَّ الخوارزمية قد تعود لزيارة العُقدة نفسها، أو الحالة مرارًا وتكرارًا، وتعيد استشكاف المسارات نفسها بلا داعٍ، ممّا يؤدي إلى إضاعة الوقت، وحسابات إضافية خصوصًا في المسائل الكبيرة التي تحتوي على دورات lps . وهذا بسبب عدم الاحتفاظ بما تمَّت زيارته. يُمكن تجنب ذلك من خلال سجلِِّ للزيارات، بحيث تتحوَّل حالة العُقدة إلى clsed لكل حالة تمَّت معالجتها نهائيا، وعدم التوسُّع في البحث في المسارات المنبثقة من هذه العُقدة.
السؤال الثاني: بناءًً على شجرة البحث للعبة (X-O) في السؤال الأول من أسئلة المعرفة، ما الخوارزمية التي يُمكِن بها إيجاد الحَلِّ الأمثل بأقل تكلفة؟ أُبرر إجابتي.
خوارزمية البحث في العرض أوَّلًا ؛ لأنَّها تسمح باكتشاف الحالات الممكنة جميعها، والو صول إلى أقرب حل
السؤال الثالث: أرسم شجرة البحث في الشكل الآتي، عمًلًا بأنََّ النقطة الهدف هي (Z)، ومسار البحث عن هذه النقطة باستخدام خوارزمية البحث في العرض أَوّلًا هو:
A → B→ C→X →Y→K→W→Z
