ألفا ويب - alfa web  ألفا ويب - alfa web
recent

أحدث المقالات

recent
برمجة
جاري التحميل ...

الذكاء الإصطناعي: نماذج ومسائل شرط الرضا CSPs #الدرس الثالث والثلاثون

الشروط تظهر في معظم مجالات المساعي البشرية، وهي وسائط طبيعية للناس كيْ تعبر عن المشاكل والمسائل في أكثر الحقول.. أكثر المسائل الحقيقية في الذكاء الإصطناعي يمكن أن تُنمذج كمسائل شرط الرضا (CSPs)، ويتم حلها عبر تقنيات البحث، ومن أمثلة الشروط:
  • مجموعة ثلاثة (3) زوايا المثلث هو 180 درجة.
  • مجموعة التيارات التي تصب في نقطة واحدة يجب أن يُساوي الصفر.
الشرط هو علاقة منطقية بيت متغيرين أو عدة متغيرات، فالشروط تربط الكائنات بدون تحديد دقيق لمواقعها، وعند تحريك أي واحد منها نظل محافظين على العلاقة. مثال: "مربع داخل دائرة أو ما شابه".
الذكاء الإصطناعي: نماذج ومسائل شرط الرضا CSPs

شرط الرضا Constraint satisfaction:

شرط الرضا هو عملية إيجاد الحل لمجموعة معينة من الشروط، هذه الشروط تُحدد سماحية القيم للمتغيرات. وإيجاد الحل هو تقييم لتلك التغيرات التي تُحقق جميع الشروط.

مسائل شرط الرضا (Constraint Satisfaction problems (CSPs:

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

وهذه أمثلة لمسائل الرضا Ex: of CSPs

فيما يلي مجموعة من المسائل الشائعة الشبيهة بلعبة اللغز، مثل المربع اللاتيني Latin Square والملكات الثمانية Eight Queens، ولعبة السودوكو Sudoku المعرفة على سبيل المثال أيضًا.

مسألة: المربع اللاتيني Latin Square:

بكل بساطة: كيف نستطيع تعبئة جدول أبعاده (n*n) وبـ n رمزًا مختلفًا، بحث أن كل رمز يقع بالضبط مرة واحدة في كل صف وعمود. هذا هو شرط الرضا، فلو كان لدينا مربعات لاتينية من n=1 إلى n=4 وكانت الرموز هي الأرقام نفسها لكل مربع. فإن حلها يكون من تحقيق شرط عدم ظهور الرقم في نصف الصف أو العمود مرتين. وسيكون كما في الشكل أو الصورة التالية:

مسألة: لغز الملكات الثمانية Eight Queens Puzzle:

شرط الرضا في المسألة هو: كيف نستطيع وضع ثمان ملكات على رقعة أبعادها (8*8) بشرط عدم تهديد أي ملكة للأخرى. والإجاية عن المسألة Solutions:
يمكلك هذا الأخير لغز الملكات الثمان 92 حلاً مختلفًا، وعندما نأخذ بالحسبان الحلول المتشابهة الناتجة عن التدوير والإنعكاس لرقعة الشطرنج. سيكون لهذا اللغز 12 حلاً وحيدًا، مع إفتراض أن الحالة الإبتدائية هي حالة الرقعة الفارغة والملكات خارجها، وكل الحلول السابقة هي حالات هذف محتملة.

مسألة: السودوكو Sudoku:

كيف يمكن تعبئة جميع مربعات شبكة مجزأة (9*9)  بحيث يكون كل صنف وكل عمود وكل مربع (3*3) من المربعات التسعة، مكونًا من جميع الأعداد من 1 إلى 9.. وفي الشكلين التاليين مسألة وحلها حيث يتم الإعطاء حالة إبتدائية للشبكة، يتم تعبئتها للوصول إلى حالة هدف تحقق الشرط:

نماذج شرط الرضا Constraint Satisfaction Models:

يقوم الإنسان بحل المسائل الموضحة أعلاه، عندما يقوم بالمُحاولة مجربًا حالات مُختلفة. مستخدمًا عددًا متنوعًا من عدد المشاهدات حول المسألة، من أجل إستكشاف عدد صغير من المحاولات.. وقد لا يكون من الواضح ما هي المشاهدات المطلوبة، فعلى سبيل المثال بالنسبة للملكات الثمان، في رقعة الشطرنج القياسية (8*8)، وكما أسلفنا أو ذكرنا أن لدينا 92 حلاً للمسألة. عندما يقوم الإنسان بمحاولة حل المسألة؛ يكون من الصعب عليه فعل ذلك عندما تكون قيمة N أكبر.. وفي ما يلي أمثلة عن الحالات الممكنة لكل رقعة حسب قيم N أي عدد الملكات وأبعاد الرقعة:

For 4-Queens there are 256 different configurations.
For 8-Queens there are 16,777,216 configurations.
For 16-Queens there are 18,446,744,073,709,551,616 configurations.
In general, for N - Queens there are we have NN configurations.
For N = 16, this would take about 12,000 years on a fast machine.

كيف نقوم بحل مسائل كهذه؟

في ما يلي ثلاثة (3) نماذج أو منهجيات معتمدة على الحاسوب. وهي:
  1. إفترض ثم إختبر Generate and Test.
  2. التتبع الخفي Backtracking.
  3. مسائل شرط الرضا (Constrain Satisfaction Problems (CSPs.
وفي الدرس القادم (الجزىء الثاني للدرس الثالث والثلاثون)، نقوم بحل المسائل المذكورة بالطرق أو النماذج أو المنهجيات الثلاثة (3) المذكورة أعلاه. وهذا التقسيم من أجل عدم نفور القارئ والتعلم بسبب طول الدرس أو المقال.

دروس سابقة:

عن الكاتب

Mr Salah

التعليقات


جميع الحقوق محفوظة

ألفا ويب - alfa web