خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع | الوحدة الثانية | الدرس الثاني
خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع هو عنوان الدرس الثاني من الوحدة الثانية التي تحمل اسم “خوارزميات الذكاء الاصطناعي” من الفصل الدراسي الأولى من مقرر “الذكاء الاصطناعي”.
ستتعرف في هذا الموضوع على خوارزميات البحث ومنها: خوارزمية البحث بأولوية الاتساع وخوارزمية البحث بأولوية العمق، واستخدام التطبيقات العملية لهما، بالإضافة إلى التمييز بين خوارزميات البحث والمقارنة بينها.
لذا قم بقراءة أهداف التعلُّم بعناية، ثم أعد قراءتها وتأكَّد من تحصيل كافة محتوياتها بعد انتهائك من دراسة الموضوع.
أهداف التعلُّم
- معرفة خوارزمية البحث بأولوية الاتساع.
- استخدام التطبيقات العملية لخوارزمية البحث بأولوية الاتساع.
- معرفة خوارزمية البحث بأولوية العمق.
- استخدام التطبيقات العملية لخوارزمية البحث بأولوية العمق.
- التمييز بين خوارزميات البحث.
هيا لنبدأ!
البحث في المُخطَّطات (Searching in Graphs)
هناك بعض الحالات التي نحتاج فيها إلى البحث عن عقدة محددة في المخطط، أو تفحص كل عقدة في المخطط لإجراء عملية بعينها مثل: طباعة عقد المخطط، فتكون حالتك كشخص يبحث عن المدينة التي يريد السفر إليها، وليتحقق هذا،
تحتاج إلى فحص كل عقدة في المخطط حتى تجد تلك التي تحتاج إليها، يُطلق على هذا الإجراء:
- البحث في المخطط.
- مسح المخطط.
وهناك العديد من الخوارزميات التي تساعد على تنفيذه مثل:
- خوارزمية البحث بأولوية الاتساع (Breadth-First Search – BFS).
- خوارزمية البحث بأولوية العمق (Depth-First Search – DFS).
خوارزمية البحث بأولوية الاتساع (Breadth-First Search (BFS) Algorithm)
تستكشف خوارزمية البحث بأولوية الاتساع (BFS) المخطط بحسب المستوى واحدًا تلو الآخر.
تبدأ بفحص عقدة الجذر (عقدة البداية)، ثم تفحص جميع العقد المرتبطة بها بشكل مباشر واحدة تلو الأخرى.
بعد الانتهاء من فحص كل العقد في المستوى، تنتقل إلى المستوى التالي، وتتبع الإجراءات نفسها كما هو موضح في الشكل التالي.
يُستخدم الطابور لتتبع العقد التي تم فحصها، وبمجرد استكشاف العقدة، ستتم اضافة العقد الفرعية إلى الطابور ثم تُحذف العقدة التالية الموجودة في أول الطابور التي تم استكشافها سابقًا.
المثال التالي يوضح طريقة عمل خوارزمية البحث بأولوية الاتساع (BFS)، باستخدام المخطط التالي حدد العقد التي يجب فحصها للانتقال من عقدة الجذر A إلى العقدة F:
ملاحظة: استخدم هيكل البيانات المناسب.
لاحظ كيف يمكنك تطبيق خوارزمية البحث بأولوية الاتساع (BFS) بلغة البايثون (Python) في المثال التالي:
لمعرفة المزيد من المعلومات عن خوارزمية البحث بأولوية الاتساع، قم بالاطّلاع على الرابط التالي:
البحث المتسع الأول – ويكيبيديا
التطبيقات العملية لخوارزمية البحث بأولوية الاتساع (Practical Applications of the BFS Algorithm)
معلومة
يُمكِن تطوير خوارزمية البحث بأولوية الاتساع (BFS) بتحديد نقطة البداية (الحالة الأوليّة) ونقطة الهدف (الحالة المُستهدَفة) لإيجاد المسار بينهما.
بإمكانك مراجعة محتوى موضوع “خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع” من بدايته وحتى نهاية هذا القسم، من خلال الرابط التالي:
خوارزمية البحث بأولوية العمق (Depth-First Search (DFS) Algorithm)
في البحث بأولوية العمق (DFS)، ستقوم باتباع الحواف، وتتعنق أكثر وأكثر في المخطط.
يستخدم البحث بأولوية العمق إجراء استدعاء تكراري للتنقل عبر العقد، عند الوصول إلى عقدة لا تحتوي على أي حواف لأي عقدة جديدة، ستعود إلى العقدة السابقة وتستمر العملية.
تستخدم خوارزمية البحث بأولوية العمق هيكل البيانات المُكدّس لتتبع مسار الاستكشاف، بمجرد استكشاف عقدة، ستُضاف إلى المُكدّس، عندما ترغب في العودة، ستحذف العقدة من المُكدّس كما هو موضح في الشكل التالي:
المثال التالي يوضح طريقة عمل خوارزمية البحث بأولوية العمق(DFS) ، باستخدام المخطط التالي، تتبع ترتيب استكشاف العقد (Traversal) بحسب خوارزمية البحث بأولوية العمق.
لاحظ أن
العُقد التي فُحِصَت باستخدام خوارزمية البحث بأولوية العمق (DFS) هي: A، B، D، E، C، F.
الآن سنتعلم طريقة تنفيذ خوارزمية البحث بأولوية العمق (DFS) في لغة البايثون.
لمعرفة المزيد من المعلومات عن خوارزمية البحث بأولوية العمق، قم بالاطّلاع على الرابط التالي:
البحث المتعمق الأول – ويكيبيديا
التطبيقات العملية لخوارزمية البحث بأولوية العمق (Practical Applications of the DFS Algorithm)
مقارنة بين خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS)
بإمكانك مراجعة محتوى موضوع “خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع” بدايةً من عنوان “خوارزمية البحث بأولوية العمق” وحتى نهاية الموضوع، من خلال الرابط التالي:
اختبر تحصيلك لمحتوى الموضوع من خلال الرابط التالي:
الواجب الإلكتروني
إلى هنا يكون قد انتهى موضوع “خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع”، لا تنسوا مراجعة أهداف التعلُّم أعلى المقال، وانتظرونا في الموضوع القادم!