انتشار محدودیت در استنتاج CSP ها

 انتشار محدودیت در استنتاج CSP ها

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

ایده ی مهم، سازگاری محلی است. اگر با هر متغیر بعنوان گره ای در گراف و با هر محدودیت دوتایی بعنوان یال رفتار کنیم، آنگاه فرآیند اعمال سازگاری در هر قسمت از گراف، موجب میشود که مقادیر ناسازگار در سراسر گراف حذف شوند. انواع مختلفی از سازگاری محلی وجود دارند، که در ادامه آنها را بررسی میکنیم.

 

سازگاری گره

اگر تمام مقادیر موجود در دامنه متغیر (که هر متغیر متناظر با گره ای در شبکه CSP است)، محدودیت های یگانی مربوط به آن متغیر را برآورده کند، میگوییم این متغیر دارای سازگاری گره است. با اجرای سازگاری گره همیشه میتوان تمام محدودیت های یگانی را در CSP حذف کرد. علاوه براین میتوان تمام محدودیت های n تایی را به دوتایی تبدیل کرد. به همین دلیل معمولا حل کننده های CSP طوری تعریف میشوند که فقط با محدودیت های دوتایی کار کنند.

 

سازگاری یال

اگر هر مقدار موجود در دامنه ی متغیری در CSP، محدودیت های دودویی این متغیر را ارضا کند، میگوییم این متغیر دارای سازگاری یال است. به طور رسمی تر، متغیر X_i نسبت به متغیر دیگر X_j دارای سازگاری یال است اگر برای هر مقدار در دامنه ی فعلی D_i مقداری در دامنه D_j وجود داشته باشد که محدودیت دوتایی روی (X_i , X_j) را ارضا کند. هر شبکه در صورتی سازگاری یال دارد که در آن هر متغیر با متغیر دیگری سازگاری یال باشد.

میتوان مفهوم سازگاری یال را تعمیم داد تا محدودیت های n تایی را نیز اداره کند (نه فقط محدودیت های دوتایی) . این تعمیم "سازگاری یال تعمیم یافته" یا سازگاری ابر گراف، نام دارد. اگر برای هر مقدار v در دامنه متغیر X_i یک چندتایی از مقادیر وجود داشته باشد که عضوی از این محدودیت باشد، متغیر X_i دارای "سازگاری یال تعمیم یافته" است و تمام مقادیر این چندتایی از دامنه های متناظر با متغیرها انتخاب میشوند، مولفه های X_i آن برابر با v است.

 

سازگاری مسیر

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

مجموعه دو متغیر {X_i , X_j} را در نظر بگیرید. اگر برای هر انتساب { X_i =a , X_j =b } سازگار با محدودیت های روی  {X_i , X_j} انتسابی به X_m وجود داشته باشد که محدودیت های روی  {X_i , X_m } و  { X_m , X_j} را ارضا کند، مجموعه  {X_i , X_j} سازگاری مسیر دارد. علت اینکه این سازگاری را به نام سازگاری مسیر میخوانیم این است که میتوان آن را مسیری از X_i به X_j دانست که X_m در وسط قرار دارد.

 

سازگاری مرتبه k

شکل های قوی تر "انتشار محدودیت" را میتوان با مفهوم سازگاری مرتبه k تعریف کرد.CSP در صورتی سازگاری مرتبه k دارد که برای هر مجموعه k-1 متغیری و برای هر اتساب سازگار با آن متغیرها، همیشه بتوان یک مقدار سازگار را به هر متغیر k ام نسبت داد. سازگاری مرتبه 1 میگوید که با توجه به یک مجموعه یال میتوان هر مجموعه ی یک متغیری را سازگار کرد، و این همان چیزی است که قبلا آن را سازگاری گره نامیدیم. سازگاری مرتبه 2 مثل سازگاری یال است. برای شبکه هایی با محدودیت های دوتایی سازگاری مرتبه 3 شبیه سازگاری مسیر است.

CSP در صورتی قویا سازگار مرتبه ی kام است که سازگار مرتبه k، سازگار مرتبه ی k-1، سازگار مرتبه k-2، و ... تا سازگار مرتبه 1 باشد. هر الگوریتم برای به دست آوردن سازگاری مرتبه n در بدترین  حالت زمانی که مصرف میکند برحسب n نمایی است. مسئله حافظه از زمان جدی تر است. در عمل، تعیین سطح مناسبی از سازگاری یک علم تجربی است.