تمرينات على خوارزميات البحث BFS و DFS - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

سؤال 1: حدد الجملة الصحيحة والجملة الخاطئة فيما يلي: 1. تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام الاستدعاء الذاتي. 2. لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) في هيكل بيانات الشجرة. 3. تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) بمساعدة هيكل بيانات القائمة المترابطة. 4. يمكن تنفيذ خوارزمية البحث بأولوية العمق (DFS) بمساعدة هيكل بيانات المكدس. 5. لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) في البحث الشبكي.

الإجابة: س1: 1) X خطأ 2) X خطأ 3) ✓ صح 4) ✓ صح 5) X خطأ

خطوات الحل:

1. **الشرح:** لنفهم هذا السؤال، علينا تحليل كل جملة على حدة بناءً على مفاهيم خوارزميات البحث BFS وDFS. **الجملة 1:** تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام الاستدعاء الذاتي. - الاستدعاء الذاتي (Recursion) هو أسلوب برمجي تستدعي فيه الدالة نفسها. - خوارزمية DFS يمكن تنفيذها باستخدام الاستدعاء الذاتي لأنها تتبع مبدأ "التعمق ثم التراجع" الذي يتناسب مع هذا الأسلوب. - خوارزمية BFS لا تُنفّذ عادةً بالاستدعاء الذاتي لأنها تزور العقد مستوى بمستوى، مما يتطلب هيكل بيانات مثل قائمة الانتظار (Queue) لإدارة العقد المراد زيارتها. - إذن هذه الجملة **خاطئة** لأنها تنطبق على DFS فقط وليس على BFS. **الجملة 2:** لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) في هيكل بيانات الشجرة. - الشجرة هي نوع من الرسوم البيانية (Graphs) بدون حلقات. - خوارزميات BFS وDFS مصممة أساساً للبحث في الرسوم البيانية، بما في ذلك الأشجار. - في الواقع، الأشجار هي حالة خاصة من الرسوم البيانية، لذا يمكن تطبيق BFS وDFS عليها بسهولة. - إذن هذه الجملة **خاطئة**. **الجملة 3:** تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) بمساعدة هيكل بيانات القائمة المترابطة. - خوارزمية BFS تستخدم قائمة انتظار (Queue) لإدارة العقد. - القائمة المترابطة (Linked List) يمكن استخدامها لبناء قائمة انتظار. - إذن من الناحية العملية، يمكن تنفيذ BFS باستخدام قائمة مترابطة لتمثيل قائمة الانتظار. - هذه الجملة **صحيحة**. **الجملة 4:** يمكن تنفيذ خوارزمية البحث بأولوية العمق (DFS) بمساعدة هيكل بيانات المكدس. - خوارزمية DFS تتبع مبدأ "آخر ما يدخل أول ما يخرج" (LIFO). - المكدس (Stack) هو هيكل بيانات يعمل بمبدأ LIFO، وهو مناسب جداً لتنفيذ DFS. - إذن هذه الجملة **صحيحة**. **الجملة 5:** لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) في البحث الشبكي. - البحث الشبكي (Network Search) يشير عادةً إلى البحث في شبكات مثل الإنترنت أو الشبكات الاجتماعية. - خوارزمية BFS تستخدم على نطاق واسع في البحث الشبكي، مثل في محركات البحث للزحف إلى الصفحات مستوى بمستوى. - إذن هذه الجملة **خاطئة**. **النتيجة النهائية:** إذن الإجابة هي: 1) خطأ 2) خطأ 3) صح 4) صح 5) خطأ

سؤال 2: اشرح كيف تعمل خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS).

الإجابة: س2: خوارزمية BFS: تبدأ من العقدة (الجذر) وتزور العقد مستوى بمستوى (تزور الجيران أولاً)، وتستخدم عادة قائمة انتظار (Queue) لحفظ العقد التي سيتم زيارتها لاحقًا. س2: خوارزمية DFS: تبدأ من العقدة وتتجه للأعمق قدر الإمكان ثم تتراجع (Backtracking)، وتُنفّذ عادةً باستخدام المكدس (Stack) أو الاستدعاء الذاتي.

خطوات الحل:

