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

• أُوضّح شجرة البحث وعناصرها.
• أرسم شجرة بحث لمسألة ما.
• أُمثّل لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩ بوصفها شجرة بحث.
• أُمثّل لعبة ⁦(XO)⁩ بوصفها شجرة بحث.
• أُوضّح مفهوم حيّز الحالة.
• أَبني حيّز الحالة لمسائل مُتعدّدة.
• أُميّز المسائل التي يُمكن بناء حيّز حالة لها.

لماذا نبحث؟ من حلّ المشكلة إلى شجرة البحث

يعمل الذكاء الاصطناعي على حلّ مشكلات مُعيّنة، وتنفيذ مهام مُتقدّمة، مثل: الإدراك (الرؤية والكلام)، وفهم اللغة الطبيعية، والتشخيص الطبي، والتحليلات الكيميائية، وغير ذلك من المهام؛ إذ يتطلّب حلّ المشكلة الوصول إلى حالة مُعيّنة ضمن مجموعة من الإجراءات العملية، في ما يُعرّف بعملية البحث.

أدرس النص الآتي، ثمّ أُجيب عن السؤال الذي يليه:

يعمل سامي في المدينة (ز)، ويسكن في المدينة (أ)، حيث يوجد العديد من الطرق الموصلة بين المنزل ومكان العمل كما يظهر في الشكل (1-1) إذا كنتُ مكان سامي، فهل سألتزم يوميًّا بالطريق نفسه أم سأسلك طرقًا مختلفةً؟ أُناقش إجابتي مع الزملاء/ الزميلات في الصف.

أربع مراحل: من الهدف إلى التنفيذ

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

• صياغة الهدف: يجب تحديد الهدف (أو الأهداف) الذي يُراد تحقيقه بلغة مفهومة، وتنظيمه، وكذا تحديد الإجراءات التي يتعيّن اتّباعها للوصول إلى هذا الهدف.

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

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

من فضاء البحث إلى شجرة من العُقد والفروع

• تُمثّل المشكلة عن طريق مجموعة من الحالات المُحتملة (المُمكِنة) للحلّ، تُسمّى فضاء البحث،
• يُطلق على التمثيل المُنتظم للحالات والعلاقات بينها اسم حيّز الحالة ⁦(State Space)⁩.

• تجدر الإشارة إلى أنَّ هذا النموذج يُستخدم في الذكاء الاصطناعي وتحليل الخوارزميات.

العناصر التي تصف أي مشكلة بحث

تتطلّب صياغة المشكلة وتمثيلها تمثيلًا دقيقًا تحديد العناصر الآتية:

• الحالات ⁦(States)⁩: تُسمّى الحالات أيضًا النقاط أو العُقد ⁦(Nodes)⁩؛ وهي مجموعة النقاط التي تُنظّم بشكل هرمي، وتُمثّل كل نقطة منها حالة من حالات فضاء البحث
• كما في الشكل (1-1) الذي يتضمّن الحالات الآتية: (أ، ب، ج، د، هـ، و، ز).

• تُمثلها المدينة (أ) في الشكل (1-1).

• تُمثلها المدينة (ز) في الشكل (1-1).
• الإجراءات ⁦(Actions)⁩: مجموعة من الإجراءات التي تقبل التطبيق، ويستطيع العميل تنفيذها للوصول إلى الحل
• يُمثلها الانتقال من المدينة (ب) إلى المدينة (د) في الشكل (1-1).

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

• ففي الشكل (1-1) مثلًا، المسار بين المدينة (ج) والمدينة (ز) هو: المدينة (ج) - المدينة (د) - المدينة (ز).

• ففي الشكل (1-1) مثلًا، الحلّ هو المسار الآتي: المدينة (أ) - المدينة (ج) - المدينة (د) - المدينة (ز).

