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

صفحه 1:
#__ هوش مصنوعی فصل پنجم مسائل ارضای محدودیت 

صفحه 2:
0 5 Artificial Intelligence _s6 94420 _w ‏هو‎ فهرست. #ارضای محدودیت چیست؟ #جست و جوی عقبگرد برای 060 بررسی پیشرو پخش محدودیت 

صفحه 3:
‎plus‏ ارضای محدودیت ‏ارضای محدودیت (2090) چیست؟ ‎ ‎~< ‎ ‏أحامته جاى ناتهى برافق هر يك إز تير ‎sna‏ ع هر محدوديت 01) زيرمجموعه اى از متغيرها و تركيبهاى ممكنى از مقادير براى ‎OT‏ ‏زیرمجموعه ها ‏»هر حالت با انقساب مقادیری به چند یا تمام متفیرها تعریف میشود #انتسابى كه هیچ محدودیتی را نقض نکنده انتساب سا کار نام دارد ‎OL?‏ كاقل آن است که هر متفیری در آن باشد 4 حالتی معتبر است که هیچ یکک از شرایط را نقض نکند. ‏# راه حل 00802 يك انتساب كامل ومعتبر است و اذى الاق قاری اس رات افد اس كن لي بعد ان لسر 

صفحه 4:
‎flue‏ ارضای محدودیت(رنگ آمیزی نقشه) ‎Mlle a gl [de og a2 49) Le‏ را با قرمز‌سبز یا آبی گونه ای رنگ کنیم كه مناطق همجوار هم رنگ نباشند, ‏فرموله کردن مساله بصورت 0090۳ ‎ ‎ ‎O86, OT, QA, OG, O, GB, T | ‎ ‎Gueensand ns 60,- ‏قرفز)‎ jer gl} cacao ‏محدودیتها: دو منطقه مجاور» همرنگ نیستند مثال: 007 # 4000 بعنی ‎WOOP)‏ عضو ‎255000 ۲ 5-7 a} Gena dra athe) pain Dain dS ‘ ‎ 

صفحه 5:
‎Pa‏ مسائل ارضای محدودیت(رنگ آمیزی نقشه-ادامه) ‎ ‏و ‏راه حل انتساب مقادیری است که محدودیتها را ارضا کند 

صفحه 6:
1 مسائل ارضای محدودیت(مثال گراف محدودیت) ری مه 2 @ ‎ee‏ لله" * یالها: محدودیتها كرو روات سدور كرون 59 © سبجو بکار وج )>( © و 

صفحه 7:
انوا محدوديت ها در 0057© #محدودیت يكانى :ساده ترين نوع محدوديت است كه مقدار يكك متغير را محدود مى كند. * به عنوان مثال در رنگ آمیزی نقشه: استرالیای جنوبی به رنگ سبز نیست.. #محدودیت دودویی ذبه دو متغیبر مربوط می شود.به عنوان مثال 909700900) ۵۶ ) دودوییآنلسکه فقط محلودیت‌ودوبیدارد و می‌تسولنند مانند گرلفموجود در لساد۶ نهایشادد شبود. محدودیت های مرتبه ی بالاتر: شامل ۳یا چند متغیر #اكر متغيرهاى کمکی کافی معرفی شوندههر محدودیت مرتبه ی بلاتر و با دمنه ی متاهی می تواندبه مجموعه ای از محدودیت ها ی دودویی کاهش یابد. محدودیت اولویت : نشان می دهد کدام راه حل ارجح تر است. ۷ 

صفحه 8:
مسائل ارضای محدودیت(مثال رمزنگاری) TWO +TWO FOUR 01009000!) ‏كمكى مسف‎ cola te XV XIAN) P,/T,O,0,R,0,.X0X0, 6 ‏متفرها‎ ‎” .) ‏كوو /اوعوشوع ولو اواو‎ XO+TD+T=OHO-XO - ‏محدوديتها: 02,10,0,8,0,00 مخالفند ( يكك محدودیت ۶ متغیره)‎ 62 3 

صفحه 9:
۹ مسائل ۱ ی محدودیت #نمايش حالتها در 2696) از الگوی استانداردی پیروی میکند #برای 296) میتوان فرمول بندی افزایشی ارائه کرد: >حالت اوليه: انتساب خالى [) كه در آن» هیچ متغیری مقدار ندارد تابع جانشين: انتساب يكك مقدار به هر متغير فاقد مقداره به شرطى كه با متغيرهايى كه قبلا مقدار كرفتند» متضاد نباشند >آزمون هدف: انتساب فعلی کامل و معتبراست گ هزینه مسیر: هزینه ثابت برای هر مرحله 