1. **الشرح:** لنفهم كيف تعمل خوارزميتا البحث BFS وDFS، تخيل أنك تبحث عن شيء في متاهة أو شبكة من الغرف المتصلة. **خوارزمية البحث بأولوية الاتساع (BFS):** - الفكرة الأساسية: تبدأ من نقطة البداية (تسمى العقدة الجذر في الشجرة أو الرسم البياني) وتزور جميع العقد المجاورة لها أولاً قبل التوجه إلى العقد الأبعد. - التشبيه: كأنك تبحث في مبنى تزور كل الطوابق بالترتيب (الطابق الأول كله، ثم الثاني، ثم الثالث...). - آلية العمل: 1. تضع العقدة الأولى (الجذر) في قائمة انتظار (Queue). 2. تزور العقدة الأولى وتخرجها من قائمة الانتظار. 3. تضيف جميع العقد المجاورة غير المزورة إلى قائمة الانتظار. 4. تكرر الخطوات حتى تنتهي من زيارة جميع العقد أو تجد الهدف. - مثال: إذا كان لديك شجرة، BFS تزور المستوى الأول (الأبناء المباشرين للجذر)، ثم المستوى الثاني (أحفاد الجذر)، وهكذا. **خوارزمية البحث بأولوية العمق (DFS):** - الفكرة الأساسية: تبدأ من نقطة البداية وتتجه في اتجاه واحد بعمق قدر الإمكان حتى تصل إلى نهاية الطريق، ثم تعود للخلف (تراجع) لتجرب طريقاً آخر. - التشبيه: كأنك تبحث في متاهة وتسير في طريق واحد حتى تصل إلى طريق مسدود، ثم تعود إلى آخر مفترق طرق وتجرب طريقاً آخر. - آلية العمل: 1. تبدأ من العقدة الأولى. 2. تزور عقدة مجاورة وتستمر في التعمق عبر عقدها المجاورة. 3. عندما تصل إلى عقدة ليس لها عقد مجاورة غير مزارة (طريق مسدود)، تعود للخلف (تراجع) إلى العقدة السابقة. 4. تكرر هذه العملية حتى تنتهي من زيارة جميع العقد أو تجد الهدف. - يمكن تنفيذ DFS باستخدام المكدس (Stack) يدوياً أو باستخدام الاستدعاء الذاتي (Recursion) في البرمجة. إذن، BFS تبحث "عرضياً" مستوى بمستوى، بينما DFS تبحث "عمودياً" بالتعمق ثم التراجع.

سؤال 3: قارن بين خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS).

الإجابة: س 3: طريقة الزيارة: BFS مستوى بمستوى، DFS يتعمق ثم يتراجع. س3: هيكل البيانات: BFS قائمة انتظار (Queue)، DFS مكدس (Stack). س3: أقصر مسار: BFS يجد أقصر مسار، DFS لا يضمن ذلك. س3: الذاكرة: BFS تستهلك ذاكرة أكبر، DFS أقل ذاكرة.

خطوات الحل:

1. **الخطوة 1 (المفهوم):** خوارزميتا BFS وDFS هما طريقتان أساسيتان للبحث في الرسوم البيانية (Graphs) والأشجار. لكل منهما خصائص مختلفة تناسب مواقف بحثية معينة. **الخطوة 2 (المقارنة):** لنقارن بينهما بناءً على عدة معايير: 1. **طريقة الزيارة:** - BFS: تزور العقد مستوى بمستوى (Level by Level). تبدأ من الجذر، ثم تزور جميع أبناء الجذر، ثم أحفاد الجذر، وهكذا. - DFS: تزور العقد بالتعمق أولاً (Depth First). تبدأ من الجذر وتتجه في فرع واحد حتى النهاية، ثم تعود لتجرب فرعاً آخر. 2. **هيكل البيانات المستخدم:** - BFS: تستخدم قائمة انتظار (Queue) التي تعمل بمبدأ "أول ما يدخل أول ما يخرج" (FIFO). - DFS: تستخدم مكدس (Stack) الذي يعمل بمبدأ "آخر ما يدخل أول ما يخرج" (LIFO)، أو يمكن تنفيذها بالاستدعاء الذاتي. 3. **إيجاد أقصر مسار:** - BFS: تضمن إيجاد أقصر مسار في رسم بياني غير موزون (Unweighted Graph) لأنها تبحث مستوى بمستوى. - DFS: لا تضمن إيجاد أقصر مسار؛ فقد تجد مساراً أطول لأنها تتعمق في اتجاه واحد. 4. **استهلاك الذاكرة:** - BFS: تستهلك ذاكرة أكبر لأنها تخزن جميع العقد في المستوى الحالي في قائمة الانتظار. - DFS: تستهلك ذاكرة أقل عادةً لأنها تتعقب مساراً واحداً في كل مرة. 5. **التطبيقات الشائعة:** - BFS: مناسبة للتطبيقات التي تحتاج أقصر مسار، مثل البحث في الشبكات الاجتماعية، أو خوارزميات الزحف في محركات البحث. - DFS: مناسبة للتطبيقات التي تحتاج استكشاف جميع الاحتمالات، مثل حل الألغاز (كالمتاهات)، أو في تحليل الدوائر الكهربائية. **الخطوة 3 (النتيجة):** إذن، BFS وDFS تختلفان في طريقة البحث وهيكل البيانات والكفاءة. اختيار إحداهما يعتمد على طبيعة المشكلة: إذا كنت تبحث عن أقصر مسار، فBFS أفضل؛ وإذا كانت الذاكرة محدودة أو تريد استكشاف عميق، فDFS قد تكون مناسبة.

