المهارات الرقمية، الصف الثاني عشر · الذكاء الاصطناعي

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

أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.

أهم الأفكار

  1. مراحل حل المشكلة نمرّ بأربع مراحل: صياغة الهدف بوضوح، ثم صياغة المشكلة بوصف معطياتها وقيودها، ثم البحث بمحاكاة تسلسلات الإجراءات لاختيار الأفضل، ثم التنفيذ الذي يقوم به الوكيل. وقد يكون الوكيل شخصًا أو برنامجًا أو نظامًا.
  2. عناصر تمثيل المشكلة لتمثيل مشكلة نحدّد: الحالات، والحالة الأولية، والحالة الهدف، والإجراءات، والنموذج الانتقالي، وتكلفة الإجراء. حيّز الحالة يصف الحالات والإجراءات الممكنة، وشجرة البحث تصف المسارات بينها، ولكل عقدة في الشجرة مسار وحيد يعود إلى الجذر.
  3. آلية البحث تركّز الخوارزمية على حالة واحدة وتؤجّل بقية الخيارات؛ فإن لم تكن هدفًا وسّعت البحث إلى أبنائها حتى تصل إلى الهدف أو إلى عقدة ميتة. تسمّى العقد المتاحة للتوسع حدود التوسع (Frontier). وقد تظهر مسارات متكررة تصل إلى النقطة نفسها، وقد تجعل المشكلة صعبة.
  4. أنواع المشكلات المشكلات القياسية (Standardized) تُستعمل لمقارنة أداء الخوارزميات ووصفها موجز ودقيق، مثل روبوت التنظيف ولغز الأرقام الثمانية ولعبة XO، وتُسمّى مشكلات عالم الشبكة. أما المشكلات الواقعية (Real-World) فتتعلق بالحياة العملية وصياغتها فردية، مثل تحديد المسار وتخطيط السفر.
  5. خطوات بناء حيّز الحالة نبدأ بعقدة الجذر للحالة الأولية، ثم نحدّد كل الانتقالات الممكنة منها ونرسم فروعًا، ونكرر ذلك لكل عقدة حتى الوصول إلى الحالات النهائية، ثم نضع تسمية لكل عقدة. في لعبة XO مثلًا لا يمكن عادة رسم كل الحالات يدويًا لكثرتها، فنرسم عدة مستويات فقط.

مصطلحات الدرس

شجرة البحث (Search Tree)
تمثيل هرمي للمشكلة من عُقَد (Nodes) تمثّل الحالات وفروع (Edges) يمثّل كل منها إجراءً ينقل إلى حالة جديدة.
حيّز الحالة (State Space)
مجموعة الحالات الممكنة للمشكلة والإجراءات التي تسمح بالانتقال من حالة إلى أخرى.
الحالة الأولية (Initial State) أو الجذر (Root)
نقطة انطلاق البحث عن الحل.
الحالة الهدف (Goal State)
الحالة المطلوب الوصول إليها، وقد تكون حالة واحدة أو عدّة حالات.
الإجراءات (Actions) والنموذج الانتقالي (Transition Model)
الإجراءات هي ما يستطيع الوكيل (Agent) تنفيذه في حالة ما، والنموذج الانتقالي يصف الحالة الناتجة عن تطبيق كل إجراء.
تكلفة الإجراء (Action Cost)
قيمة عددية لتطبيق إجراء، كالمسافة أو الزمن أو المال، وتكلفة المسار مجموع تكاليف إجراءاته.
المسار (Path) والحل (Solution)
المسار حالات متتالية في الشجرة، والحل مسار من الحالة الأولية إلى الحالة الهدف، والحل الأمثل هو الأقل تكلفة.
الأب (Parent) والعقدة الميتة
الأب عقدة يتفرع منها أبناء، والعقدة الميتة عقدة ليس لها أبناء.

من اُدرُس: odrosai.com/ar/subjects/JO-DIGI-G12/units/4/digi12-u4_l1_search_tree

بدك تتأكد إنك فاهم؟

سجّل مجاناً وحلّ أسئلة على هالدرس، بتتصحّح خطوة خطوة ومعها تلميحات لما تعلق.