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