ألفا ويب - alfa web  ألفا ويب - alfa web
recent

أحدث المقالات

recent
برمجة
جاري التحميل ...

الذكاء الإصطناعي : البحث الشامل Exhaustive Search #الدرس الواحد و الثلاثون

البحث الشامل Exhaustive Search في الذكاء الإصطناعي
الذكاء الإصطناعي

البحث الشامل Exhaustive Search :

إضافةً إلى التقييد الخلفي و الأمامي الموضوحين في الدروس السابقة، هناك إستراتيجيات بحث مستخدمة في الذكاء الإحتسابي من خلال أغلب المنهجيات المستخدمة الشائعة : البحث الأفقي و البحث الرأسي. و يقال أن البحث الشامل إذا كان يضمن توليد جميع الحالات الممكن الوصول إليها قبل أن ينتهي بالفشل،  و تُستخدم للبحث الشامل أشجار القرار Decision Tree و هي تمثيل رسومي Graphical Representation لكل الحالات المحتملة و المسارات المرتبطة بها.

البحث بالعرض أو البحث الأفقي (BFS) :

البحث بالعرض أو البحث الأفقي Breadth First Search هو إستراتيجية بحث التي تكون فيها الطبقة العليا من شجرة القرار تبحث تماماً قبل الإستمرار إلى الطبقة التالية  في هذه الإستراتيجية، و لا يوجد حل قابل للحياة يحذف و لذلك يضمن إكتشاف  الحل المثالي، و هذه الإستراتيجية ليست مجدية عادة عندما يكون فضاء البحث كبيراً.

البحث بالعمق أو البحث الرأسي (DFS) :

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

إستراتيجية البحث الأفقي (بالعرض) :

و هي نفسها تقنية البحث الشامل Exhaustive Search Technique، البحث يولد جميع النقاط على مستوى معين قبل الوصول إلى المستوى التالي للشجرة، البحث بشكل منظم تستمر باختيار كل نقطة تصل إليها من النقطة الأب. البحث يستمر نظامياً باختيار كل نقطة ممكنة الوصول إليها من النقطة الأب، قبل أن تتوسع إلى أي حد واحد من النقاط الأبناء، و يضمن نظام التحكم أن فضاء الإنتقالات الممكنة قد تم إختباره بالنْتِضام، و يتطلب هذا البحث أخذ موارد الذاكرة بالإعتبار، و الفضاء الذي نصل إليه يكون بحجم متوسط، و الحل قد يكون الإختبار صائباً.

إستراتيجية البحث الرأسي (بالمعمق) : 

هي تقنية بحث شامل للوصول إلى المستوى المطلوب، و هنا يكون البحث و هنا يكون البحث مستمراً حتى العمق d، قبل أن نأخذ مساراً آخر بالإعتبار، فإذا كان العمق الأقصى  لشجرة البحث هو ثلاثة 3، و من ثم إذا إذا كانت هذه الحدود قابلة للوصول و لم يتم الحصول على الحل، عندئذٍ يتم العودة إلى المستوى السابق واستِكشاف أي بديل متبقي في نفس المستوى، و هكذا.
و إجراءات التتبع الخلفي هي التي تظمن تنظيم و شمولية إختبار جميع المسارات الممكنة، و إذا كانت الشجرة عميقة جداً و كان العمق الأقصى للبحث أقل من العمق الأقصى للشجرة، عندئذٍ يكون هذا الإجراء المطبق و يسمى Exhaustive Modulo of Depth.

التعميق التكراري للبحث بالعمق (DFID) :

تعتبر DFID نوع آخر من إجراءات البحث الشامل التي تكون مزيجًا من البحث بالعمق و البحث بالعرض. و هذه هي خطوات الخوارزمية Algorithm : Steps :
  • أولاً : نُنْجِز بحث رأسياً (بالعمق) إلى عمق واحد
  • ثم : نبدأ بحثاً جديداً (بالعمق) في العمق الثاني، بتجاهل النقاط الناتجة عن البحث السابق.
  • ثم : نذهب للعمق الثالث ببحث رأسي (بالعمق) حتى الوصول إلى حالة الهدف.

خوارزميات البحث بالعمق :

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

Put the root node on a stack;
while (stack is not empty)
{ remove a node from the stack;
if (node is a goal node) return success;
put all children of node onto the stack; }
return failure;
- ملاحظات :
  • في كل خطوة يتكون المكدس من بعض النقاط أي مستوى يمر به.
  • حجم المكدس المطلوب يعتمد على عامل التفرع b.
  • في مستوى البحث n، يحتوي المكدس تقريباً على n * b نقطة.
  • و عندما تنجح هذه الطريقة؛ فهي لا تعطينا المسار.
  • و لكي نسجل مسار البحث نحتاج إلى الخوارزمية (Recursive depth_first search) و مكدس كبير الحجم.

خوارزمية البحث الأفقي :

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

Put the root node on a queue;
while (queue is not empty)
{ remove a node from the queue;
if (node is a goal node) return success;
put all children of node onto the queue; }
return failure;
- ملاحظات :
  • يتم تحميل الطابور بجميع النقاط من المستوى n، قبل البدأ في إستكشاف ذلك المستوى.
  • في الشجرة المثالية يكون عدد النقاط يتزايد في كل مستوى طردياً مع العمق.
  • متطلبات الذاكرة Memory Requirements قد تكون كافية.

مقارنة بين البحث الرأسي و الأفقي :

1. مقارنة المميزات :

- البحث الرأسي: 
  • عند النجاح فإن النقطة الهدف المكتشفة لا تكون بالضرورة بالعمق الأدنى.
  • الشجرة الكبيرة قد تتطلب ذاكرة مفرطة الحجم، و ذلك حتى لإيجاد نقطة نقطة قريبة للهدف.
- البحث الأفقي:
  • عند النجاح نحصل على المسار الأدنى و الأقرب للجذر لنقطة الهدف.
  • الشجرة الكبيرة قد تتطلب ذاكرة مفرطة الحجم.

2. الخوارزميات:

لهما نفس الخوارزمية لكن تكون خوارزمية البحث الرأسي باستخدام الطابور Queue، أما خوارزمية البحث الأفقي تكون باستخدام المكدس Stack. كما أوضحنى ذلك في الأعلى.

عن الكاتب

Mr Salah

التعليقات


جميع الحقوق محفوظة

ألفا ويب - alfa web