سؤال 1: حدد الجملة الصحيحة والجملة الخاطئة فيما يلي:

الإجابة الصحيحة: انظر الأسئلة الفرعية

الشرح: هذا سؤال رئيسي يحتوي على أسئلة فرعية

تلميح: راجع الأسئلة الفرعية أدناه

سؤال 2: اشرح كيف تعمل خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS).

• أ) BFS تستخدم قائمة انتظار وتبدأ من الجذر، بينما DFS تستخدم مكدساً وتبدأ من الجذر
• ب) BFS تستخدم مكدساً وتبدأ من الجذر، بينما DFS تستخدم قائمة انتظار وتبدأ من الجذر
• ج) كلاهما يستخدمان قائمة انتظار ويبدآن من العقدة الأخيرة
• د) كلاهما يستخدمان مكدساً ويبدآن من العقدة الأخيرة

الإجابة الصحيحة: خوارزمية البحث بأولوية الاتساع (BFS) تعمل باجتياز المستويات بشكل أفقي، حيث تبدأ من العقدة الجذر وتزور جميع العقد المجاورة أولاً قبل الانتقال إلى المستوى التالي، باستخدام قائمة انتظار (Queue). خوارزمية البحث بأولوية العمق (DFS) تعمل باجتياز المسارات بشكل عمودي، حيث تبدأ من العقدة الجذر وتستكشف أقصى عمق ممكن في كل فرع قبل العودة، باستخدام مكدس (Stack) أو الاستدعاء الذاتي.

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

تلميح: ركز على الفرق في استراتيجية الاجتياز وهياكل البيانات المستخدمة

سؤال 3: قارن بين خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS).

• أ) BFS تستخدم مكدساً وتبحث عميقاً، بينما DFS تستخدم قائمة انتظار وتبحش أفقيًا
• ب) BFS تستخدم قائمة انتظار وتبحث أفقيًا، بينما DFS تستخدم مكدساً وتبحث عميقاً
• ج) كلاهما يستخدمان قائمة انتظار ويبحثان أفقيًا
• د) كلاهما يستخدمان مكدساً ويبحثان عميقاً

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

الشرح: المقارنة تشمل استراتيجية الاجتياز (أفقي مقابل عمودي)، هيكل البيانات (قائمة انتظار مقابل مكدس)، التعقيد الزمني (O(V+E) لكليهما)، التعقيد المكاني (O(V) لـ BFS مقابل O(log V) لـ DFS في المتوسط)، والتطبيقات العملية.

تلميح: قارن من حيث الاستراتيجية، هياكل البيانات، التعقيد، والتطبيقات

سؤال 1: تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام الاستدعاء الذاتي.

الإجابة الصحيحة: خطأ

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

تلميح: تذكر هياكل البيانات المستخدمة في تنفيذ كل خوارزمية

سؤال 1: لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) في هيكل بيانات الشجرة.

الإجابة الصحيحة: خطأ

