الذكاء الإصطناعي : تقنيات شرطا الرضا + مسائل و حلها بالتفصيل #الدر السابع
السلام عليكم ، اليوم و مع درسمهم جداً ، ألا و هو درس شرطا الرضا أو الـConstraint Satisfaction Techniques ، و س،اخذ مسألة على الدرس و سنقوم بحلها ، كما طلبتم مني ، و كما وعدتكم ، و هيا لنبدأ إذاً...
- تقنيات شرطا الرضا Constraint Satisfaction Techniques :
القيد أو الشرط : و هو علاقة منطقية خلال عدة متغيرات مثلاً "رسم دائرة داخل مربع" وهي مسألة هندسية شهيرة ، تحتاج إلى تطبيق مجموعة معينة من الشروط بالمربع و بالدائرة ، فالشروط تربط الكائنات بدقة ، بدون تديد الموقف منها أو حذف أي كائن ، لكي تبقى العلاقة سليمة.
القيد أو شرطا الرضا : هي عمليو إيجاد حل لمجموعة من القيود أو شروط ، بحيث تحدد الشروط و القيم الميموح بها للمتغيرات ، و لإيجاد الحل يتم تقييد هذه المتغيرات لفحص مدى مطابقتها لشروط الرضا Satisfaction ، أو بالأحرى هي شروط القبول.
إذن مسألة شرطا الرضا و حلها : و يرمز لها بـ"CSP" لأنها إختصار لكلمة Constraint Satisfaction Problem K
- حيث تتكون المسألة من :
#المتغيرات ، محموعة النهايات مثل نهايات الرياضيات من العدد x1 إلى العدد xn حيث n عدد طبيعي أو حسب نوع المسألة.
#النطاق ، المجموعة المنتهية Di للقيم المحتملة التي يمكن أن يأخذها المتغير Xi.
#الشروط ، مجموعة من القين التي تحد مطتبقة المتغيرات للشروط في نفس الوقت (D1 != D2) .
- حل المسألة CSP :
سنحل المسألة كإرتباط بين القيم من النطاق المحدد ألى جميع المتغيرات التي تطابق أو تناسب كل القيد ، و يمكن هذا أن يكون :
#حل واحد مقبول ، دون تحديده بالضبط.
#جميع الحلول مقبولة و مرضية تماماً.
#الحل المثالي أو الجيد ، ( مسألة الشرط المثالي COP ).
حيث توجد تطبيقات كثيرة لتقنية شرط الرضا في الذكاء الإصطناعي و مجالات كثيرة مثل لغات البرمجة و المنطق الإحتسابي ، و حتى الحوسبة الرموزية Symbolic Computing.
مثال للعبة الملكات-ن N-Queens puzzle :
ليكن لدينا عدد صحيح نسميه N من الملكات ، في رقعة شطرنج و لتكن أبعادها N*N ، و يتم وضعها بحيث تحقق شرط الرضا ة هو أن لا تهدد ملكة ملكة أخرى في الرقعة ، و يكون ذلك عندما تكون ملكتان متقابلتان في نفس الصف أو العمود أو بشكل مائل.
الحل : من أجل نمذجة هذه المسألة
- لنفرض أن كل ملكة في مختلف عن الأخرى.
- انربط المتغيرات (Ri (i = 1 to N بملكة في العمود رقم i ، مع تحديد موقع الملكة في الصف.
- و لنطبق أيضاً شرط عدم التهديد بين كل زوج من القطع Ri و Rj ، و لنطور بعدها الخوارزمية.
ملاحضة : لمن لا يعرف الخوارزميات أو معناها ، أو مذا نعمل بها ، فاليطلب مني ، لنقدم مفهوم أو دورة على الخوارزميات
مثال ثاني "2" تلوين الخريطة Map Coloring :
تعطى خريطة بيانية أو بالأحرى رسومية و عدد من الألون "مثلاً 4 ألوان" ، و المسألة هي كيف نربط الألوان بتلك المساحات في الخريطة (فقط فكر حيدأً) و حيث ننضر لها كنقاط لنسهل الأمر ، بحيث يتحقق الشرط الذي يقتضي منع أن ترتبط نقطتين يعني "مساحتين" متجاورتين بنفس الون ، آآآآ الآن إتضح وجه كبير من الحل.
الحل : من أجل نمذجة مسألة تلوين الخريطة :
- نقوم بتمية كل نقط (مساحة) في الخريطة بمتغير حيث نطاق المتغيرات يكون مناضر لمجموعة الألون.
- تقدم شرط عدم تساوي قيم أي متغيرين حيث سمينا الألوان متغير ، يسميان نقطتين متجاورتين.
هذه المسألة طرحناها من نضرية الألوان الأربعة ، و ما هي نضرية الألوان الأربعة : حيث تنص هذه النضرية على أي يكفي لرسم أي خريطة أن نستخدم أربعة ألوان فقط ، بحيث أن لا تكون أي مناطق متشابهة في اللون ، أي أن التي تكون لها حدود مشتركة تون ملونة بلون مختلف... هذه الصورة توضح رسم خريطة بتقنية الألوان الأربعة هذه النضرية :
وصلنا إلى نهاية الدرس ، السلام عليكم ، و نشكركم لمتابعتكم لدروسنا...
تصفح قائمة جميع الدروس من : هنا