المشروع - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

سؤال 1: عدل المقطع البرمجي لخوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل (A* search) الموزونتين بتغيير الأوزان الأفقية والرأسية إلى 3 والأوزان القطرية إلى 5، وكذلك عدّل نقطة البداية إلى (7, 2).

الإجابة: س:1: اجعل وزن الحركة الأفقية/الرأسية=3، والقطرية=5، ونقطة البداية (2, 7) في BFS و *A.

خطوات الحل:

1. **الخطوة 1 (فهم المطلوب):** لنفهم هذا السؤال. لدينا خوارزميتان للبحث في الرسوم البيانية أو الشبكات: خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل (A*). المطلوب هو تعديل نسخة موزونة منهما، أي نسخة تأخذ في الاعتبار تكاليف مختلفة للحركات.
2. **الخطوة 2 (تحديد التعديلات):** التعديلات المطلوبة هي ثلاث: 1. تغيير وزن الحركة الأفقية (يمين/يسار) والحركة الرأسية (أعلى/أسفل) ليصبح 3 بدلاً من 1 (عادةً). 2. تغيير وزن الحركة القطرية (مثل أعلى-يمين) ليصبح 5 بدلاً من √2 تقريباً (أو قيمة أخرى). 3. تغيير نقطة البداية في البحث من (0,0) عادةً إلى (7, 2). هذه التعديلات تُطبق على الكود أو الخوارزمية نفسها، مما يعني أن أي حساب للمسافة أو التكلفة سيعتمد على هذه الأوزان الجديدة.
3. **الخطوة 3 (النتيجة والتطبيق):** إذن، بعد التعديل، ستقوم الخوارزمية الموزونة (BFS الموزون و A* الموزون) بحساب تكلفة المسار بناءً على: تكلفة 3 لكل خطوة أفقية أو رأسية، وتكلفة 5 لكل خطوة قطرية. وستبدأ البحث من الخلية أو العقدة ذات الإحداثيات (7, 2).

سؤال 2: ما المسار الجديد ذو المسافة الأقصر، وما عدد الخلايا التي فحصت في الإصدارات غير الموزونة لخوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search) باستخدام دالة الاستدلال الثابت؟ حدد هذه القيم ودون ملاحظاتك.

الإجابة: س:2: - المسار الأقصر (غير موزون): الأقل خطوات. - BFS و *A (استدلال ثابت): نفس المسار الأقصر. - الخلايا المفحوصة: متساوية تقريبًا.

خطوات الحل:

1. **الشرح:** هذا السؤال يتعلق بمقارنة أداء الخوارزميات في حالة عدم استخدام الأوزان (غير الموزونة). الفكرة هنا هي فهم كيف تعمل BFS و A* عندما تكون تكلفة كل حركة متساوية (عادةً 1). أولاً، المسار الأقصر في النسخة غير الموزونة هو المسار الذي يحتوي على أقل عدد من الخطوات أو الخلايا من نقطة البداية إلى الهدف، بغض النظر عن الاتجاه (أفقي، رأسي، قطري). ثانياً، عندما تستخدم خوارزمية A* دالة استدلال ثابتة (مثل h(n)=0)، فإنها تفقد ميزة التوجيه نحو الهدف. في هذه الحالة، تصبح سلوكياً مشابهة جداً لـ BFS، حيث تبحث في الخلايا بنفس الترتيب تقريباً (يعتمد على تنفيذ قائمة الانتظار). لذلك، من المتوقع أن تجدا نفس المسار الأقصر (الأقل في عدد الخطوات). أخيراً، لأن سلوكهما متشابه في هذه الحالة الخاصة (A* باستدلال ثابت)، فإن عدد الخلايا التي تفحصها كل خوارزمية قبل الوصول للهدف سيكون متقارباً أو متساوياً تقريباً، حيث تبحثان في نفس المناطق من الفضاء.

سؤال 3: اتبع الخطوات نفسها للإصدارات الموزونة من خوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search) باستخدام دالة الاستدلال الثابت.

الإجابة: س:3: - المسار الأقصر (موزون): الأقل تكلفة. - مع استدلال ثابت: BFS الموزون و *A متطابقان في المسار وعدد الخلايا.

خطوات الحل:

