مراحل حلّ المشكلة
- صياغة الهدف: يجب تحديد الهدف (أو الأهداف) الذي يُراد تحقيقه بلغة مفهومة، وتنظيمه، وكذا تحديد الإجراءات التي يتعيّن اتّباعها للوصول إلى هذا الهدف. بالعودة إلى النشاط التمهيدي السابق، فإنَّ الهدف المنشود هو الوصول إلى المدينة (ز) انطلاقًا من المدينة (أ).
- صياغة المشكلة: ينبغي تقديم وصف واضح للمشكلة التي يُراد حلّها، والتحدّيات أو القيود المُتعلّقة بالحلّ (إن وُجدت) ذات الصلة بالمصادر المتاحة، أو نوعيتها، أو جودتها؛ بغيّة الوصول إلى الهدف المنشود. ففي النشاط التمهيدي المذكور آنفًا، تتمثّل صياغة المشكلة في "البحث عن أسرع طريق للانتقال من المدينة (أ) إلى المدينة (ز)".
- البحث: يجب محاكاة جملة التسلسلات والإجراءات المُتوافرة في المسألة للوصول إلى التسلسل الأفضل الذي يحقّق الهدف المنشود. غير أنَّه يُمكن - في بعض الحالات - محاكاة تسلسلات عديدة لا توصل إلى الهدف المطلوب؛ ما يُحتّم الاستمرار في عملية المحاكاة لحين الوصول إلى التسلسل الصحيح.
- التنفيذ: يتولّى الوكيل (Agent)، الذي يُطلق عليه أحيانًا اسم العميل، تنفيذ إجراءات الحلّ (البحث) خطوة خطوة. بالعودة إلى النشاط التمهيدي السابق، فإنَّ الوكيل هو سامي، لكنَّ ذلك ليس مقياسًا يُعتدّ به؛ فقد يكون الوكيل في مسائل أخرى هو البرنامج أو النظام.
- الحالات (States): تُسمّى الحالات أيضًا النقاط أو العُقد (Nodes)؛ وهي مجموعة النقاط التي تُنظّم بشكل هرمي، وتُمثّل كل نقطة منها حالة من حالات فضاء البحث كما في الشكل (1-1) الذي يتضمّن الحالات الآتية: (أ، ب، ج، د، هـ، و، ز).
- الحالة الأوّلية (Initial State) أو الجذر (Roots): حالة ابتدائية للمشكلة؛ أي نقطة الانطلاق للبحث عن الحلّ، وتُمثلها المدينة (أ) في الشكل (1-1).
- الحالة الهدف (Goal State): حالة مرغوب الوصول إليها، وقد تكون حالة واحدة، أو مجموعة من الحالات، وتُمثلها المدينة (ز) في الشكل (1-1).
- الإجراءات (Actions): مجموعة من الإجراءات التي تقبل التطبيق، ويستطيع العميل تنفيذها للوصول إلى الحلّ، ويُمثلها الانتقال من المدينة (ب) إلى المدينة (د) في الشكل (1-1).
- النموذج الانتقالي (Transition Model): نموذج يُقدّم وصفًا لما يتضمّنه كل إجراء في حالة مُعيّنة.
- تكلفة الإجراء (Action Cost Function): تشير تكلفة الإجراء إلى التكلفة العددية لتطبيق إجراء مُعيّن. على سبيل المثال، عند الانتقال من مدينة إلى أخرى، قد تُحسب التكلفة بالمسافة المقطوعة، أو الوقت المُستغرق للوصول إلى المدينة المقصودة، أو بالتكلفة المادية للانتقال بين المدينتين، علمًا بأنَّ التكلفة الإجمالية هي مجموع تكلفة الإجراءات مُنفردة.
- المسار (Path): مجموعة النقاط أو الحالات المتتالية في الشجرة. ففي الشكل (1-1) مثلًا، المسار بين المدينة (ج) والمدينة (ز) هو: المدينة (ج) - المدينة (د) - المدينة (ز).
- الحلّ (Solution): مسار من النقطة الأوّلية (الابتدائية) إلى النقطة الهدف. ففي الشكل (1-1) مثلًا، الحلّ هو المسار الآتي: المدينة (أ) - المدينة (ج) - المدينة (د) - المدينة (ز).
- الحلّ الأمثل (Optimal Solution): حلّ ذو مسار أقل تكلفة بين مسارات الحلول المُحتملة (المُمكِنة) جميعها.
- الأب (Parent): عُقدة يتفرّع منها عُقد أخرى تُسمّى الأبناء. ففي الشكل (1-1) مثلًا، يُطلق على العُقدة (أ) اسم الأب، ويُطلق على العُقد (هـ، ج، ب) اسم الأبناء، في حين يُطلق على العُقدة (ز) اسم العُقدة الميتة؛ نظرًا إلى عدم وجود أبناء لها.
خوارزميات البحث
- تتمثّل آليّة عمل خوارزميات البحث في التركيز على خيار واحد، ووضع الخيارات الأخرى جانبًا؛ أي النظر إلى حالة واحدة فقط، فإذا تبيّن أنَّ هذه الحالة ليست الحالة الهدف، فيتمّ التوسّع في نطاق البحث، ليشمل البحث في إحدى عُقد الأبناء إلى حين الوصول إلى عُقدة ميتة (العُقدة التي ليس لها أبناء).
- يُطلق على مجموعة العُقد المتاحة للتوسّع في نقطة مُعيّنة اسم حدود التوسّع لتلك العُقدة (Frontier)، وقد تُسمّى أحيانًا القائمة المفتوحة (Open List).
المشكلات
- المشكلات القياسية (Standardized Problem): مشكلات يستخدمها الباحثون في المقارنة بين أداء الخوارزميات، ويُمكن وصفها بشكل موجز ودقيق.
- المشكلات الواقعية (Real-World Problem): مشكلات تتعلّق بالحياة العملية، ويُمكن صياغتها فردية، وهي ليست مُوحّدة.
روبوت التنظيف.
- الحالة الأوّلية (الابتدائية): يُمكن عدّ أيّ حالة من الحالات الظاهرة في الشكل حالة ابتدائية.
- الإجراءات: في عالم الشبكة الظاهرة في الشكل، حُدّدت ثلاثة إجراءات أساسية، هي: إزالة الأوساخ، والتحرّك إلى اليسار، والتحرّك إلى اليمين. وقد يضاف إلى هذه الإجراءات الثلاثة - في أمثلة…