صفحه 10:
جست و جوى عقبكرد براى 0656 انيت :ل عر عفقق تخاب مقادیر یکت متفیر در هر زغان و عقبگرد در صورت عدم وجود مقداری معتبر برای انتساب به متغیر یک لگوریتم نآ گاهنه است > براق مسئلة هاى بزركك کارآمد نیست ape col, ar aye, pap ca? ‏به کار گیری هر مجموعه ای از فعالیت ها تاثیری در نتیجه ندارد-بتدا‎ ‏را سبز در نظر بگيريم سپس 2۳زا آبی و برعکس ابتدا را‎ 8 ۰ ابی در نظر بگیریم و سپس 069) را سبز تفاوتی ندارد. 

صفحه 11:
جست و جوی عقبگرد برای ‎(Sho) CGP‏ HD 

صفحه 12:
جست و جوی عقبگرد برای 0068 (مثال-ادامه ۱) _ Fe 4745 65 

صفحه 13:
جست و جوی عقبگرد برای 0068 (مثال-ادامه ۲) _ Fe 65 45 €S aa و45 بكو 

صفحه 14:
جست و جوی عقبگرد برای 0068 (مثال-ادامه۳) وه ييسج تسیز 6 © جو 

صفحه 15:
* سه تابع اکتشاف برای 65 ۴ اکتشاف مقادیر باقیمانده کمینه(/7۳07) ۴ اکتشاف درجه ای ؟ اکتشاف مقداری با کمترین محدودیت 

صفحه 16:
1 اکتشاف مقادیر باقیمانده کمینه(0680)) تیا ناع ها اکتا *محودتزین یر یا #ولین عکت یو صاعدهبی هرد. ‎joni BS ge‏ #نتفیری اتغاب میشوه که به احتمال زیا بزودی با فکشست موالبه خله و در تیجه درخت جست و جو را هرس میکند 

صفحه 17:
اکتشاف درجه ای طاشعی میکنلافا کتور انشعاب را ذر القخاب آینلاه کم کن ِ متغیری که بیشترین فا کتور انشعاب را دارد در ابتدا انتخاب می شود 4 متفیری را انتخاب میکند که در بزرگترین محدودیتهای مربوط به متفیرهای بدون انتساب قرار دار ا د ‎vein cell‏ مسق اهر دوخ اسان وان 

صفحه 18:
5 اکتشاف مقداری با کمترین محدودیت 7+ o|A aA 2 5 2160 0 این روش مقداری را ترجیح ميدهد كه در كراف محدوديت,. متغيرهاى همسايه بندرت ‎OT‏ را انتخاب میکنند کنتر ین محقودیتا را روی ستقیر ما متا یه داز #اسعى بر ايجاد بيشترين قابليت انعطاف براى انتساب بعدی متفیرها 

صفحه 19:
* انتشار اطلاعات به کمک محدودیت ها * بررسی پیشرو * پخش محدودیت سازگاری یال پخش محدودیت سازگاری 16 

صفحه 20:
بررسی پیشرو وقتی انتساب به ۱ صورت ده فرایند بررسی پیشرو متغیرهای بدون انتساب مثل ۲ را در نظر میگیرد که از طریق یک محدودیت به 2 متصل است و هر مقداری را که با مقدار انتخاب شده پرای کا برابر است. از دامنه ۲۲ حذف میکند با هر سه اکتشاف ذکر شده می توان در نظر گرفت. #نمونه: با اکتشاف درجه ای-متغیری که بيشترين فاكتور انشعاب را دارد در ابتدا ae WA NT a Nsw ۷ SA T 1 ee en) 9 11 1 | 8 11 9 | ۳ انتخاب شود 

صفحه 21:
و بررسی پیشرولادمه 4۱ انتساب رنگک قرمز به 060 و در نتبجه حذف رنگ قرمز از دامنه ی نواحی هم جوار با ‎OP‏ نی ‎GO OP‏ 

صفحه 22:
Ly ‏بررسی پیشرولادام‎ gle ee WA NT Q NSW ۷ SA T ت#دامنه ی ‎GOON‏ شامل یک مقدار است. 

صفحه 23:
‎Ll be‏ اب ۲<() .دامنه ی 96) خالی می شود لذا بررسی پیشرو در می یابد که ‎govt!‏ إصاط- (),موصي> 39 ,لمت 101009 بامحدوديتهاى مسئله سازكار نيست و الگوریتم فورابرگشت می کند ‎ ‎ ‎ ‎ 

