خوارزميات البحث في الذكاء الاصطناعي
لقد صمم باستخدام الذكاء الاصطناعي عدد كبير من خوارزميات البحث لحل أصعب المشكلات في الكثير من التطبيقات، ومن الأمثلة على هذه التطبيقات عمليات الملاحة .
مفهوم خوارزميات البحث:
هي سلسلة من الخطوات غير المعروفة مسبقا، للعثور على الحل الذي يطابق مجموعة من المعايير من بين مجموعة من الحلول المحتملة.
ملاحظة:
- خوارزميات البحث هي سلسلة من الخطوات غير المعروفة مسبقاً.
- مبدأ عمل خوارزميات البحث: أخذ المشكلة على أنها مدخلات، ثم القيام بسلسلة من العمليات والتوقف عند الوصول إلى الهدف
وجدت خوارزميات البحث في الذكاء الاصطناعي؛ لحل مشكلات ذات صفات ،أذكر هذه الصفات ؟
- لا يوجد الحل طريقة تحليلية واضحة، أو أن الحل مستحيل بالطرائق العادية
- يحتاج الحل إلى عمليات حسابية كثيرة ومتنوعة لإيجاده (مثل الألعاب، والتشفير وغيرها) .
- يحتاج الحل إلى حدس عالي (مثل الشطرنج)
ملاحظة : للتعبير عن هذا النوع من المشكلات، تمثل باستخدام شجرة البحث.
شجرة البحث:
هي الطريقة المستخدمة للتعبير عن المسألة (المشكلة) لتسهيل عمليات البحث عن الحلول الممكنة من خلال خوارزميات البحث
تعلّم :
- بعض المشكلات المعقدة يصعب وصفها بطريقة شجرة البحث
- تجد شجرة البحث حلة محتملة للمشكلة عن طريق النظر في البيانات المتاحة بطريقة منظمة تعتمد على هيكلية الشجرة
وفي ما يأتي توضيح لأهم المفاهيم في شجرة البحث:
|
أ - مجموعة من النقاط أو العقد |
النقاط التي تنظم بشكل هرمي (مستويات مختلفة) |
|
ب - مستويات الشجرة |
تأخذ بشكل عرضي |
| ج- حالات فضاء البحث |
هي النقاط الممكنة جميعها |
| د - جذر الشجرة |
هو النقطة الموجودة أعلى الشجرة، وهو الحالة الابتدائية للمشكلة وهي نقطة البداية التي نبدأ منها البحث |
| هـ - الأب |
هو النقطة التي تتفرع منها نقاط أخرى والنقاط المتفرعة منها تسمى الأبناء |
|
و- النقطة الميتة |
النقطة التي ليس لديها أبناء |
|
ي - النقطة الهدف أو حالة الهدف |
هي الهدف المطلوب الوصول إليه أو الحالة النهائية للمشكلة |
| ل - المسار |
هو مجموعة من النقاط المتتالية في شجرة البحث من الحالة الابتدائية أو جذر الشجرة إلى الحالة الهدف |
تعلّم :
- تكتب حالات فضاء البحث بوضع فواصل بين كل رمز والآخر
- يكتب مسار البحث ويقرأ من اليسار لليمين، وتوضع إشارة (-) للفصل بين الرموز كما يمكن استخدام أي رمز آخر ما عدا الفاصلة
- خوارزميات البحث لا تملك أي معلومات مسبقة عن المسألة التي ستقوم بحلهاوتستخدم استراتيجية ثابتة للبحث بحيث تفحص كل حالات فضاء البحث واحدة تلو الأخرى
مثال (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
مثال (2): تأمل في الشكل المجاور، ثم أجب عن الأسئلة الآتية:
علما بأن هذا الشكل جزء من شجرة بحث للعبة (0 X) بين لاعبين، ويقوم اللاعبان باللعب بالتناوب:
يقوم اللاعب الأول (الحاسوب) بوضع (X) واللاعب الثاني (المستخدم) بوضع (0)
ما النقطة التي تمثل جذر الشجرة؟
النقطة A
كم عدد حالات فضاء البحث؟ اذكرها.
A,B,C,D,E,F,G,H,l,J,K,N,L,M
(عدد الحالات 14 )
اذكر أمثلة على مسار
A-B-F-K
ما عدد النقاط الميتة
6 نقاط
ما حالة الهدف في هذه الشجرة؟ ولماذا؟
الحالة الهدف هي الحالة التي تمثل الفوز باللعبة. ومن ثم، فإن النقاط (K,N) تمثل فوز الحاسوب والنقاط (H,G) تمثّل حالة الفوز للمستخدم