الشرح: يمكن استخدام كل من خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) في هيكل بيانات الشجرة، حيث تُستخدم لاجتياز العقد في الشجرة بطرق مختلفة.

تلميح: فكر في كيفية اجتياز الأشجار باستخدام BFS وDFS

سؤال 1: تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) بمساعدة هيكل بيانات القائمة المترابطة.

الإجابة الصحيحة: خطأ

الشرح: تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) عادةً باستخدام هيكل بيانات قائمة الانتظار (Queue) وليس القائمة المترابطة (Linked List) بشكل مباشر، رغم أن قائمة الانتظار يمكن تنفيذها باستخدام قائمة مترابطة.

تلميح: ما هو الهيكل الرئيسي المستخدم في تنفيذ BFS؟

سؤال 1: يمكن تنفيذ خوارزمية البحث بأولوية العمق (DFS) بمساعدة هيكل بيانات المكدس.

الإجابة الصحيحة: صحيح

الشرح: نعم، يمكن تنفيذ خوارزمية البحث بأولوية العمق (DFS) باستخدام هيكل بيانات المكدس (Stack)، سواء بشكل صريح أو ضمنيًا عبر الاستدعاء الذاتي.

تلميح: كيف يتم تخزين العقد في DFS؟

سؤال 1: لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) في البحث الشبكي.

الإجابة الصحيحة: خطأ

الشرح: يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) في البحث الشبكي، حيث تُستخدم للعثور على أقصر مسار في الشبكات أو الرسوم البيانية غير الموزونة.

تلميح: ما هي تطبيقات BFS في الشبكات؟

ما هي هياكل البيانات المستخدمة لتنفيذ خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS)؟

الإجابة: تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) بمساعدة هيكل بيانات القائمة (Queue)، بينما تُنفّذ خوارزمية البحث بأولوية العمق (DFS) بمساعدة هيكل بيانات المكدس (Stack).

الشرح: خوارزمية BFS تعمل بمبدأ 'من يدخل أولاً يخرج أولاً' (FIFO) وهو ما توفره القائمة. أما DFS فتعمل بمبدأ 'من يدخل أخيراً يخرج أولاً' (LIFO) وهو ما يوفره المكدس.

تلميح: فكر في كيفية استكشاف كل خوارزمية للعقد. هل تستكشف أقدم العقد أولاً أم أحدثها؟

ما هو التنفيذ الشائع لخوارزمية البحث بأولوية العمق (DFS)؟

الإجابة: تُنفّذ خوارزمية البحث بأولوية العمق (DFS) بمساعدة هيكل بيانات المكدس (Stack)، وغالباً ما يتم ذلك باستخدام الاستدعاء الذاتي (Recursion).

الشرح: الاستدعاء الذاتي هو شكل من أشكال استخدام المكدس بشكل ضمني. كل استدعاء للدالة يضع إطارًا على المكدس، وعندما تعود الدالة، يتم سحب الإطار من المكدس.

تلميح: ما هي التقنية التي تسمح للدالة باستدعاء نفسها، وكيف ترتبط هذه التقنية بطريقة عمل DFS؟

هل يمكن استخدام خوارزميات البحث بأولوية الاتساع (BFS) وأولوية العمق (DFS) في هيكل بيانات الشجرة؟

الإجابة: نعم، يمكن استخدام كل من خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) في هيكل بيانات الشجرة. غالباً ما تُستخدم BFS للتنقل بين المستويات، بينما تُستخدم DFS للتنقل في مسار محدد.

الشرح: الشجرة هي حالة خاصة من الرسم البياني. تسمح BFS بزيارة جميع العقد على مستوى معين قبل الانتقال للمستوى التالي، بينما تسمح DFS باستكشاف فرع كامل قبل العودة.

تلميح: فكر في كيفية تمثيل الشجرة. هل يمكن تطبيق مبادئ الاستكشاف المتسلسل (BFS) والتعمق (DFS) عليها؟

لماذا لا يمكن في بعض السياقات استخدام خوارزمية البحث بأولوية الاتساع (BFS) في البحث الشبكي؟

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

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

تلميح: ما هو التحدي الذي قد تواجهه الخوارزميات التي تستكشف مسارات مختلفة في هياكل بيانات قد تحتوي على حلقات؟