المعالجة السابقة لإرضاء قيود مشكلة ذات قيود مشدّدة بغية تعيين وحل الصراعات

Abstract

ينظر إلى مشكلة إرضاء القيود (CSP) على أنها ذات قيود مشددة، إذا لم يكن لها حل، وكانت قيودها متصارعة. وسنقوم هنا بتسمية المجموعات الفرعية من القيود المتصارعة بعضها مع بعض، بالمجموعات المتصارعة.<br>إن عملية تعيين أو تحديد هذه المجموعات المتصارعة تسمى تعيين الصراع. وفي هذا البحث، نقترح خوارزميات لتعيين المجموعات المتصارعة لأرضاء قيود مشكلة ذات قيود مشددة بغية حل هذه الصراعات. وسنري هنا كيف أن هذه المجموعات المتصارعة تظهر كل الطرق المختلفة لحل هذه الصراعات وبالتالي تحدد فراغ التراخي (الذي يكمن فيه الحل مع مراعاة حدود القيود).<br>ونقترح في هذا البحث أيضا خوارزمية لإيجاد فراغ التراخي الأمثل، الذي ييسر تعيين أقل عدد ممكن من القيود لحل الصراع. وفي هذه الخوارزمية، نقترح طريقة معالجة سابقة (ابتدائية) لمشكلة إرضاء القيود المشددة (CSP) بحيث تستخدم معلومات التراخي التي نحصل عليها من المجموعات المتصارعة في الحل الأمثل لهذه المشكلة. وأثبت البحث أن هذه الطريقة تحسّن أداء خوارزميات التفرع والتقييد المستخدمة في الوصول إلى الحل المطلوب.