بخشی از پاورپوینت
اسلاید 1 :
فصل پنجم
مسائل ارضای محدوديت (CSP)
اسلاید 2 :
فهرست
ارضای محدوديت چيست؟
جستجوی پس گرد در CSP
وارسی پيش رو
انتشار محدوديت
جستجوی محلی در مسائل دارای محدودیت
اسلاید 3 :
مقدمه
بسیاری از مسائل مهندسی کامپیوتر جزو دسته مسائل ارضای محدودیت هستند به عنوان مثال میتوان به مساله زمان بندی jobها مثلا در سیستم عامل اشاره کرد. یا مساله رنگ آمیزی گراف که در این درس مورد بررسی قرار خواهد گرفت و بسیار مسائل دیگر.
به عنوان مثال به این فکر کنید چه محدودیتهایی برای مجموعه اساتید و کلاسهای یک دانشگاه وجود خواهد داشت؟ بین مجموعه دانشجوها و درس چطور؟
اسلاید 4 :
چرا مسائل را باید به فرم ارضای محدودیت تعریف کنیم؟
۱- در الگوریتمهای هوشمند قبلی دیدیم که باید تابع هوریستیک تعریف کنیم. این هم اشاره کردیم که تعریف هوریستیک کار آسانی نیست آن هم هوریستیکی که تخمین نزدیک به صحیح بزند. این باعث میشود که الگوریتمهایی مثلA* همه جان کاربرد نداشته باشند. اگر من بتوانم مساله را به فرم جامع تری تعریف کنم (یعنی هوریستیک کلی ارائه بدهم) آنگاه میتونم هر مساله را در قالب آن هوریستیک کلی ببرم و حل کنم. این هوریستیک کلی همین ارضای محدودیت است.
۲ - اگر مساله یی به فرم ارضای محدودیت تعریف شود، میتوان الگوریتمهای جستجو خاصی را روی آن اعمال کرد و به جواب رسید
اسلاید 5 :
مجموعه متناهی از متغيرها؛ X1, X2, …, Xn
مجموعه متناهی از محدوديتها؛ C1, C2, …, Cm
دامنه های متناهی ناتهی برای هر يک از متغيرها؛DX1,DX2,…,DXn
هر محدوديت Ci زيرمجموعه ای از متغيرها و ترکيبهای ممکنی از مقادير برای آن زيرمجموعه ها
محدودیتها میتوانند یکانی ( xi = odd integers) یا دو گانی (رنگ آمیزی گراف) باشند
وقتی ما به تمام متغیرها مقادیر مجاز تخصیص دهیم به طوری که همهٔ محدودیتها ارضا شوند میگوییم به جواب )راه حل ( رسیدیم
هر حالت با انتساب مقاديری به چند يا تمام متغيرها تعريف مي شود.
انتسابی که هيچ محدوديتی را نقض نکند، انتساب سازگار یا مجاز نام دارد.
انتساب کامل آن است که هر متغيری در آن باشد.
راه حل CSP يک انتساب کامل است اگر تمام محدوديتها را برآورده کند.
بعضی از CSPها به راه حلهايي نياز دارند که تابع هدف را بيشينه کنند.
ارضای محدوديت (CSP) چيست؟
اسلاید 6 :
متغيرها: WA, NT, Q, NSW, V, SA, T
دامنه: {آبی، سبز، قرمز} = Di
محدوديتها: نواحی مجاور، دارای
رنگهای متمایز.
مثال: WA ≠ NT يعنی (WA,NT) عضو:
{(قرمز,سبز),(قرمز,آبی),(سبز,قرمز)،(سبز,آبی),(آبی,قرمز),(آبی,سبز)}
مثال CSP: رنگ آميزی نقشه استرالیا
شکل 5-1 (الف)
اسلاید 7 :
مثال CSP: رنگ آميزی نقشه استرالیا
راه حلهای متعددی مانند آنچه در ذیل نشان داده شده بدست خواهد آمد:
{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red }
اسلاید 8 :
در گراف محدوديت:
گره ها: متغيرها
يالها: محدوديتها
گراف برای ساده تر کردن جستجو بکار مي رود.
مساله رنگ آمیزی نقشه به شکل گراف محدودیت
شکل 5-1 (ب)
اسلاید 9 :
N Queens
اسلاید 10 :
متغيرها: F,T,U,W,R,O,X1,X2,X3 دامنه:{9و8و7و6و5و4و3و2و1و0}
در مساله رمز نگاری کلا ۲ نوع محدودیت داریم1- Alldifferent (F,O,U,R,W,T) :
مثال CSP: رمزنگاری
2- O + O = R + 10*X1, W+W+x1 = U + 10*x2,
T+T+x2 = O + 10 *x3 X3 = F
اسلاید 11 :
بعد از توصیف مساله به صورت ارضای محدودیت باید فضای حالتش را توصیف کنیم:
۱- از حالت اولیه شروع کن
۲- توسط تابع پسین تمام مابعدهایی که از طریق ارضای محدودیت میتونیم آن را تولید کنیم تولید کن
۳- یک آزمون هدف داشته باش تا بتوانی بر روی گرههای درخت اعمال کنی
General Algorithm in slide 13
اسلاید 12 :
Initial state
اول عمق با بازگشت به عقب گزینه خوبی برای جستجو در فضا حالت است، اول عرض چطور؟
اگر بنا باشد نودی را گسترش دهیم، فقط فرزندانی را تولید میکنیم که محدودیتها را ارضا کنند
۱-فضای ایجاد شده حتما درخت است
۲- درخت متناهی است و عمقش هم خیلی زیاد نیست
۳- عرض درخت میتواند زیاد باشد ( لا اقل بیشتر از عمقش)
۴- در مسائل ارضای محدودیت در صورت هدف ، هدف حتما برگ است
اسلاید 13 :
برای CSP مي توان فرمول بندی افزايشي ارائه کرد:
حالت اوليه: انتساب خالی{} که در آن، هيچ متغيری مقدار ندارد.
تابع جانشين: انتساب يک مقدار به هر متغير فاقد مقدار، به شرطی که با متغيرهايي که قبلا مقدار گرفتند، متضاد نباشد.
آزمون هدف: انتساب فعلی کامل است؟
هزينه مسير: هزينه ثابت برای هر مرحله برای شطرنج هزینه نداریم
مسائل ارضای محدودیت
مساله ارضای محدودیت را میتوان به فرم مساله جستجوی فضای حالت در نظر گرفت،
که در آن هر حالت فضای جستجو از تخصیص مقادیر به متغیرها به وجود آمده است. جستجو در فضای حالت اصولاً یعنی جستجو بین حالتها جهت رسیدن به یک حالت خاص (مثلا جواب)
اسلاید 14 :
جستجوی پس گرد به جستجوی اول عمقی اطلاق می شود که در آن در هر زمان برای یک متغیر مقادیری در نظر گرفته می شود و هنگامی که هیچ مقدار مجازی برای انتساب به یک متغیر باقی نمانده باشد به عقب بر می گردد.
یک الگوريتم ناآگاهانه است.
برای مسئله های بزرگ کارآمد نيست.
جستجوی عقبگرد برای CSP
جستجوی پس گرد همان اول عمق فصل ۳ است، فقط اسمش اینجا عوض شده است، و الا عین اول عمق عمل میکند
اسلاید 15 :
جستجوی عقبگرد برای CSP
اسلاید 16 :
مثال جستجوی عقبگرد برای CSP
اسلاید 19 :
ساده ترین نوع CSP شامل متغیرهای گسسته با دامنه محدود می باشند (مساله رنگ آمیزی نقشه از این نوع است). مساله 8 وزیر نیز می تواند از این نوع قلمداد شود که در آن متغیرهای Q1, Q2, …, Q8 موقعیت های هر وزیر در ستونهای 1 تا 8 می باشد و هر متغیر دارای دامنه {1،2،3،4،5،6،7،8} است. اگر حداکثر اندازه دامنه هر متغیر در یک CSP برابر با d باشد، آنگاه تعداد انتسابهای کامل ممکن در آن، برابر با O(dn)خواهد بود که یک تابع نمایی نسبت به تعداد متغیرها می باشد.
متغیر
دامنه
وقتی پیچیدگی نمایی باشد برای مسائل بزرگ کارا نیست
مثلا برای ۸ وزیر اگر از روش پس گرد استفاده کنیم جواب میگیرم اما ۱۰۰۰ وزیر چی؟!
اسلاید 20 :
ساده ترین نوع محدودیت، محدودیت های یگانی می باشند که باعث محدود شدن مقدار یک متغیر منفرد می شود. به عنوان مثال، می توان فرض نمود که ناحیه SA به رنگ سبز نباشد. هر محدودیت یگانی را می توان با انجام یک پیش پردازش در دامنه مقادیر متغیرمتناظر و حذف مقادیری که باعث نقض آن محدودیت می شود، تأمین شده انگاشت. یک محدودیت دوگانی، دومتغیر را به هم مربوط می سازد. مثلا SA ≠NSW یک محدودیت دودویی است.
یک CSP دوگانی، CSP ی است که دارای محدودیتهای دودویی باشد.
محدودیت ها با درجات بالاتر شامل سه یا تعداد بیشتری متغیر می باشند.
یک مثال معروف، معمای حساب رمزی می باشد.
قضیهای است که میگوید تمام محدودیتهای بالاتر از درجه ۲ قابل تقلیل به محدودیت با درجه۲ است
