تلخيص مقدمة في شجرة البحث

العناوين الرئيسة في هذا الدرس:

• مفهوم شجرة البحث ومُُكوِِّناتها
•  كيف تُمثل بعض الألعاب باستخدام شجرة البحث.
• مفهوم حيِّز الحالة ( State Space )
•  بناء حيِّز الحالة لمجموعة من المسائل المختلفة
• تمييز المسائل التي يُمكِن بناء حيِّز حالة لها من تلك التي لا يُمكِن بناء حيِّز حالة لها

ما هي  المشكلة (المسألة) ؟

 هي الهدف أو الناتج الذي يُراد الوصول إليه عن طريق تنفيذ مجموعة من الخطوات أو الإجراءات بناءً على معطيات مُحدََّدة.

مراحل  حل المشكلة :

تشتمل هذه الإجراءات على أربع خطوات رئيسة، هي:

1. صياغة الهدف: يجب تحديد الهدف أو الأهداف الذي يُراد تحقيقه بلغة مفهومة، وتنظيمه، وكذا تحديد الإجراءات التي يتعينَّ اتِّباعها للوصول إلى هذا الهدف. بالعودة إلى النشاط التمهيدي السابق، فإنَّ الهدف المنشود 

2. صياغة المشكلة: ينبغي تقديم وصف واضح للمشكلة التي يُراد حَ هُّلا، والتحدِّيات أو القيود المُتعلقِّة بالحَلِّ إنْ وُجِدت ذات الصلة بالمصادر المتاحة، أو نوعيتها، أو جودتها؛ بُغْيَةَ الوصول إلى الهدف المنشود.

3. البحث: يجب محاكاة جملة التسلسلات والإجراءات المُتوافِرة في المسألة للوصول إلى التسلسل الأفضل الذي يُحقِّق الهدف المنشود. غير أنَّه يُمكِن - في بعض الحالات- محاكاة تسلسلات عديدة لا توصِل إلى الهدف المطلوب؛ ما يُحتمِّ الاستمرار في عميلة المحاكاة لحين الوصول إلى التسلسل الصحيح.

4. التنفيذ: يتولّى الوكيل ( Agent )، الذي يُطلَق عيله أحيانًا اسم العميل، تنفيذ إجراءات الحَلِّ البحث خطوة خطوة. بالعودة إلى النشاط التمهيدي السابق، فإنَّ الوكيل هو  سامي، لكنَّ ذلك ليس مقياسًا يُعْتَدُّ به؛ فقد يكون الوكيل في مسائل أُخرى هو البرنامج أو النظام. تُمثل المشكلة عن طريق مجموعة من الحالات المُُحتملة الممكنة للحَل، تُسمّى فضاء البحث، في حين يُطلَق على التمثيل المُنظم للحالات والعلاقات بينها اسم حيِّز الحالة(State Space)

تُمثل المشكلة بشكل هرمي من عُقَد ( Nodes )  وفروع ( Edges ) تُمسى شجرة البحث (Search Tree). وبينما تُمثل كل عُقْدة في الشجرة حالةً مُعيَّنةً من المشكلة، فإنَّ كل فرع في الشجرة يُمثِّل إجراءً يؤدّي إلى حالة جديدة. تجدر الإشارة إلى أن  هذا النموذج يُستخدَم في الذكاء الاصطناعي وتحليل الخوارزميات.

تتطلبَ صياغة المشكلة وتمثيلها تمثيلا دقيقًًا لتحديد العناصر الآتية:
1. الحالات (States ): تُسمّى الحالات أيضًا النقاط أو العُقَد ( Nodes )؛ وهي مجموعة النقاط التي تُنظمَّ بشكل هرمي، وتُمثِّل كل نقطة منها حالة من حالات فضاء البحث 

2. الحالة الأوَّلية (Initial State) أوالجذر(Roots): حالة ابتدائية للمشكلة؛أي نقطة الانطلاق للبحث عن الحَلِّ

3. الحالة الهدف(Goal State ): حالة مرغوب الوصول إليها، وقد تكون حالة واحدة، أو مجموعة من الحالات

4.  ( Actions ): مجموعة من الإجراءات التي تَقْبل التطبيق، ويستطيع العميل تنفيذها للوصول إلى الحَلِّ

5. النموذج الانتقالي ( Transition Model ): نموذج يُقدِّم وصفًا لِما يتضمَّنه كل إجراء في حالة مُعينَّة.

 

6. تكلفة الإجراء ( Action Cost Function ): تشير تكلفة الإجراء إلى التكلفة العددية لتطبيق إجراء مُعين. على سبيل المثال، عند الانتقال من مدينة إلى أُخرى، قد تُحسَب التكلفة بالمسافة المقطوعة، أو الوقت المُستغرَق للوصول إلى المدينة المقصودة، أو بالتكلفة المادية للانتقال بين المدينتين، علمًا بأنَّ التكلفة الإجمالية هي مجموع تكلفة الإجراءات مُنفرِدة.

