تقنيات البحث بآلية الكشف Heuristic Search Techniques
تقنيات البحث بآلية الكشف :
للمسائل المعقدة في الخوارزميات المذكورة في الدرس السابق، لا تقدر على إيجاد الحل ضمن زمن واقعي و فضاء محدد، و لهذا كثير من التقنيات طُوِرت بشكل كبير باستخدام دوال آلية الكشف:
- البحث الأعمى غير ممكن دائمًا لأنه يتطلب زمن أو ذاكرة كبيرتين، أما البحث الموجه فهو تقنية ضعيفة، لكنه يمكن أن يكون فعالاً إن تم تطبيقه بشكل صحيح، فهو يتطلب معلومات محددة عن ميدان المسألة.
خصائص البحث مع الكشف :
آليات الكشف Heuristics هي تلك المعرفة عن ميدان المسألة، التي تساعد البحث و الإستنباط في ذلك الميدان، و هو يدمج المعرفة الميدانية لتطوير الكفاءة عبر البحث الأعمى، و هي دوال عند تطبيقها على الحالات تعيد لنا قيمًا كما قدرنا لتلك الحالات فيما يتعلق بالهدف، و آليات الكشف التي تكون أقل من التوقع تكون مطلوبة و ندْعُوها بالمقبولة admissible.
دالة تقييم الكشف تُقدم تقديرًا عن إمكانية إعطاء الحالة التي تقود إلى حالة الهدف، و دالة اللبحث الموجه تعطي تكلفة تقديرية من الحالة الحالية إلى الهدف، بافتراض كفاءة الدالة.
البحث بآلية الكشف مقارنةً بيتقنية البحث الأعمى :
البحث بآلية الكشف :
- تقوم بتقدير مسافة "Distance" إلى الحالة الهدف.
- يرشد عمليات البحث باتجاه الحالة الهدف.
- يميز الحالات أو النقاط الأقرب مسافة إلى الحالة الهدف، و ليس بعيدة عنها.
البحث الأعمى أو القوة العمياء :
- لديها معرفة فقط عن النقاط التي قامت باكتشافها من قبل.
- لا توجد معرفة حول كيف تبعد أي نقطة عن الحالة الهدف.
مثال: اللغز بثمان مربعات :
- الحالة الإبتدائية State Initial: أي فضاء حالة غير مرتب كما في الشكل.
- الحالة الهدف Goal State: القطع الثمان مرتبة كما في الشكل.
- الحل Solution: السلسلة المثالية للمشتغلين باللعبة لتحقيق الحالة الهدف.
- الفعل Action: تحريك المربع الفارغ "Blank Moves".
- الشروط Condition: أن تكون الحركات (الأفعال) خلال ضمن اللوح.
- الإتجاهات Direction: الإتجاهات الأربع إن أمكن Dn, Up, Right, Left.
المسألة Problem:
أي تحريكات اللغز هي الأفضل؟ ما هي آلية الكشف التي يمكن إستخدامها؟ أي الخطوات أفضل من ناحية عدم البدأ بالأسوأ.الأفعال Action:
الشكل أدناه يوضج لنا ثلاثة حالاتت إنتقالية محتملة و هي: Left, Up, Right.
- أولاً: نقوم بحساب المواقع الصحيحة لكل قطعة مقارنة بالحالة الهدف.
- ثانيًا: نحسب المواقع الخاطئة لكل قطعة مقارنة بالحالة الهدف.
- ثالثًا: نحسب كم تبعد كل قطعة عن موقعها الصحيح في الحالة الهدف.
و بالنسبة للحالات في المثال في الشكل السابق؛ الجدول التالي يوضح الحسابات أعلاه :
شرح آلية الكشف Heuristic (الجدول):
كما جاء في الجدول، هناك ثلاثة منهجيات Apporaches لآلية الكشف :
المنهجية الأولى 1st approach: منهجيتها حساب المواقع الصحيحة لكل قطعة مقارنة بالحالة الهدف، و تكون المنهجية ناجحة أكثر كلما كان عدد الحالات صحيحة الموقع أكثر في الحالة الإبتدائية، كما تتصف بسهولة الحساب فهي أسرع و تأخذ ذاكرة أقل كما أنها أسهل طرق الكشف المحتملة.
المنهجية الثانية 2st approach: منهجيتها حساب المواقع الغير صحيحة لكل قطعة، مقارنة بالحالة الهدف، و تكون المنهجية أفضل كلما كان كان عدد الحالات الخاظئة أقل، و تكون الحركة الأفضل هي التي تؤدي إلى إنقاص عدد الحالات العائدة من منهجية الكشف.
المنهجية الثالثة 3st approach: منهجيتها حساب كم تبعد كل قطعة عن الموقع الصحيح، أي كم عدد الإنتقالات اللازمة لوصول القطعة إلى موقعها الصحيح، و حساب العدد الإجمالي لجميع القطع، و أفضل حركة هي التي تُؤدي إلى إنقاص الحالات العائدة من آلية الكشف.
خوارزميات البحث بآلية الكشف Hueristic Search Algorithms:
- خوارزمية إفترض واختبر Generate and Test
- خوارزمية تسلق الجبل Hill Climbing
- خوارزمية البحث عن الأفضل أولاً Best First Search
- خوارزمية البحث بتقليص المشكلة Problem Reduction
- خوارزمية تحقيق شرط الرضا Constraint Satisfaction
- خوارزمية النهاية المطلوبة Mean end Analysis
ملاحظة! جميع الخوارزميات المذكورة أعلاه تم شرحها في الدروس السابقة، يمكنك البحث عنها من مربع البحث في أعلى الموقع.