پاورپوینت هوش مصنوعی فصل ششم مسائل ارضای محدودیت

بخشی از پاورپوینت

اسلاید 1 :

هوش مصنوعي
فصل ششم
مسائل ارضای محدوديت

اسلاید 2 :

فهرست
ارضای محدوديت چيست؟
جست و جوی عقبگرد برای CSP
بررسی پيشرو
پخش محدوديت

اسلاید 3 :

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

در مسایل جستجوی استاندارد: هر حالت به عنوان یک جعبه سیاه در نظر گرفته میشود.
در مسایل ارضای محدودیت: هر حالت مجموعه ای از متغیرها (Xi) و مقادیر منتسب به آنهاست.
یک مساله ارضای محدوديت (CSP) شامل:
مجموعه متناهی از متغيرها؛ X1, X2, …, Xn
دامنه های ناتهی برای هر يک از متغيرها؛D1,D2,…,Dn
مجموعه متناهی از محدوديتها؛ C1, C2, …, Cm

هر محدوديت Ci شامل زيرمجموعه ای از متغيرهاست و ترکيبهای ممکنی از مقادير برای آن متغیرها را میسازد.
یک محدودیت به صورت بیان میشود که
scope متغیرهایی است که در محدودیت شرکت دارند.
و relation رابطه ای است که بین مقادیر آنها باید برقرار باشد.
راه حل یک مساله CSP يک انتساب کامل به تمام متغیرها است که تمام محدوديتها را برآورده کند (انتساب کامل و سازگار).
بعضی از CSPها به راه حلهايي نياز دارند که تابع هدف را هم بيشينه کنند.

اسلاید 4 :

مثال: رنگ آميزی نقشه
متغيرها: ایالات استرالیا:WA, NT, Q, NSW, V, SA, T
دامنه: {آبی، سبز، قرمز} = Di
محدوديتها: دو منطقه مجاور، همرنگ نيستند.

WA ≠ NT در واقع خلاصه ای برای محدودیت <,WA≠NT> است که به این معنی است که (WA,NT) باید عضو مجموعه زیر باشد:
{(قرمز,سبز),(قرمز,آبی),(سبز,قرمز)،(سبز,آبی),(آبی,قرمز),(آبی,سبز)}

اسلاید 5 :

مثال: رنگ آميزی نقشه
راه حل مساله انتساب مقاديری است که محدوديتها را ارضا کند

اسلاید 6 :

مسایل ارضای محدودیت
گراف محدوديت: برای نمایش محدودیتها به کار میرود.
گره ها متغيرها و يالها محدوديتها را مشخص میکنند.
گراف برای ساده تر کردن جست و جو بکار ميرود.
مسایل ارضای محدودیت دودویی: متغیرهای حالت فقط دو مقدار میپذیرند.

اسلاید 7 :

مثال: زمانبندی وظایف
به عنوان مثال: مونتاژ یک خودرو با 15 مرحله
متغیرها:

دامنه: اعداد صحیح که نشاندهنده زمان شروع یک وظیفه اند.

محدودیتها:

اسلاید 8 :

تعاریف
مسایل متغیرگسسته
با دامنه محدود: با دامنه به اندازه d، dn انتساب ممکن برای متغیرها داریم.
مثال: Boolean Satisfiability
با دامنه نامحدود:
مثال: زمانبندی وظایف: متغیرها روز شروع و پایان هر وظیفه هستند.
نیاز به یک زبان محدودیت دارند مثلاً StartJob1+5<=StartJob3
برای محدودیتهای خطی راه حلهای تصمیم پذیری وجود دارد اما در حالت غیرخطی الگوریتمی وجود ندارد.
مسایل متغیرپیوسته
مثال: زمانبندی دقیق یک فضاپیما (روز، ساعت، دقیقه ..)
محدودیتهای خطی در زمان چندجمله ای با روشهای برنامه ریزی خطی قابل حل اند.
محدودیتهای یکانی (SA≠green)، محدودیتهای دوتایی (SA≠WA) و محدودیتهای سراسری
محدودیتهای مطلق و محدودیتهای ترجیحی (مسایل بهینه سازی محدودیت)