1. **الخطوة 1 (المفهوم):** نتذكر أن الخوارزميات الموزونة تأخذ في الاعتبار تكاليف مختلفة للحركات. هنا، الأوزان هي 3 للحركات الأفقية/الرأسية و5 للقطرية.
2. **الخطوة 2 (التطبيق والمقارنة):** في هذه الحالة، المسار الأقصر هو الذي له أقل تكلفة إجمالية (مجموع أوزان حركاته)، وليس بالضرورة أقل عدد من الخطوات. عند استخدام دالة استدلال ثابتة (مثل h(n)=0) مع الخوارزمية A* الموزونة، فإنها مرة أخرى تفقد ميزة التوجيه. ستقارن الخلايا بناءً على التكلفة الفعلية من نقطة البداية فقط (g(n)). هذا يجعل سلوكها مطابقاً لخوارزمية BFS الموزون، والتي تبحث أيضاً عن المسار بأقل تكلفة دون توجيه استدلالي.
3. **الخطوة 3 (النتيجة):** لذلك، في هذا السيناريو المحدد (موزون + استدلال ثابت)، نتوقع أن خوارزميتي BFS الموزون و A* الموزون ستجدان نفس المسار الأمثل (ذو أقل تكلفة)، وستفحصان نفس عدد الخلايا تقريباً خلال عملية البحث، لأنهما تتبعان منطقاً مشابهاً جداً.

سؤال 4: كرر العملية للإصدارات غير الموزونة والموزونة من خوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search) باستخدام دالة استدلال مانهاتن (Manhattan Heuristic).

الإجابة: س:4: - BFS: لا يتأثر بالاستدلال. - *A (مانهاتن): أكثر توجيهًا، يفحص خلايا أقل من الاستدلال الثابت.

خطوات الحل:

1. **الشرح:** هنا نفحص تأثير استخدام دالة استدلال أكثر ذكاءً، وهي مسافة مانهاتن، على الخوارزميات في حالتها الموزونة وغير الموزونة. أولاً، خوارزمية BFS، سواء كانت موزونة أو غير موزونة، لا تستخدم دالة استدلال على الإطلاق. فهي تبحث بشكل منهجي (طبقة تلو الأخرى) بناءً على التكلفة المتراكمة (في الموزون) أو عدد الخطوات (في غير الموزون). لذلك، دالة استدلال مانهاتن لا تؤثر على سلوكها أو نتائجها؛ مسارها وعدد الخلايا المفحوصة يبقيان كما هو محسوب بواسطة BFS. ثانياً، خوارزمية A* تستفيد من الدالة الاستدلالية. مسافة مانهاتن (مجموع الفروق المطلقة في الإحداثيات الأفقية والرأسية بين الخلية الحالية والهدف) تعطي تقديراً جيداً للمسافة المتبقية في الشبكات حيث الحركة الأفقية/الرأسية فقط مسموحة، أو تكون تكلفتها هي الأساس. حتى في الحالة الموزونة أو مع الحركات القطرية، تظل أداة توجيه قوية. عند استخدام استدلال مانهاتن مع A* (مقارنةً باستخدام استدلال ثابت)، تصبح الخوارزمية "أكثر توجيهاً" نحو الهدف. فهي تفضل استكشاف الخلايا التي يُقدّر أنها أقرب إلى الهدف، مما يقلل من عدد الخلايا غير الضرورية التي يتم فحصها. لذلك، سواء في النسخة الموزونة أو غير الموزونة، من المتوقع أن يفحص A* (باستدلال مانهاتن) عدداً أقل من الخلايا مقارنةً بـ A* (باستدلال ثابت) للوصول إلى نفس الحل الأمثل، مما يجعلها أكثر كفاءة.

سؤال 1: عدل المقطع البرمجي لخوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل (A* search) الموزونتين بتغيير الأوزان الأفقية والرأسية إلى 3 والأوزان القطرية إلى 5، وكذلك عدّل نقطة البداية إلى (7, 2).

• أ) تغيير الأوزان الأفقية والرأسية إلى 3، والأوزان القطرية إلى 5، ونقطة البداية إلى (7, 2)
• ب) تغيير الأوزان الأفقية والرأسية إلى 5، والأوزان القطرية إلى 3، ونقطة البداية إلى (2, 7)
• ج) تغيير الأوزان الأفقية والرأسية إلى 2، والأوزان القطرية إلى 4، ونقطة البداية إلى (7, 2)
• د) تغيير الأوزان الأفقية والرأسية إلى 3، والأوزان القطرية إلى 5، ونقطة البداية إلى (2, 7)

الإجابة الصحيحة: يجب تعديل المقطع البرمجي بتغيير الأوزان الأفقية والرأسية إلى 3، والأوزان القطرية إلى 5، وتغيير إحداثيات نقطة البداية إلى (7, 2) لكل من خوارزميتي BFS وA* search الموزونتين.

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

تلميح: راجع متغيرات الأوزان وإحداثيات البداية في الكود.

سؤال 2: ما المسار الجديد ذو المسافة الأقصر، وما عدد الخلايا التي فحصت في الإصدارات غير الموزونة لخوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search) باستخدام دالة الاستدلال الثابت؟ حدد هذه القيم ودون ملاحظاتك.

