مسئله های ارضای محدودیت CSP

مسئله های ارضای محدودیت CSP

همانطور که میدانید مسئله ها میتوانند از طریق جست وجو در فضایی از حالتها حل شوند. این حالتها را میتوان با ابتکارهای خاص دامنه ارزیابی، و تست کرد که آیا آنها حالتهای هدف هستند یا خیر. اما از نظر الگوریتم جست وجو هر حالت یک جعبه سیاه است که ساختار داخلی آن قابل تمیز دادن نیست.

در اینجا روشی داریم که تعداد زیادی از مسئله ها را با کارایی بیشتری حل میکند. برای هر حالت، از مجموعه ای از متغیرها که هر کدام دارای یک مقدار است، استفاده میکنیم. مسئله وقتی حل میشود که هر متغیر دارای مقداری باشد که تمام محدودیت های روی آن متغیر را برآورده کند (آن محدودیت را ارضا کند). مسئله ای که به این روش توصیف میشود، مسئله ارضای محدودیت یا  CSP نام دارد.

الگوریتم جست وجوی CSP از ساختار حالت استفاده میکند و به جای ابتکارهای خاص مسئله، از ابتکارهای همه منطوره برای حل مسئله های پیچیده بهره میگیرند. ایده ی اصلی این است که با مشخص کردن ترکیب هایی از متغیر/ مقدار که محدودیت ها را نقض میکنند، بخش های بزرگی از فضای جست وجو بطور همزمان حذف شوند.

مسئله های ارضای محدودیت شامل سه مولفه ی X ، D، و C است: 

► X مجموعه ای از متغیرها است،  {X₁, X₂, …, X_n}. 

► D مجموعه ای از دامنه هاست، {D₁, D₂, …, D_n} که برای هر متغیر یک دامنه وجود دارد.

► C مجموعه ای از محدودیت هاست که ترکیبهایی از مقادیر را مشخص میکند.

هر دامنه ی D_i شامل مجموعه ای از مقادیر مجاز {v₁, v₂, …, v_k} برای متغیر X_i است. هر محدودیت C_i شامل زوج (scope , rel) است، که scope یک چندتایی از متغیرهاست که سهمی در محدودیت دارد و rel رابطه ای است که مقادیری را تعریف میکند که آن متغیرها میتوانند بپذیرند. رابطه میتواند بصورت لیستی از تمام چندتایی هایی از مقادیرش نمایش داده شود که این مقادیر محدودیت ها را ارضا میکند، میتواند بصورت یک رابطه ی انتزاعی نشان داده شود که از دو عملیات پشتیبانی میکند:

► عملیاتی که تست میکند آیا یک چندتایی عضو این رابطه هست یا خیر؟

► عملیاتی که تعداد اعضای رابطه را شمارش میکند.

برای مثال، اگر X₁ و X₂ هر دو دارای دامنه ی {A , B } باشند، آنگاه محدودیتی که میگوید "دو متغیر باید مقادیر متفاوتی داشته باشند"، به صورت ( (X₁ , X₂) , [(A , B) , (B ,A) ] )  نوشته میشود.

برای حل CSP لازم است یک فضای حالت و مفهوم جواب را تعریف کنیم. هر حالت در CSP توسط انتساب مقادیر به تمام یا بعضی از متغیرها بصورت  { X_i = v_i , X_J = v_j ,…} تعریف میشود. انتسابی که هیچ محدودیتی را نقض نمیکند، انتساب سازگار یا معتبر نام دارد. انتساب کامل انتسابی است که در آن به هر متغیر مقداری نسبت داده شده است، و جواب CSP یک انتساب سازگار و کامل است. انتساب جزیی، انتسابی است که در آن مقادیر به بعضی از متغیرها نسبت داده میشود.