صفحه 24:
بررسی پیشرو(مثال ۴ وزیر) x1 2 {1,2,3,4} {1,2,3,4} 1 2 3 4 23 24 {1,2,3,4} {1,2,3,4} BWN eH 

صفحه 25:
)۱ ‏وزیر-ادامه‎ ۴ Jeera eon gle X1 X2 {1,2,3,4} {1,2,3,4} 23 4 {1,2,3,4} {1,2,3,4} 

صفحه 26:
بررسی پیشرو(مثال ۴ وزیر-ادامه ۲) X1 X2 {1,2,3,4} ) , 3,4} 23 4 4,2, ,4( 12,3, ( 

صفحه 27:
بررسی پیشرو(منال ۴ وزیر-ادامه۲) 1 X2 {1,2,3,4} 4 , 3,4} 283 4 { ,2, ,4( 4 ,2,3, } 

صفحه 28:
بررسی پیشرو(منال ۴ وزیر-ادامه۴) 1 X2 {1,2,3,4} 4 , 3,4} 

صفحه 29:
‎gle‏ بررسی پیشیوامتال ۴ وزیر-ادامه۵) ‎2 ‎{1,2,3,4} ‎ ‎x4 ‎{1,2,3,4} ‎ ‎ ‎ ‎ ‎ ‎X1 ‎{ ,2,3,4} ‎3 ‎{1,2,3,4} ‎ ‎ ‎123 4 ‏بر يم نا حي ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 30:
بررسی پیشرو(منال ۴ وزیر-ادامه۶) X2 A} x4 3,4} + {1, X1 { ,2,3,4} X3 141, ,3, 123 4 بر يم نا حي 

صفحه 31:
)۷ ‏بررسی پیشیوامتال 7 وزیر-ادامه‎ gle X1 X2 { ,2,3,4} {,. 4} 23 4 {1, ,3, } {1, ,3,4} 

صفحه 32:
‎gle‏ بررسی پیشیوامتال 7 وزیر-ادامه۸) ‎X1 X2 { ,2,3,4} {,. 4} ‎ ‎ ‎ ‎ ‎ ‎23 4 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 33:
بررسی پیشرو(منال ۴ وزیر-ادامه٩)‏ 1 X2 { ,2,3,4} {,, A} X3 4 

صفحه 34:
۰ ‏پیشیو(مال ۴ وزیر-دامه‎ eet glee X1 X2 { ,2,3,4} {,. 4} 23 4 

صفحه 35:
و بررسی پیشیو(مال ۴ وزیر-دامه ۱ X1 X2 { ,2,3,4} {,. 4} 23 4 

صفحه 36:
a پخش محدودیت .واژه ی کلی برای پخش الزام محدودیتهای یک متغیر به متغیرهای دیگراست گمنال: پخش محدودیتهای 069 و 3 به 07و 09). وقتی 060 قرمز و ‎Q‏ سبز است» 0۳و00 می خواهند آپی باشند.در حالی که همجوار هستند و نمی توانند یک رنگ باشند. جل يعاق نا Nsw v SA 1 1 11 11 ۱۲1 ۲۱ 

صفحه 37:
#اگر وقتی که برای پخش محدودیت ها صرف می كمع بیشتر از جستجوی ساده باشد از میزان جستجو چندان کم نخواهد شد. yaw Ost pays ap ‏#أاووس‎ ‎acl gia تور اب10 یال هنت فار فراگزات مود یت #بررسي سازكارى یال به صورتهای زیر قابل اجراست: بك مرحله بيش بردازش»ء قبل از شروع جستجو > يكك مرحله بخشى بس از هر انتساب در حين جستجو 3 

صفحه 38:
مسائل ارضای محدودیت(مثال سا ز گاری یال) WA NT Q Nsw v SA T ۷ ‏سازگار است که برای هر مقدار لا از 969 : مقداری مثل‎ 3) DEO 4GO 3 LO ‏برای 126960) وجود دارد که با لساز گار است.‎ ‏سا زگار است اگر‎ )69 -« 0 * ‏رت‎ vk 

صفحه 39:
مسائل ارضای محدودیت(مثال سا زگاری یال-ادامه۱) #بررسی سا زگاری یال از 606900 به 909): ازگار است ‎JOD‏ " يال ميتواند سا زگار شود با حذف داز 0090 42 

صفحه 40:
5۹ مسائل ارضای محدودیت(مثال سا زگاری بال-ادامه ۲) WA NT a NSW v SA T " يال ميتواند سازكار شود با حذف صاطاز 000800 ۴ حذف اهاز 6 