اسلاید 9 :

مثال: معمای اعداد رمزی
متغيرها: F,T,U,W,R,O,X1,X2,X3
دامنۀ: {9و8و7و6و5و4و3و2و1و0}
محدوديتها: Alldiff (F, T, U, W, R, O)

هایپرگراف محدودیت
هر محدودیت چندتایی را میتوان به تعدادی محدودیت دوتایی تبدیل کرد.

اسلاید 10 :

فرمولبندی CSP
فرمولبندی افزایشی:
حالت اوليه: انتساب خالی{} که در آن، هيچ متغيری مقدار ندارد
تابع جانشين: انتساب يک مقدار به هر متغير فاقد مقدار، به شرطی که با متغيرهايي که قبلا مقدار گرفتند، متضاد نباشند
آزمون هدف: انتساب فعلی کامل باشد.
هزينه مسير: هزينه ثابت برای هر مرحله
میتوان از یک فرمولبندی حالت کامل هم استفاده کرد.
همیشه راه حل برای n متغیر در عمق n به دست می آید پس میتوان از جستجوی عمق اول استفاده کرد.
n!dn برگ داریم.

اسلاید 11 :

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

اسلاید 12 :

الگوریتم AC-3 برای اعمال سازگاری یال
پیچیدگی الگوریتم در بدترین حالت O(cd3) است (d حداکثر اندازه دامنه ها و c تعداد محدودیتهای دوتایی)

اسلاید 13 :

انتشار محدودیت
سازگاری مسیر: متغیرهای {Xi,Xj}با توجه به متغیر Xm سازگاری مسیر دارند اگر به ازای هر انتساب سازگار با محدویتهای روی {Xi,Xj} مقداری برای Xm وجود داشته باشد که با محدودیتهای روی {Xi,Xm} و {Xj,Xm} سازگار باشد. (سازگاری بین سه متغیر)
سازگاری مرتبۀ k: به همان ترتیب بالا بین k متغیر
هر مساله با n متغیر را میتوان با اعمال سازگاری از مرتبۀ 1 تا n حل کرد.
اما اعمال سازگاری در هر مرحله در بدترین حالت نمایی است.
محدودیتهای سراسری: برای انواع خاصی از محدودیتهای سراسری الگوریتمهای کارآیی وجود دارد که میتواند بهتر از الگوریتمهای محدودیتهای عام بالا اعمال شود.
برای مثال اگر در محدودیت Alldiff، m متغیر داشته باشیم و مجموعاً n مقدار برای همه متغیرها داشته باشیم قطعاً محدودیت نمیتواند برقرار شود.

اسلاید 14 :

مثال: سودوکو
یک مساله CSP با 81 متغیر، 27 محدودیت Alldiff
سودوکوهای ساده میتوانند با اعمال الگوریتم AC-3 حل شوند.

سودوکوهای سخت تر میتوانند با الگوریتم PC-2 (برای اعمال سازگاری مسیر) حل شوند.
سختترین سودوکوها برای حل نیاز به جستجو هم دارند.

اسلاید 15 :

جستجوی عقبگرد در CSP
برای اجرای یک الگوریتم عمقی استاندارد بر روی مسایل CSP در سطوح بالا ضریب انشعاب nd است که خیلی زیاد است.
اما انتساب مقادیر به متغیرهای حالت معمولاً جابجایی پذیر است. یعنی ترتیب انتساب متغیرها مهم نیست.
در جستجوی عقبگرد در هر زمان فقط برای يک متغير انتساب صورت میپذیرد و در صورت عدم وجود مقداری معتبر برای انتساب بازگشت به عقب صورت میپذیرد.
يک الگوريتم ناآگاهانه است و برای مسئله های بزرگ کارآمد نيست

اسلاید 16 :

جستجوی عقبگرد در CSP

اسلاید 17 :

مثال جست و جوی عقبگرد در رنگ آمیزی نقشه