الدرس 2 من 9
تلخيص درس مقدمة في شجرة البحث
الدرس باختصار
كثير من مسائل الذكاء الاصطناعي تُحلّ بالبحث: ننطلق من حالة أولية ونجرّب إجراءات تنقلنا من حالة إلى أخرى حتى نبلغ الحالة الهدف. نمثّل هذه الحالات والانتقالات بشجرة بحث (Search Tree)، ونسمّي مجموعة الحالات والإجراءات حيّز الحالة (State Space).
مصطلحات الدرس
كل مصطلحات الدرس بصفحة وحدة · راجعها ببطاقات
- شجرة البحث (Search Tree)
- تمثيل هرمي للمشكلة من عُقَد (Nodes) تمثّل الحالات وفروع (Edges) يمثّل كل منها إجراءً ينقل إلى حالة جديدة.
- حيّز الحالة (State Space)
- مجموعة الحالات الممكنة للمشكلة والإجراءات التي تسمح بالانتقال من حالة إلى أخرى.
- الحالة الأولية (Initial State) أو الجذر (Root)
- نقطة انطلاق البحث عن الحل.
- الحالة الهدف (Goal State)
- الحالة المطلوب الوصول إليها، وقد تكون حالة واحدة أو عدّة حالات.
- الإجراءات (Actions) والنموذج الانتقالي (Transition Model)
- الإجراءات هي ما يستطيع الوكيل (Agent) تنفيذه في حالة ما، والنموذج الانتقالي يصف الحالة الناتجة عن تطبيق كل إجراء.
- تكلفة الإجراء (Action Cost)
- قيمة عددية لتطبيق إجراء، كالمسافة أو الزمن أو المال، وتكلفة المسار مجموع تكاليف إجراءاته.
- المسار (Path) والحل (Solution)
- المسار حالات متتالية في الشجرة، والحل مسار من الحالة الأولية إلى الحالة الهدف، والحل الأمثل هو الأقل تكلفة.
- الأب (Parent) والعقدة الميتة
- الأب عقدة يتفرع منها أبناء، والعقدة الميتة عقدة ليس لها أبناء.
أهم الأفكار
مراحل حل المشكلة
نمرّ بأربع مراحل: صياغة الهدف بوضوح، ثم صياغة المشكلة بوصف معطياتها وقيودها، ثم البحث بمحاكاة تسلسلات الإجراءات لاختيار الأفضل، ثم التنفيذ الذي يقوم به الوكيل. وقد يكون الوكيل شخصًا أو برنامجًا أو نظامًا.
عناصر تمثيل المشكلة
لتمثيل مشكلة نحدّد: الحالات، والحالة الأولية، والحالة الهدف، والإجراءات، والنموذج الانتقالي، وتكلفة الإجراء. حيّز الحالة يصف الحالات والإجراءات الممكنة، وشجرة البحث تصف المسارات بينها، ولكل عقدة في الشجرة مسار وحيد يعود إلى الجذر.
آلية البحث
تركّز الخوارزمية على حالة واحدة وتؤجّل بقية الخيارات؛ فإن لم تكن هدفًا وسّعت البحث إلى أبنائها حتى تصل إلى الهدف أو إلى عقدة ميتة. تسمّى العقد المتاحة للتوسع حدود التوسع (Frontier). وقد تظهر مسارات متكررة تصل إلى النقطة نفسها، وقد تجعل المشكلة صعبة.
أنواع المشكلات
المشكلات القياسية (Standardized) تُستعمل لمقارنة أداء الخوارزميات ووصفها موجز ودقيق، مثل روبوت التنظيف ولغز الأرقام الثمانية ولعبة XO، وتُسمّى مشكلات عالم الشبكة. أما المشكلات الواقعية (Real-World) فتتعلق بالحياة العملية وصياغتها فردية، مثل تحديد المسار وتخطيط السفر.
خطوات بناء حيّز الحالة
نبدأ بعقدة الجذر للحالة الأولية، ثم نحدّد كل الانتقالات الممكنة منها ونرسم فروعًا، ونكرر ذلك لكل عقدة حتى الوصول إلى الحالات النهائية، ثم نضع تسمية لكل عقدة. في لعبة XO مثلًا لا يمكن عادة رسم كل الحالات يدويًا لكثرتها، فنرسم عدة مستويات فقط.
أمثلة محلولة
مثال 1: الحل والمسار والتكلفة
في خريطة فيها الطرق: أ إلى ب وج وهـ، ومن ب وج إلى د، ومن هـ إلى و، ومن د وو إلى ز. الحالة الأولية أ والهدف ز، وكل إجراء (انتقال) تكلفته 1. اذكر حلًّا وأوجد تكلفته.
اعرض الحل
- الحل مسار من أ إلى ز، مثلًا: أ - ج - د - ز.
- هذا المسار فيه ثلاثة انتقالات: أ إلى ج، ثم ج إلى د، ثم د إلى ز.
- التكلفة = 1 + 1 + 1 = 3. والمسار أ - هـ - و - ز له التكلفة نفسها.
الجواب: المسار أ - ج - د - ز، وتكلفته 3
اختبر حالك
1. روبوت تنظيف في صف من 3 مربعات، كل مربع إما نظيف أو متّسخ، والروبوت في أحدها. كم حالة ممكنة؟
2. ما اسم العقدة التي ليس لها أبناء في شجرة البحث؟
3. مسار حل فيه 4 إجراءات، تكلفة كل إجراء 1. ما تكلفة الحل؟
4. في لغز الثمانية، المساحة الفارغة في زاوية الشبكة. كم إجراءً ممكنًا؟
باقي الدرس للمسجّلين، ومجاناً
- 4 أمثلة محلولة كمان
- 4 أخطاء شائعة وكيف تتجنّبها
- إجابات «اختبر حالك» مع الشرح
جاهز تتدرّب؟
32 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 32 سؤال من هالدرس مجانًا