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