إرضاء القيود

في مجال الذكاء الاصطناعي وبحوث العمليات ، يُعرف إرضاء القيود بأنه عملية إيجاد حل من خلال مجموعة من القيود التي تفرض شروطًا يجب أن تستوفيها المتغيرات . ^{[ 1 ]} وبالتالي، فإن الحل هو تعيين قيم للمتغيرات بحيث تستوفي جميع القيود ، أي نقطة في المنطقة الممكنة .

تعتمد التقنيات المستخدمة في حل القيود على نوع القيود المطروحة. غالبًا ما تُستخدم القيود المفروضة على نطاق محدود ، لدرجة أن مسائل حل القيود تُعرَّف عادةً بأنها مسائل قائمة على قيود في نطاق محدود. تُحل هذه المسائل عادةً عن طريق البحث ، وتحديدًا باستخدام أسلوب التراجع أو البحث المحلي . يُعد نشر القيود مجموعة أخرى من الأساليب المستخدمة في هذه المسائل؛ ومعظمها غير مكتمل بشكل عام، أي أنها قد تحل المسألة أو تثبت عدم قابليتها للحل، ولكن ليس دائمًا. تُستخدم أساليب نشر القيود أيضًا بالتزامن مع البحث لتسهيل حل المسألة. من أنواع القيود الأخرى التي تُدرس، القيود المفروضة على الأعداد الحقيقية أو النسبية ؛ ويتم حل المسائل المتعلقة بهذه القيود عن طريق حذف المتغيرات أو خوارزمية السمبلكس .

نشأت مسألة إرضاء القيود كمشكلة عامة في مجال الذكاء الاصطناعي في سبعينيات القرن العشرين (انظر على سبيل المثال ( Laurière 1978 ) ). ومع ذلك، عندما تُعبَّر القيود كمعادلات خطية متعددة المتغيرات تُعرِّف متباينات (أو عدم متباينات)، فإن هذا المجال يعود إلى جوزيف فورييه في القرن التاسع عشر: فقد سمح اختراع جورج دانتزيج لخوارزمية سيمبلكس للبرمجة الخطية (وهي حالة خاصة من التحسين الرياضي) في عام 1946 بتحديد حلول ممكنة لمسائل تحتوي على مئات المتغيرات.

خلال ثمانينيات وتسعينيات القرن العشرين، تم تطوير دمج القيود في لغات البرمجة . وكانت لغة برولوج أول لغة مصممة خصيصًا لدعم برمجة القيود بشكل جوهري . ومنذ ذلك الحين، أصبحت مكتبات برمجة القيود متاحة في لغات أخرى، مثل سي++ أو جافا (على سبيل المثال، تشوكو لجافا ^{[ 2 ]} ).

كما عُرِّفت في الأصل في مجال الذكاء الاصطناعي، تُحدِّد القيود القيم الممكنة التي قد تأخذها مجموعة من المتغيرات في عالم مُعطى. العالم الممكن هو مجموعة كاملة من القيم المُخصصة للمتغيرات، والتي تُمثِّل طريقةً يُمكن أن يكون عليها العالم (حقيقيًا كان أم مُتخيَّلًا). ^{[ 3 ]} وبشكلٍ غير رسمي، المجال المحدود هو مجموعة محدودة من العناصر العشوائية. تتضمن مسألة إرضاء القيود على هذا المجال مجموعة من المتغيرات التي لا يُمكن أن تأخذ قيمها إلا من هذا المجال، ومجموعة من القيود، حيث يُحدِّد كل قيد القيم المسموح بها لمجموعة من المتغيرات. حل هذه المسألة هو تقييم المتغيرات الذي يُرضي جميع القيود. بعبارة أخرى، الحل هو طريقة لتخصيص قيمة لكل متغير بحيث تُرضي هذه القيم جميع القيود.

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

عملياً، غالباً ما تُصاغ القيود بصيغة مختصرة، بدلاً من سرد جميع قيم المتغيرات التي تُحقق القيد. ومن أكثر القيود استخداماً (بشكل بديهي) القيد الذي ينص على أن قيم المتغيرات المتأثرة يجب أن تكون جميعها مختلفة.

من بين المشكلات التي يمكن التعبير عنها كمشكلات إرضاء القيود، لغز الملكات الثماني ، ومسألة حل سودوكو ، والعديد من الألغاز المنطقية الأخرى، ومسألة الإرضاء البولياني ، ومشكلات الجدولة ، ومشكلات تقدير الخطأ المحدود ، ومشكلات متنوعة على الرسوم البيانية مثل مشكلة تلوين الرسوم البيانية .

على الرغم من أن المعادلات والمتباينات الحسابية لا تُدرج عادةً في التعريف المذكور أعلاه لمسألة إرضاء القيود، إلا أنها تُقيّد قيم المتغيرات التي تحتويها، وبالتالي يمكن اعتبارها شكلاً من أشكال القيود. مجالها هو مجموعة الأعداد (سواء كانت صحيحة أو نسبية أو حقيقية)، وهي مجموعة غير منتهية؛ لذلك، قد تكون علاقات هذه القيود غير منتهية أيضاً؛ على سبيل المثال،${\displaystyle X=Y+1}$يحتوي على عدد لا نهائي من أزواج القيم المُرضية. غالبًا ما تُهمل المعادلات والمتباينات الحسابية ضمن تعريف "مسألة إرضاء القيود"، الذي يقتصر على نطاقات محدودة. ومع ذلك، تُستخدم بكثرة في برمجة القيود .

يمكن إثبات أن المتباينات أو المعادلات الحسابية الموجودة في بعض أنواع ألغاز المنطق المحدود مثل Futoshiki أو Kakuro (المعروفة أيضًا باسم Cross Sums) يمكن التعامل معها كقيود غير حسابية (انظر إرضاء القيود القائم على الأنماط وألغاز المنطق ^{[ 4 ]} ).

البرمجة المقيدة هي استخدام القيود كلغة برمجة لترميز المشكلات وحلها. ويتم ذلك غالبًا عن طريق تضمين القيود في لغة برمجة تُسمى اللغة المضيفة. نشأت البرمجة المقيدة من صياغة رسمية لمعادلات الحدود في لغة برولوج 2 ، مما أدى إلى إطار عمل عام لتضمين القيود في لغة برمجة منطقية . من أشهر اللغات المضيفة برولوج ، وسي++ ، وجافا ، ولكن استُخدمت لغات أخرى أيضًا.

• مشكلة إرضاء القيود
• القيد (الرياضيات)
• الحل المرشح
• مشكلة إرضاء المنطق البولياني
• نظرية القرار
• قابلية الإرضاء وفقًا للنظريات
• التكوين القائم على المعرفة

• برنامج تعليمي لـ CSP