7. المسار( Path ): مجموعة النقاط أو الحالات المتتالية في الشجرة.

8. الحَلُّ ( Solution ): مسار من النقطة الأوَّلية(الابتدائية) إلى النقطة (الهدف) .

9. الحَلُّ الأمثل ( Optimal Solution ): حَلٌّ ذو مسار أقل تكلفة بين مسارات الحلول المُحتمَلة المُمكِنة جميعها.

10. الأب (Parent ): عُقْدة يتفرَّع منها عُقَد أُخرى تُسمّى الأبناء. 

 

خوارزميات البحث:
تتمثَّل آليَّة عمل خوارزميات البحث في التركيز على خيار واحد، ووضع الخيارات الأُخرى جانبًا؛أي النظر إلى حالة واحدة فقط، فإذا تبيََّن أن هذه الحالة ليست الحالة الهدف، فيتمُُّ التوسُّع في نطاق البحث، ليشمل البحث في إحدى عُقد الأبناء إلى حين الوصول إلى عُقْدة ميتة العُقْدة التي ليسلها أبناء يُطلَق على مجموعة العُُقََد المتاحة للتوسُّع في نقطة مُعينة اسم حدود التوسُّع لتلك العُقدة (Frontier)، وقد تُسمّى أحيانًا القائمة المفتوحة(Open List) .

تستمر هذه العميلة إلى حين الوصول إلى الحل الحالة الهدف، أو انتهاء الفحص في الحالات جميعها.

 

•  شجرة البحث ومكوناتها (Search Tree)

شجرة البحث هي تمثيل بياني لحيز الحالة، وتتكون من العناصر الأساسية التالية:

• الجذر (Root Node): يمثل الحالة الابتدائية للمسألة (نقطة الانطلاق).

• العقد (Nodes): تمثل كل عقدة حالة معينة من حالات المسألة.

• الوصلات (Edges/Branches): تمثل الأفعال أو الانتقالات بين الحالات.

• العقدة الأب (Parent) والعقدة الابن (Child): تسمى العقدة الناتجة عن فعل معين "ابناً" للعقدة التي سبقتها.

• العقد الطرفية (Leaf Nodes): هي العقد التي لا يتفرع منها أي عقد أخرى، وقد تكون هي "حالة الهدف" (Goal State). 

 

في بعض الأحيان، قد تواجه شجرة البحث مسارات مُتكررة ( Redundant Paths )؛ ما يعني إمكانية الوصول إلى النقطة نفسها عن طريق مسارات كثيرة. وهذا الإجراء قد يُحول المشكلة التي تقْبل الحَلَ إلى مشكلة مُستعصية.

يوجد نوعان من المشكلات التي تحتاج إلى حَلّ هما:
1. المشكلات القياسية : مشكلات يستخدمها الباحثون في المقارنة بين أداء الخوارزميات، ويُمكِن وصفها بشكل موجز ودقيق.
2. المشكلات الواقعية: مشكلات تتعلقّ بالحياة العميلة، ويُمكِن صياغتها صياغة فردية، وهي ليست مُوحَّدة.

• أمثلة على المشكلات القياسية:

1.تمثيل لعبة لغز الأرقام الثمانية (8-Puzzle) كشجرة بحث

• الحالة الابتدائية: لوحة مبعثرة للأرقام من 1 إلى 8 مع مربع فارغ.

• الأفعال: تحريك المربع الفارغ (أعلى، أسفل، يمين، يسار).

• شجرة البحث: يتم تفريع الشجرة بناءً على الحركات الممكنة للمربع الفارغ في كل خطوة، حيث تمثل كل عقدة شكلاً جديداً للوحة حتى نصل إلى الحالة المرتبة (الهدف).

 

 2. تمثيل لعبة (XO) كشجرة بحث

• الجذر: لوحة فارغة تماماً (3×3).

• المستويات:

1. المستوى الأول يمثل كافة الأماكن الممكنة التي يمكن للاعب الأول (X) أن يضع علامته فيها (9 احتمالات).
2. المستوى الثاني يمثل ردود فعل اللاعب الثاني (O) على كل حركة لـ X.

 تنتهي فروع الشجرة عند حالات الفوز، الخسارة، أو التعادل (امتلاء اللوحة).

 

الخلاصة :

شجرة البحث هي الأداة التي يستخدمها الذكاء الاصطناعي "للتفكير" في العواقب المستقبلية لكل حركة قبل اتخاذها، وحيز الحالة هو "الخريطة الكاملة" التي تتحرك ضمنها هذه الشجرة للوصول إلى الحل الأمثل.