• الأب ⁦(Parent)⁩: عُقدة يتفرّع منها عُقد أخرى تُسمّى الأبناء.
• ففي الشكل (1-1) مثلًا، يُطلق على العُقدة (أ) اسم الأب، ويُطلق على العُقد (هـ، ج، ب) اسم الأبناء،
• في حين يُطلق على العُقدة (ز) اسم العُقدة الميتة؛ نظرًا إلى عدم وجود أبناء لها.

أدرس الشكل المجاور، ثمّ أُجيب عن الأسئلة الآتية:

أُحدّد الحالة الأوّلية التي يُمثّلها هذا الشكل.

أُعدّد العُقد الظاهرة في الشكل.

أذكر من الشكل مثالين على كل من المسار، والأب، والعُقد الميتة.

كيف تبحث الخوارزمية؟ عُقدة بعد عُقدة

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

• تستمر هذه العملية إلى حين الوصول إلى الحلّ (الحالة الهدف)، أو انتهاء الفحص في الحالات جميعها.
• أنظر الشكل (2-1) الذي يُبيّن كيف يُمكن التوسّع في البحث من عُقدة إلى أخرى.

مشكلات قياسية ومشكلات واقعية

يوجد نوعان من المشكلات التي تحتاج إلى حلّ، هما:

• يوجد العديد من الأمثلة على المشكلات القياسية، وهذه أبرزها: روبوت التنظيف، ولعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩، ولعبة الشطرنج، ولعبة ⁦(XO)⁩.

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

روبوت التنظيف: كم حالة ممكنة؟

• يُمكن صياغة هذه المشكلة بطريقة عالم الشبكة كما في الشكل (3-1).

• عدد الحالات المُحتملة (المُمكِنة) لروبوت التنظيف هو (8) حالات، حيث إنَّ عدد المُربّعات في كل حالة اثنان، وكل مُربّع إما أن يحتوي على أوساخ، وإما أن يكون نظيفًا؛ ما يعني وجود حالتين مُمكنتين.
• كذلك يُمكن للروبوت (العميل) أن يوجد في أيّ من المُربّعين، في دلالة على وجود حالتين مُمكنتين أيضًا.

2 (وجود الأوساخ في المُربّع الأوّل، أو عدم وجودها فيه) × 2 (وجود الأوساخ في المُربّع الثاني، أو عدم وجودها فيه) × 2 (موقع الروبوت في أحد المُربّعين) = 8 حالات.

• الحالة الأوّلية (الابتدائية): يُمكن عدّ أيّ حالة من الحالات الظاهرة في الشكل حالة ابتدائية.
• الإجراءات: في عالم الشبكة الظاهرة في الشكل، حُدّدت ثلاثة إجراءات أساسية، هي: إزالة الأوساخ، والتحرّك إلى اليسار، والتحرّك إلى اليمين.
• وقد يضاف إلى هذه الإجراءات الثلاثة - في أمثلة أخرى - التحرّك إلى الأعلى، والتحرّك إلى الأسفل.

• الحالة الهدف: الحالة الهدف في هذه المشكلة هي أن تكون جميع المُربّعات نظيفة.
• تكلفة الإجراء: تُحسب التكلفة بعدد الإجراءات، وكل إجراء يُكلّف وحدة واحدة.

أحدّد - بالتعاون مع أفراد مجموعتي - مسارين للحلّ في الشكل (3-1)، ثمّ نَحسُب تكلفتهما.

بعد ذلك نُقارن النتائج التي نتوصّل إليها في المجموعة بالنتائج التي توصّل إليه الزملاء/ الزميلات في المجموعات الأخرى، ثمّ نُناقش معًا سبب الاختلاف (إن وُجد)، ونتبادل معًا التغذية الراجعة.

لغز الأرقام الثمانية على شكل شجرة بحث

• تُمثّل هذه اللعبة عن طريق شبكة أبعادها ⁦(3×3)⁩، وهي تحتوي على (8) مُربّعات مُرقّمة من (1) إلى (8)، إضافةً إلى مساحة فارغة واحدة.
• أمّا هدف اللعبة فهو الوصول إلى ترتيب متتالٍ للأرقام على المُربّعات،
• وذلك باستخدام المساحة الفارغة في تحريك المُربّعات إلى اليمين، أو إلى اليسار، أو إلى الأعلى، أو إلى الأسفل كما هو مُبيّن في الشكل (4-1).

