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

Report
Constraint Satisfaction
Problems
(CSP)
‫• مساله ارضای محدودیت به وسیله مجموعه ای از متغیرهای ‪ X1,X2,… , Xn‬و مجموعه‬
‫ای از محدودیت های ‪ C1, C2, … , Cn‬تعریف می شود‪.‬‬
‫• هر متغیر ‪ Xi‬دارای یک دامنه ناتهی ‪ Di‬با مقادیر ممکن است‪.‬‬
‫• هر محدودیت ‪ Ci‬شامل زیر مجموعه هایی از متغیرها و ترکیب های ممکنی از مقادیر برای آن‬
‫زیرمجموعه هاست‪.‬‬
‫• هر حالت مساله با انتساب مقادیری به چند یا تمام متغیرها تعریف می شود‪:‬‬
‫}… ‪• {Xi = vi, Xj = vj ,‬‬
‫• انتسابی که هیچ محدودیتی را نقض نکند‪ ،‬انتساب سازگار یا معتبر نام دارد‪.‬‬
‫• انتساب کامل آن است که هر متغیری در آن باشد‪.‬‬
‫• راه حل ‪ CSP‬یک انتساب کامل است اگر تمام محدودیتها را برآورده کند‪.‬‬
‫• بعض ی از ‪ CSP‬ها به راه حل هایی نیاز دارند که تابع هدف را بیشینه کنند‪.‬‬
‫• عمق هر راه حل‪ ،‬اگر ‪ n‬متغیر وجود داشته باشد‪ n ،‬است‪.‬‬
‫• الگوریتمهای عمقی برای ‪ CSP‬ها مناسب اند‪.‬‬
‫گراف محدودیت‬
‫فرمول بندی افزایش ی‬
‫•حالت اولیه‪ :‬انتساب خالی }{ بدون متغیر‬
‫•تابع جانشین‪ :‬انتساب یک مقدار به یک متغیر به شرط رعایت محدودیت‬
‫•آزمون هدف‪ :‬انتساب کامل‬
‫•هزینه مسیر‪ :‬هزینه ثابت برای هر مرحله‬
‫چون مسیر رسیدن به راه حل مهم نیست می توان از فرمول بندی کامل نیز استفاده کرد‪.‬‬
‫مساله های ارضای محدودیت (‪)CSP‬‬
‫یک نمونه راه حل‬
‫ساده ترین نوع ‪ CSP‬ها شامل متغیرهایی است که گسسته اند و دامنههای متناهی دارند‪ .‬مثل رنگ‬
‫آمیزی نقشه و مساله هشت وزیر‬
‫محدوديتها به گونههاي مختلفي ظاهر ميشوند‪:‬‬
‫‪ ‬محدوديتهاي يکتا‬
‫‪ ‬محدوديتهاي دودويي‬
‫محدوديتهاي مطلق •‬
‫محدوديتهاي اولويتدار•‬
‫‪CSP‬ها ميتوانند توسط الگوريتمهاي جستجوي ‪ general-purpose‬حل شوند‪ ،‬اما به‬
‫علت ساختار خاص آنها‪ ،‬الگوريتمهايي صرفا براي ‪ CSP‬ها طرح ميشوند که از الگوريتمهاي‬
‫عمومي کارآيي بهتري دارند‪.‬‬
‫تعویض پذیری یکی از خواص مهم ‪CSP‬‬
‫جستجوی عقبگرد‪ ،‬با استفاده از روش یک مقدار در هر زمان‬
‫مقادیر باقیمانده کمینه (‪)Minimum Remaining Values‬‬
‫پس از انتساب‬
‫‪WA = red‬‬
‫‪NT = green‬‬
‫فقط یک مقدار برای ‪ SA‬وجود دارد‬
‫به جای ‪ Q‬قدم بعدی ‪ SA = blue‬انجام می شود‪.‬‬
‫وقتی انتساب به ‪ X‬صورت می گیرد‪ ،‬فرآیند بررس ی پیش رو‪،‬‬
‫متغیرهای بدون انتساب مثل ‪ Y‬را در نظر می گیردکه از طریق یک‬
‫محدودیت به ‪ X‬متصل است و هر مقداری را که با مقدار انتخاب‬
‫شده برای ‪ X‬برابر است‪ ،‬از دامنه ‪ Y‬حذف می کند‪.‬‬
‫• جست و جوی محلی با اکتشاف کمترین برخورد‬
‫• انتخاب مقداري كه كمترين برخورد را با متغیرهاي ديگر ايجاد كند‬

similar documents