أنواع خوارزميات البحث
يوجد الكثير من آليات وطرائق البحث في الذكاء الاصطناعي، وتختلف خوارزميات حسب الترتيب الذي تختار فيه النقاط في شجرة البحث في أثناء البحث عن الحالة الهدف.
تعلّم:
- الخوارزميات لا تملك أي معلومات مسبقة عن المسألة التي ستقوم بحلها
- تستخدم خوارزميات البحث إستراتيجية ثابتة للبحث، بحيث تفحص كل حالات الفضاء واحدة تلو الأخرى، لمعرفة إذا كانت مطابقة للهدف المطلوب أم غير مطابقة.
- الشيء الوحيد الذي يمكن لهذه الخوارزميات القيام به هو تمييز بين حالة غير الهدف من حالة الهدف
أنواع خوارزميات البحث:
1. البحث في العمق أولا
2. خوارزميـة البحـث فـي العـرض أولا
3. الخوارزمية الحدسية
خوارزمية البحث في العمق أولا:
تأخذ خوارزمية البحث في العمق أولا المسار أقصى اليسار في شجرة البحث وتفحصه بالاتجاه إلى الأمام حتى تصل إلى نقطة ميتة، تعود إلى الخلف إلى أقرب نقطة في الشجرة يكون فيها تفرع آخر لم يفحص، ويختبر ذلك المسار حتى نهايته، ثم تكرر العملية للوصول إلى الهدف.
تعلّم :
- خوارزمية البحث في العمق أولا تقف عند الوصول إلى نقطة الهدف
- خوارزمية البحث في العمق أولا لا تعطي المسار الأقصر للحلّ
- النقطة الميتة ليست نقطة الهدف
- خوارزمية البحث في العمق أولا تسمى أيضا خوارزمية البحث الرأسي
مثال (1): تأمل في الشكل المجاور ثم أجب عن السؤال الآتي ؟
1.ما مسار البحث عن نقطة الهدف (N) باستخدام خوارزمية البحث في العمق أولا؟
تبدأ عملية البحث في خوارزمية البحث في العمق أولا من الحالة الابتدائية أو جذر الشجرة (A) ثم نختار المسار في أقصى اليسار (B) ثم (D) ثم (I) ونقارن كل نقطة أو حالة مع النقطة الهدف (N) بعد الوصول إلى (I) التي تعد نقطة ميتة (لأنه لا توجد نقطة فرعية)، نرجع إلى الخلف إلى النقطة السابقة (D)لاحظ أن تم فحص النقطة (D) سابقا لذا تُكرّر هذه النقطة في مسار البحث، عند النقطة (D) يوجد نقطة فرعيـة لـم يتم فحصها أو اختبارها فتتم عملية تتبع هذا المسار (ل) فنصل إلى نقطة ميتة، فنرجع مرة أخرى إلى الخلف إلى (D) والتي اختُبرت جميع مساراتها فنرجع مرة أخرى إلى الخلف إلى النقطة (B) حيث نجد أن نقطة (E)لم تُختبر وبعد ذلك نختار المسار أقصى اليسار فنصل إلى النقطة (K) التي تعدّ نقطة ميتة فنرجع للخلف ثم نكرر هذه العملية إلى أن نصل للنقطة الهدف وبناءً على ما سبق فإن مسار البحث عن الحل باستخدام خوارزمية البحث في العمق أولاً هي : A-B-D-I-J-E-K-L-M-C-F-N
لاحظ أن خوارزمية البحث توقفت عند الوصول إلى النقطة الهدف ولم تقم بالمرور أو فحص النقاط G,H,O,P
مثال (2): تأمل في الشكل المجاور ثم أجب عن الأسئلة الآتية ؟
1.جد مسار البحث عن حالة الهدف في شجرة البحث باستخدام خوارزمية البحث في العمق أولا، علما بأن نقطة الهدف هـو فـوز اللاعب (X) :
(S-D-E-F-G)
2. هل يوجد مسار آخر للحل؟ ما هو؟ وهل يمكن الوصول إليه باستخدام
خوارزمية البحث في العمق أولا
يوجد مساران آخران، هما: (S-H-J-K) (S-C)
ولا يمكن الوصول إليها باستخدام خوارزمية البحث في
العمق أولا
مثال ( 3): تأمل بالشكل المجاور ثم أجب عن الأسئلة الآتية؟
1. جد مسار البحث عن حالة الهدف في شجرة البحث باستخدام خوارزمية البحث في العمق أولا، علما بأن النقطة الهدف هـي E ؟ R-A-C-D-B-E
2. إذا علمت أن خوارزمية البحث في العمق أولا توقفت عند الوصول إلى النقطة الهدف E ، اذكر النقاط التي لم تقم بالمرور بها أو فحصها ؟ النقطة F