• العُقد ⁦(Nodes)⁩: هي المُربّعات المُرقّمة.
• الحالات ⁦(States)⁩: الحالة في هذه اللعبة هي وصف لموقع كل مُربّع من المُربّعات ضمن الشبكة.
• الحالة الأوّلية ⁦(Initial State)⁩: يُمكن تحديد أيّ توزيع للمُربّعات بوصفه حالة ابتدائية.
• الإجراءات ⁦(Actions)⁩: تتمثّل الإجراءات في تحريك المُربّع الفارغ إلى اليمين، أو إلى اليسار، أو إلى الأعلى، أو إلى الأسفل، ومراعاة أنَّ بعض الإجراءات قد تكون غير قابلة للتطبيق إذا كانت المساحة الفارغة موجودة على إحدى الحافات أو الزوايا.

مشكلات واقعية: من خرائط الطرق إلى الطيران

• تطبيقات تحديد المسار، مثل مشكلة الانتقال من مدينة إلى أخرى التي ورد ذكرها في بداية الدرس.
• الشبكة العنكبوتية (مواقع الويب)، وهي تُعدّ مثالًا جيّدًا على المشكلات الواقعية.
• أنظمة السيارات التي تُوفّر اتّجاهات عديدة للقيادة، وتُقدّم طرقًا بديلةً في حال وجود عوائق أو ازدحام مروري،
• ومن ثمّ تتفاوت تكلفة الانتقال تبعًا للتأخيرات الناجمة عن حركة المرور.
• أنظمة تخطيط السفر الجوي.

اعتمادًا على شجرة البحث الخاصة بالانتقال من مطار الملكة علياء الدولي ⁦(AMM)⁩ إلى مدينة هيوستن، أُجيب - بالتعاون مع أفراد مجموعتي - عن الأسئلة الآتية:

أُحدّد جذر الشجرة.

أُعدّد حالات فضاء البحث.

أذكر مسارين يُمكن اتّخاذهما للوصول إلى الوجهة المنشودة.

ما الحالة الهدف في هذه الشجرة؟

ما تكلفة الانتقال من مدينة عمّان إلى مدينة هيوستن بالوقت، مرورًا بمطار شيكاغو؟

هل يُمكن اعتماد تكلفة انتقال أخرى؟ هل سيكون فضاء البحث مختلفًا في حال اعتمادها؟

ما نموذج الانتقال الخاص بالرحلة من مدينة عمّان إلى مدينة مونتريال؟

أُناقش إجابات الأسئلة مع زملائي/ زميلاتي في المجموعة، ثمّ أعرضها أمام أفراد المجموعات الأخرى بهدف التوصّل إلى استنتاجات مُشتركة، ونتبادل معًا التغذية الراجعة.

كيف نبني حيّز الحالة ونرسم الشجرة؟

والآن سأتعرّف الخطوات اللازمة لبناء حيّز الحالة عند رسم شجرة بحث:

• الخطوة 1: البدء برسم عُقدة الجذر التي تُمثّل الحالة الأوّلية (الابتدائية).
• الخطوة 2: تحديد جميع التحرّكات أو الانتقالات المُحتملة (المُمكِنة) من هذه الحالة، ورسم فروع منها.
• الخطوة 3: تكرار العملية لكل عُقدة حتى الوصول إلى الحالات النهائية.
• الخطوة 4: إضافة تسمية إلى كل عُقدة لتوضيح الحالة.

• الخطوة 1: رسم الجذر، وهو في هذه اللعبة لوحة فارغة كما في الشكل (7-1).

• الخطوة 2: تحديد جميع الحالات المُحتملة (المُمكِنة) للاعب ⁦(X)⁩ على أساس أنَّه مَن سيبدأ اللعب كما في الشكل (8-1).

