استراتيجيات البحث في الذكاء الاصطناعي

من حيّز الحالة إلى البحث عن الحلّ

سأتعرّف في هذا الدرس بعض طرائق البحث العمياء، وكيفية تطبيقها على مسائل مُحدَّدة. كذلك سأتعرّف بعض أساليب البحث الاجتهادية، وأُطبِّق خوارزمية ⁦A⁩* على لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩ باستخدام الاقترانات (الدوال) التقييمية، ثمَّ أُقارِن بين نتائج هذه الطرائق المختلفة.

• أُوضّح بعض طرائق البحث العمياء.
• أُطبّق بعض طرائق البحث العمياء على لعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩، ثمّ أُقارن بينها.
• أُبيّن طرائق البحث الاستدلالية.

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

والآن: كيف نبحث في حيّز الحالة عن الحالة الهدف؟

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

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

أرسم حيّز الحالة لهذه المسألة، علمًا بأنَّ كل حالة يجب أن تحتوي على ضفة يسرى وضفة يمنى وموضع زياد والذئب والماعز وكيس الذُرّة.

أُحدّد الحركات المُحتملة (المُمكِنة) كما يأتي:

انتقال زياد من ضفة النهر إلى الضفة الأخرى وحده.

الحالة الأوّلية (الابتدائية): زياد والذئب والماعز وكيس الذُرّة على الضفة اليسرى.

الحالة النهائية: زياد والذئب والماعز وكيس الذُرّة على الضفة اليمنى.

البحث الأعمى: نجرّب الاحتمالات بنظام

فما أشهر هذه الطرائق؟

• من الأمثلة على هذا النوع من الاستراتيجيات:
• البحث في العمق أوّلًا ⁦(Depth-First Search)⁩.
• البحث في العرض أوّلًا ⁦(Breadth-First Search)⁩.
• البحث العشوائي ⁦(Random Search)⁩.
• البحث ذو التكلفة المُوحّدة ⁦(Uniform Cost Search)⁩.

العمق أوّلًا: ننزل في الفرع حتى نهايته

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

• لتوضيح آليّة عمل خوارزمية البحث في العمق أوّلًا، أنظر الشكل (2-1) الذي يُبيّن الحالات المُحتملة (المُمكِنة) للعبة (لغز) الأرقام الثمانية ⁦(8-Puzzle)⁩:

• تُسمّى الحالة الابتدائية ⁦(A)⁩، وهي نقطة البداية.
• من الحالة الابتدائية ⁦(A)⁩، انبثقت ثلاث حالات، هي:
• الحالة ⁦(B)⁩ التي نتجت من تحريك المُربّع الذي يحمل الرقم (1) إلى الأسفل.
• الحالة ⁦(C)⁩ التي نتجت من تحريك المُربّع الذي يحمل الرقم (4) إلى اليسار.
• الحالة ⁦(D)⁩ التي نتجت من تحريك المُربّع الذي يحمل الرقم (7) إلى الأعلى.

• في المستوى الرابع، يوجد أبناء للعُقدة ⁦(E)⁩، تُمثلهم حالتان، هما:
• الحالة ⁦(H)⁩ التي نتجت من تحريك الرقم (7) إلى اليمين.
• الحالة ⁦(I)⁩ التي نتجت من تحريك الرقم (8) إلى اليسار.

مثال: نبحث عن الحالة ⁦(I)⁩ بالعمق أوّلًا

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

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

العرض أوّلًا: نفحص المستوى كلّه ثمّ ننزل

• استنادًا إلى الشكل (2-1)، يُمكن تطبيق خوارزمية البحث في العرض أوّلًا على النحو الآتي:
• بدء الخوارزمية العمل من الحالة الابتدائية ⁦(A)⁩، ثمّ مقارنة هذه الحالة بالحالة الهدف.

• في حال لم يوجد الحلّ في المستوى الثاني، فإنَّ الخوارزمية تنتقل إلى العمل في المستوى الثالث من شجرة البحث،
• تُستكشف فيه جميع العُقد مُرتّبةً من اليسار إلى اليمين، بدءًا بالعُقدة ⁦(E)⁩، ومرورًا بالعُقدة ⁦(F)⁩، وانتهاءً بالعُقدة ⁦(G)⁩،
• فيتبيّن أنَّ جميع هذه العُقد لا تُمثّل الحالة الهدف.

بالعودة إلى الشكل (3-2)، أُحدّد - بالتعاون مع أفراد مجموعتي - مسار البحث باستخدام خوارزمية البحث في العرض أوّلًا لإيجاد الحلّ المثالي لهذه اللعبة.

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

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

أجد مسار البحث عن النقطة الهدف باستخدام خوارزمية البحث في العمق أوّلًا.

أجد مسار البحث عن النقطة الهدف باستخدام خوارزمية البحث في العرض أوّلًا.

أحسب تكلفة المسارين، ثمّ أُحدّد أيّ المسارين أقصر وأقل تكلفة.

هل يُمكن للحالة الابتدائية أن تكون غير العُقدة ⁦(A)⁩؟ أُبرّر إجابتي.

إذا رسمتُ شجرة البحث من اليمين إلى اليسار، فهل ستختلف مسارات الحلّ عن الحالة الهدف؟ أُبرّر إجابتي.

أرسم شجرة البحث للمسألة الآتية:

"روبوت مُتحرّك يوجد في موقع البداية ⁦(A)⁩، وهو يتحرّك في مواقع مختلفة وفقًا للقواعد الآتية:

من الموقع ⁦(A)⁩ يُمكنه الذهاب إلى الموقع ⁦(B)⁩ أو الموقع ⁦(C)⁩.

من الموقع ⁦(B)⁩ يُمكنه الذهاب إلى الموقع ⁦(D)⁩ أو الموقع ⁦(E)⁩.

من الموقع ⁦(C)⁩ يُمكنه الذهاب إلى الموقع ⁦(F)⁩.

من الموقع ⁦(E)⁩ يُمكنه الذهاب إلى الموقع (⁦G) (⁩الحالة الهدف).

من الموقع ⁦(F)⁩ يُمكنه الذهاب إلى الموقع (⁦G) (⁩الحالة الهدف).

البحث المستنير: نبحث بمعرفة عن المسألة

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

يُستخدم في معظم هذه الخوارزميات دالّةً يُرمز إليها بالرمز ⁦(n)⁩ : ⁦h(n)⁩

⁦h(n)⁩: التكلفة المُقدّرة لأرخص مسار من الحالة ⁦(n)⁩ إلى الحالة المُستهدفة.

h(n) = 0.

• استخدامات خوارزميات البحث المستنير (الاستدلالي):
• الذكاء الاصطناعي: في الروبوتات والألعاب.
• تحليل البيانات: عند الحاجة إلى تحليل البيانات لاستخراج الأنماط.
• الرسوم البيانية ⁦(Graphs)⁩: البحث فيها.

البحث الجشع: أقرب خطوة الآن

• يوجد العديد من خوارزميات البحث بالأفضلية، ولكلّ منها مزايا وعيوب، وهذه أبرزها:

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

هل تُفضي خوارزمية البحث الجشع إلى المسار الأفضل دائمًا؟

الشبكة العصبية: نتعلّم دالّة التقدير

• يمتاز هذا النوع من خوارزميات البحث بالقدرة على حلّ مشكلات مُعقدة بدقة عالية
• تتحسّن فعاليتها بمرور الوقت في ظلّ زيادة التدريب والبيانات.
• تُستخدم خوارزمية البحث بالشبكة العصبية في ألعاب الذكاء الاصطناعي، وأنظمة التوصية، والتحليل التنبؤي.

مستعمرات النمل: نتّبع أثر الفيرمونات

• يُستخدم هذا النوع من خوارزميات البحث عند الحاجة إلى إيجاد مسارات قصيرة ومُتعددة كما في شبكات النقل والمواصلات.

البحث الشامل: نجمع التقدير مع التكلفة الفعلية

• تُعدّ هذه الخوارزمية واحدة من أكثر الخوارزميات استخدامًا وكفاءةً في إيجاد الحلول المُثلى.
• يُستخدم هذا النوع من خوارزميات البحث في أنظمة الملاحة ⁦(GPS)⁩، وألعاب حلّ الألغاز، وأنظمة الجدولة (مثل جدولة المواعيد الطبية)، وإدارة الرحلات الجوية، والبحث في البيانات الضخمة.

البحث التكراري: ذاكرة أقل من البحث الشامل

أستعين بالمواقع الإلكترونية الموثوقة في شبكة الإنترنت للمقارنة بين خوارزمية البحث الشامل بالأفضلية (⁦A⁩ ⁦Search⁩) وخوارزمية البحث التكراري بالأفضلية (⁦Iterative Deepening A⁩: ⁦IDA⁩*) من حيث آليّة العمل، والتكلفة، والاستخدامات، ثمّ أشارك النتائج التي أتوصل إليها مع الزملاء/ الزميلات في الصف.

أقيّم تعلّمي: أطبّق الطرائق على الأشجار

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

السؤال الأوّل: يُمثّل الشكل التالي شجرة البحث للعبة ⁦(X-O)⁩. أجد مسار الحلّ باستخدام خوارزمية البحث في العرض أولًا، علمًا بأنّ فوز أحد اللاعبين يعني انتهاء اللعبة.

السؤال الثاني: أحدّد الحالات التي تُستخدم فيها خوارزميات البحث المستنير (الاستدلالي).

السؤال الثالث: أدرس الحالات الآتية، ثمّ أحدّد طريقة البحث الفضلى للوصول إلى الحلّ:

"روبوت يحاول الخروج من متاهة بسيطة، والمسارات كلها متساوية في الطول، والهدف قريب من نقطة البداية".

"لعبة تتطلّب الوصول إلى نتيجة مُعيّنة، لكنّها بحاجة إلى خطوات كثيرة جدًا، والمسارات الطويلة كثيرة".

"لاعب يبحث عن أقصر مسار لحلّ لغز يتطلّب التحرك بين حالات عديدة بتكاليف مختلفة (بعض التحركات أصعب من غيرها)".

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

السؤال الأوّل: يقال: "إنّ الخوارزميات التي تنسى تاريخها محكوم عليها بتكرار هذا التاريخ". أُوضّح المقصود بهذا القول، ثمّ أُبيّن كيف يُمكن تجنّب ذلك.

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

السؤال الثالث: أرسم شجرة البحث في الشكل الآتي، علمًا بأنّ النقطة الهدف هي ⁦(Z)⁩، ومسار البحث عن هذه النقطة باستخدام خوارزمية البحث في العرض أولًا هو: ⁦A → B → C → X → Y → K → W → Z⁩