البحث الاعمى

المادة: الذكاء الاصطناعي (Artificial Intelligence)

المرحلة الرابعة / ( المحاضرة 5)

المصدر: ترجمة (Artificial Intelligence / George F. Luger)

1. خوارزميات البحث

 

• البحث:دراسة لطرائق البحث مع قاعدة المعرفة, و المقارنة بينها للوصول للهدف بأقل وقت و أقل تكلفة.
• يتم تقسيم خوارزميات البحث إلى نوعين:

• أ‌-خوارزميات البحث الأعمى (Blind Search) و تتضمن خوارزميتين:

• خوارزمية البحث العمودي (Depth First Search) و تكتب اختصاراً (DFS).
• خوارزمية البحث الأفقي (Breadth First Search) و تكتب اختصاراً (BFS).

• ب‌-خوارزميات البحث الموجه (Heuristic Search) و تتضمن خوارزميتين:

• خوارزمية تسلق الجبل (Hill Climbing).
• خوارزمية (A*).

1. البحث الأعمى (Blind Search)

1. خوارزمية البحث العمودي (DFS)

   Function depth_first_search;

   begin

       open:=[Start];

       close:=[];

       while open ≠ [] do

           begin

               remove leftmost state from open, call it X;

               if X is a goal then return SUCCESS

                  else begin

   generate children of X;

                     put X on closed;

                     discard children of X if already on open or closed;

                     put remaining children on left end of open

                 end

         end;

    return FAIL

   end.

2. خوارزمية البحث الأفقي (BFS)

   Function breadth_first_search;

   begin

       open:=[Start];

       close:=[];

       while open ≠ [] do

           begin

               remove leftmost state from open, call it X;

               if X is a goal then return SUCCESS

                  else begin

                     generate children of X;

                     put X on closed;

                     discard children of X if already on open or closed;

                     put remaining children on right end of open

                 end

         end;

    return FAIL

   end.

1. فوائد البحث الأعمى (Blind Search Advantages)

• فوائد البحث العمودي

1. 1.(DFS) يحتاج إلى ذاكرة أقل لأنه يخزن العقد التي في مساره الحالي. هذا يتناقض مع (BFS) الذي يقوم بخزن الشجرة المولَّدة كاملةً.
2. 2.(DFS) من الممكن أن يجد الحل بدون اختبار فضاء البحث كله. هذا يتناقض مع (BFS) الذي يجب أن يختبر كل أجزاء الشجرة ابتداء من العقد في المستوى (N) إلى العقد في المستوى (N+1).و هذا الشيء مهم لأن (DFS) يتوقف أينما يجد الهدف حتى لو كان هناك أكثر من هدف.

• فوائد البحث الأفقي

1. 1.(BFS) لا يقع في مصيدة البحث الأعمى. هذا يتناقض مع (DFS) الذي يتبع طريق وحيد و غير مثمر و لفترة طويلة. و هذه تعتبر مشكلة في (DFS) إذا كانت هناك حلقات لم تؤخذ بعناية خاصة و الذي بدوره يؤدي إلى التوسع في الاختبار للوصول إلى الحل.
2. إذا كان هناك حلاً, فإن (BFS) يضمن وجوده. و أكثر من ذلك, إذا كانت هناك حلول متعددة, فإن (BFS) سوف يجد الحل الأمثل (أقصر الحلول), وهذا مضمون لأن المسارات الأطول لن يتم بحثها حتى يتم بحث المسارات الأقصر.