• بهذه الطريقة، أكون قد حَدّدْتُ المستوى الثاني من شجرة البحث.
• الخطوة 3: تحديد جميع الحالات المُحتملة (المُمكِنة) للاعب ⁦(O)⁩ بناءً على تحرّكات اللاعب ⁦(X)⁩ في المستوى الثاني كما في الشكل (9-1).

• الخطوة 4: رسم المستوى الرابع من شجرة البحث، وتحديد جميع الحالات المُحتملة (المُمكِنة) للاعب ⁦(X)⁩ كما في الشكل (10-1).

• تكرار العمليات السابقة وصولًا إلى الحالات التي يفوز فيها أحد اللاعبين.

اعتمادًا على المثال السابق، أرسم الحالات الكاملة لإنهاء حيّز العمل الخاص بلعبة ⁦(X-O)⁩، هل يُمكن فعل ذلك؟ أُبرّر إجابتي.

أقرأ الوصف الآتي للعبة ⁦(Sokoban Puzzle)⁩، ثمّ أرسم الحلول المُحتملة (المُمكِنة) على شكل شجرة بحث، ثمّ أُناقش ما أتوصّل إليه من حلول مع الزملاء/ الزميلات في الصف:

في أحجية ⁦(Sokoban Puzzle)⁩ المُمثّلة في الشكل (11-1)، يجب على اللاعب دفع عدد من الصناديق المنتشرة في الشبكة إلى مواقع تخزين مُحدّدة، بحيث تُعبّر الحالة عن تغيير مكان صندوق واحد. عند تحريك الصندوق إلى الأمام، فإنَّ اللاعب والصندوق يتحرّكان نحو الأمام في حال وجود مساحة فارغة على الجانب الآخر من الصندوق، علمًا بأنَّه لا يُسمح للاعب أن يدفع صندوقًا آخر أو إلى الجدار".

نشاط: رحلات عمّان إلى جاكرتا بشجرة بحث

أُناقش أفراد مجموعتي في الأسئلة الآتية:

ما المسائل التي يُمكن بناء حيّز حالة لها؟

ما المسائل التي لا يُمكن بناء حيّز حالة لها؟

أُبرّر إجابتي في كلتا الحالتين.

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

مواطنة رقمية: التفكير الحاسوبي والنزاهة

أقيّم تعلّمي: معرفة ومهارات

أستخدم ما تعلّمته من معارف في هذا الدرس للإجابة عن السؤالين الآتيين:

السؤال الأوّل: أُوضّح المقصود بكلّ ممّا يأتي:

حيّز الحالة.

النموذج الانتقالي.

السؤال الثاني: يُمثّل الشكل المجاور لعبة (لغز) البلاط المُتحرّك أو القطع المُتحرّكة، ويظهر في الشكل (15) قطعة مُرقّمة بالأعداد من (1) إلى (15)، إضافةً إلى بلاطة (قطعة) واحدة فارغة.

تهدف هذه اللعبة إلى ترتيب الأرقام من (1) إلى (15) على نحو متتالٍ.

أُحدّد كُلًّا ممّا يأتي:

الحالات.

الحالة الأوّلية (الابتدائية).

الإجراءات.

نموذج الانتقال.

الحالة الهدف.

تكلفة الإجراءات.

أُوظّف مهارات التفكير الناقد والبحث الرقمي والتواصل في الإجابة عن الأسئلة الآتية:

السؤال الأوّل: أكتب تعريفًا للعميل ⁦(Agent)⁩ الذي يؤدّي دورًا رئيسًا في عمليات الذكاء الاصطناعي.

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

السؤال الثالث: أبحث عن مشكلات لا يُمكن بناء حيّز حالة لها، ثمّ أُبرّر إجابتي.

السؤال الرابع: أرسم حيّز حالة لبرج هانوي ⁦(Tower of Hanoi)⁩، علمًا بأنَّه يجب نقل الأقراص الثلاثة من العمود الأوّل إلى العمود الثالث (عمود واحد في كل مرّة)، ولا يُمكن وضع القرص الأكبر فوق القرص الأصغر.