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