• أ) تحديد المسار الأقصر وعدد الخلايا المفحوصة لـ BFS وA* search غير الموزونتين
• ب) تحديد المسار الأقصر فقط لـ BFS وA* search
• ج) تحديد عدد الخلايا المفحوصة فقط لـ BFS وA* search
• د) تحديد المسار الأقصر لـ BFS فقط

الإجابة الصحيحة: يجب تحديد المسار الأقصر الجديد وعدد الخلايا المفحوصة لكل من BFS وA* search غير الموزونتين باستخدام دالة الاستدلال الثابت، مع تدوين الملاحظات.

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

تلميح: شغل الخوارزميات بعد التعديلات وسجل المخرجات.

سؤال 3: اتبع الخطوات نفسها للإصدارات الموزونة من خوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search) باستخدام دالة الاستدلال الثابت.

• أ) تطبيق نفس الخطوات على BFS وA* search الموزونتين باستخدام دالة الاستدلال الثابت
• ب) تطبيق خطوات مختلفة على BFS وA* search الموزونتين
• ج) تطبيق نفس الخطوات على BFS فقط
• د) تطبيق نفس الخطوات على A* search فقط

الإجابة الصحيحة: يجب تطبيق نفس خطوات السؤال السابق (تحديد المسار الأقصر وعدد الخلايا المفحوصة) على الإصدارات الموزونة من BFS وA* search باستخدام دالة الاستدلال الثابت.

الشرح: هذا امتداد للسؤال السابق، لكن للإصدارات الموزونة من الخوارزميات، مما قد يغير النتائج بسبب الأوزان المختلفة.

تلميح: كرر عملية التشغيل والتسجيل للخوارزميات الموزونة.

سؤال 4: كرر العملية للإصدارات غير الموزونة والموزونة من خوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search) باستخدام دالة استدلال مانهاتن (Manhattan Heuristic).

• أ) تكرار العملية لـ BFS وA* search غير الموزونة والموزونة باستخدام دالة استدلال مانهاتن
• ب) تكرار العملية لـ BFS فقط باستخدام دالة استدلال مانهاتن
• ج) تكرار العملية لـ A* search فقط باستخدام دالة استدلال مانهاتن
• د) تكرار العملية لـ BFS وA* search غير الموزونة فقط

الإجابة الصحيحة: يجب تكرار عملية تحديد المسار الأقصر وعدد الخلايا المفحوصة لكل من الإصدارات غير الموزونة والموزونة من BFS وA* search، ولكن باستخدام دالة استدلال مانهاتن بدلاً من الثابت.

الشرح: هذا يوسع التجربة لاستخدام دالة استدلال مختلفة (مانهاتن)، والتي قد تؤثر على كفاءة ونتائج خوارزمية A* search.

تلميح: غير دالة الاستدلال في الكود إلى مانهاتن وكرر التجارب.

ما هو التعديل المطلوب على المقطع البرمجي لخوارزميتي BFS و A* search بتغيير الأوزان المذكورة؟

الإجابة: يجب تغيير الأوزان الأفقية والرأسية إلى 3 والأوزان القطرية إلى 5، بالإضافة إلى تعديل نقطة البداية إلى (7, 2).

الشرح: التعليمات تطلب تعديل المقطع البرمجي بخوارزميتي BFS و A* search بتحديد قيم جديدة للأوزان (أفقي، رأسي، قطري) وتغيير نقطة البداية.

تلميح: ركز على الأرقام المحددة للأوزان ونقطة البداية المذكورة في التعليمات.

ما هو المسار الجديد ذو المسافة الأقصر وعدد الخلايا المفحوصة في الإصدارات غير الموزونة لخوارزميتي BFS و A* search باستخدام دالة الاستدلال الثابت؟

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

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

تلميح: هذا السؤال يتطلب تطبيق عملي للخوارزميات المذكورة في سياق الشبكة المحددة.

ما هي الاعتبارات عند اتباع نفس الخطوات للإصدارات الموزونة من خوارزميتي BFS و A* search باستخدام دالة الاستدلال الثابت؟

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

الشرح: الإصدارات الموزونة تأخذ تكلفة الانتقال بين الخلايا في الاعتبار، مما يعني أن المسار الذي قد يبدو أطول هندسياً قد يكون أقل تكلفة بسبب الأوزان.

تلميح: ما هو الاختلاف الرئيسي بين البحث الموزون وغير الموزون؟

ما هي التغييرات المتوقعة عند تكرار العملية للإصدارات غير الموزونة والموزونة من خوارزميتي BFS و A* search باستخدام دالة استدلال مانهاتن؟

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

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

تلميح: كيف تختلف دالة استدلال مانهاتن عن دالة الاستدلال الثابت؟