صفحه 41:
5۹ مسائل ارضای محدودیت(مثال سا زگاری بال-ادامه۳) " يال ميتواند سازكار شود با حذف صاطاز 000800 * حذف از 6 5 

صفحه 42:
4 فرآیند حذف ناساز گاری ها باید مکررا انجام شود تا هیچ ناساز گاری باقی نماند. # هر وقت مقداری از دامنه ی متفیبری حذف شود تا ناساز گاری یال بر طرف گرده: ممکن است در یالی که به ‎OT‏ متغیبر اشاره می کند ناسا ز گاری جدیدی ایجاد شود. #الكوريتم كامل ناسازكارى يال (©-863)يال هابى را که باید ناسا زگاری آن ها بررسی شوند در يكك صف زازع سعفد #اگر مقادیری از دامته ‎de Mt‏ شود آنگاه هر یال که به 261 اشارة می کند دوبازه به صعت مذ کور اضافهامی شود تا سا زگاری اش بررسی گردد. % پیچیدگی زمانی در بدترین وضعیت (0)۸640 است. اثبات :۳() دودویی حدا کثر( (۸6)()یال دارد و هر یال فقط ابار می تواند در صف قرار كيرد و بررسی سا زگاری یال می تواند در زمان( 0406)()صورت گیرد. ‎ra‏ 

صفحه 43:
Function Ac-3 (csp) returns the csp,possibly with reduct domains Input : esp,a binary csp with variabels{x1,x2,....xn} local variabels:queue,a queue of arcs, initially all the arcs in csp While queue is not empty do (xixj) _ REMOVE-FIRST(queue) If REMOVE-INCONSISTENT-VALUES(xi,xj) then for each xk in neighbors[xi] do add xk,xi to queue Function REMOVE-INCONSISTENT-VALUES(xi,xj)returns true if we remove a value removed false For each x in domain{xi} do if novalue y in domain {xj} allows (x,y) to satisfi the constraint between xi and xj +— then delete x from domain {xi};removed true Return removed 39 

صفحه 44:
ساز کاری 6 #سازكارى یال تمام ناسا زگاریهای ممکن را مشخص نمیکند 9 سازگاری 1: شکلهای قویتری از پخش را مبتوان تعریف کرد #در صورتی 2086۳) سا زگاری1) است» که برای هر 4امتفیر و برای هر انتساب سا زگار با آن متغیرهاء يكك مقدار سا زكار» هميشه بتواند به متغير كام نسبت داده شود 

صفحه 45:
سا ز کاری ) (ادامه) #بطور مثال: > سازكارى 1: هر متغير با ودش سا زكار اس ت(سازكارى گره) سا زگاری ۲: مشابه سا ز گاری یال ‎hy EGS‏ بسط هر جفت. از متغیرهای همجوار به سومین متفیر همسایه(ساز گاری مسیر) کفرافت کز تور تون هرا تا زگگا )نع گنه ‏> سا زگارت] باشد ‏> همچنین سا زگار | و سا زگار ۳6 و... ساز گار ۱ باشد ‎Pier See alld een, scl Se‏ کرد ‏» ييجيدكى زمانى آن (21) © است ‎© 

صفحه 46:
جستجوی محلی در مسائل ارضای محدودیت #الكوريتم های جستجوی محلی بسیاری از 269)ها را بطور کارآمد حل مى كنئد > حالت اوليه. مقداری را به هر متغیر نسبتمیدهد *تابع جانشین؛ تغیبر مقدار یک متفیر در هر زمان انتخاب مقدار جدید برای یک متغیر انتخاب مقداری که کمترین برخورد را با متغیرهای دیگر ایجاد کند(اکتشاف برخورد کم) * زمان اجرای برخورد کم مستقل از اندازه مسئله است برخورد کم برای مسئله های سخت نیز کار میکند ‎ngs ee cu‏ ساسحا انجام دهد 2 

صفحه 47:
‎plus‏ ارضای محدودیت(مثال ۸وزیر) ‏راه حل دو مرحله ای برای مسئله ۸وزیر با استفاده از کمترین برخورد ‎ ‎ ‎ ‎ ‏*در هر مرحله یک وزیر برای انتساب ممجدد در ستون حودش انتخاب میگردد. "تعداد برخوردها در هر مربع نشان داده شده است ‏*الگوریتم وزیر را به مربعی با کمترین برخورد انقال میدهده بطوریکه گره ها را بطور تصادفی میشکند 8 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