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

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

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

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

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

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

يحلّ الذكاء الاصطناعي كثيراً من المشكلات عبر عملية بحث للوصول من حالة أولية إلى حالة هدف ضمن إجراءات ممكنة. وتُمثَّل هذه العملية بـشجرة البحث (Search Tree): عقدة جذر هي الحالة الأولية (Initial State)، وتتفرّع منها عقد جديدة عبر الإجراءات (Actions) وفق النموذج الانتقالي (Transition Model)، حتى بلوغ الحالة الهدف (Goal State).

شجرة البحث: تمثيل شجري للحالات، جذره الحالة الأولية، وتتفرّع منه الحالات الناتجة عن الإجراءات حتى الهدف.

عناصر الشجرة: الوكيل (Agent)، والحالات (States)، والجذر/الحالة الأولية، والحالة الهدف، والإجراءات، وتكلفة الإجراء (Action Cost)، والمسار (Path) من الجذر إلى الهدف، والحل (Solution) وهو المسار الذي يحقّق الهدف، وحدّ التوسّع (Frontier) أي الحالات المرشّحة للتوسيع.

1. حيّز الحالة (State Space) هو مجموعة كل الحالات الممكنة للمسألة والانتقالات بينها. لا يمكن بناء حيّز حالة إلا للمسائل محدّدة المعالم: حالات وإجراءات وهدف معرّفة بدقّة.
2. أما المسائل الغامضة التي تفتقر إلى تعريف واضح للحالات والإجراءات فلا يمكن بناء حيّز حالة لها.
3. يعرّف هذا الدرس شجرة البحث (Search Tree) بوصفها تمثيلاً لمسار حلّ مسألة في الذكاء الاصطناعي، ويستعرض عناصرها (الوكيل، الحالة الأولية، الحالة الهدف، الإج

ليست كل مسألة قابلة للتمثيل: لا يُبنى حيّز حالة إلا لمسألة واضحة الحالات والإجراءات والهدف؛ المسائل الغامضة غير القابلة للتعريف الدقيق لا حيّز حالة لها.

1. تُمثَّل الألعاب بشجرة بحث: في لغز الأرقام الثمانية (8-Puzzle) كل ترتيب للمربّعات حالة، وتحريك المربّع الفارغ إجراء، والهدف هو الترتيب النهائي.
2. وفي لعبة XO كل وضع للوحة حالة، ووضع علامة في خانة فارغة إجراء، والهدف صفّ ثلاث علامات متتالية.
3. يعرّف هذا الدرس شجرة البحث (Search Tree) بوصفها تمثيلاً لمسار حلّ مسألة في الذكاء الاصطناعي، ويستعرض عناصرها (الوكيل، الحالة الأولية، الحالة الهدف، الإجراءات، النموذج الانتقال

8-Puzzle كشجرة: الحالة الأولية = الترتيب المبعثر؛ كل تحريك للفراغ يولّد حالة ابنة؛ المسار من الجذر إلى ترتيب الهدف هو الحل.