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

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

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

اسلاید 2: 2هوش مصنوعي Artificial Intelligenceفهرستارضای محدوديت چيست؟جست و جوی عقبگرد برای CSPبررسی پيشروپخش محدوديت

اسلاید 3: 3مسائل ارضای محدوديت ارضای محدوديت (CSP) چيست؟مجموعه متناهی از متغيرها؛ X1, X2, …, Xn مجموعه متناهی از محدوديتها؛ C1, C2, …, Cmدامنه های ناتهی برای هر يک از متغيرها؛DX1,DX2,…,DXn هر محدوديت Ci زيرمجموعه ای از متغيرها و ترکيبهای ممکنی از مقادير برای آن زيرمجموعه هاهر حالت با انتساب مقاديری به چند يا تمام متغيرها تعريف ميشودانتسابی که هيچ محدوديتی را نقض نکند، انتساب سازگار نام داردانتساب کامل آن است که هر متغيری در آن باشدحالتی معتبر است که هیچ یک از شرایط را نقض نکند. راه حل CSP يک انتساب کامل ومعتبر استبعضی از CSPها به راه حلهايي نياز دارند که تابع هدف را بيشينه کنند

اسلاید 4: 4مسائل ارضای محدوديت(رنگ آمیزی نقشه)مساله :در نقشه ی مقابل باید هر منطقه را با قرمز،سبز یا آبی به گونه ای رنگ کنیم که مناطق همجوار هم رنگ نباشند. فرموله کردن مساله بصورت CSP:متغيرها: WA, NT, Q, NSW, V, SA, Tدامنه: {آبی، سبز، قرمز} = Diمحدوديتها: دو منطقه مجاور، همرنگ نيستندمثال: WA ≠ NT يعنی (WA,NT) عضو{(قرمز,سبز),(قرمز,آبی),(سبز,قرمز)، (سبز,آبی),(آبی,قرمز),(آبی,سبز)}

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

اسلاید 6: 6مسائل ارضای محدوديت(مثال گراف محدودیت)در گراف محدوديت:گره ها: متغيرهايالها: محدوديتهاگراف برای ساده تر کردن جستجو بکار ميرود

اسلاید 7: 7انواع محدودیت ها در Cspمحدودیت یکانی :ساده ترین نوع محدودیت است که مقدار یک متغیر را محدود می کند. به عنوان مثال در رنگ آمیزی نقشه: استرالیای جنوبی به رنگ سبز نیست.محدودیت دودویی :به دو متغییر مربوط می شود.به عنوان مثال SA≠NSWCSP دودویی:آن است که فقط محدودیت دودویی دارد و می توانند مانند گراف موجود در اسلاید 6 نمایش داده شود.محدودیت های مرتبه ی بالاتر: شامل 3 یا چند متغیر.اگر متغیرهای کمکی کافی معرفی شوند،هر محدودیت مرتبه ی بالاتر و با دامنه ی متناهی می تواند به مجموعه ای از محدودیت ها ی دودویی کاهش یابد.محدودیت اولویت : نشان می دهد کدام راه حل ارجح تر است.

اسلاید 8: 8مسائل ارضای محدوديت(مثال رمزنگاری)متغيرها F,T,U,W,R,O,X1,X2,X3 (X1,X2,X3 متغیرهای کمکی هستند.) دامنه:{9و8و7و6و5و4و3و2و1و0}محدوديتها: F,T,U,R,O,W مخالفند ( یک محدودیت 6 متغیره) - ...O+O=R+10.X1X1+W+W=U+10-X2X2+T+T=O+10-X3X3=F

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

اسلاید 10: 10جست و جوی عقبگرد برای CSPجست و جوی عمقيانتخاب مقادير يک متغير در هر زمان و عقبگرد در صورت عدم وجود مقداری معتبر برای انتساب به متغيريک الگوريتم ناآگاهانه استبرای مسئله های بزرگ کارآمد نيستخاصیت تعویض پذیری: مسئله وقتی تعویض پذیر است که ترتیب به کارگیری هر مجموعه ای از فعالیت ها تاثیری در نتیجه ندارد-ابتدا WA را سبز در نظر بگیریم سپس NT را آبی و برعکس ابتدا Nt را ابی در نظر بگیریم و سپس WA را سبز تفاوتی ندارد.

اسلاید 11: 11جست و جوی عقبگرد برایCSP (مثال)

اسلاید 12: 12جست و جوی عقبگرد برایCSP (مثال-ادامه1)

اسلاید 13: 13جست و جوی عقبگرد برایCSP (مثال-ادامه2)

اسلاید 14: 14جست و جوی عقبگرد برایCSP (مثال-ادامه3)

اسلاید 15: سه تابع اکتشاف برای cspاکتشاف مقادير باقيمانده کمينه(MRV)اکتشاف درجه ایاکتشاف مقداری با کمترین محدودیت15

اسلاید 16: 16اکتشاف مقادير باقيمانده کمينه(MRV)با نام های اکتشاف ”محدودترین متغیر“ یا ”اولین شکست“نیز شناخته می شود.انتخاب متغيری با کمترين مقادير معتبرمتغيری انتخاب ميشود که به احتمال زياد، بزودی با شکست مواجه شده و در نتیجه درخت جست و جو را هرس ميکند

اسلاید 17: 17اکتشاف درجه ایسعی ميکند فاکتور انشعاب را در انتخاب آينده کم کندمتغیری که بیشترین فاکتور انشعاب را دارد در ابتدا انتخاب می شودمتغيری را انتخاب ميکند که در بزرگترين محدوديتهای مربوط به متغيرهای بدون انتساب قرار دارد متغیری که یالهای بیشتری به متغیرهای بدون انتساب دارد

اسلاید 18: 18اکتشاف مقداری با کمترین محدودیتاين روش مقداری را ترجيح ميدهد که در گراف محدوديت، متغيرهای همسايه بندرت آن را انتخاب ميکنندکمترین محدودیت را روی متغیرهای همسایه داردسعی بر ايجاد بيشترين قابليت انعطاف برای انتساب بعدی متغيرها

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

اسلاید 20: 20بررسی پیشرووقتی انتساب به X صورت ميگيرد، فرايند بررسی پيشرو، متغيرهای بدون انتساب مثل Y را در نظر ميگيرد که از طريق يک محدوديت به X متصل است و هر مقداری را که با مقدار انتخاب شده برای X برابر است، از دامنه Y حذف ميکندبا هر سه اکتشاف ذکر شده می توان در نظر گرفت.نمونه: با اکتشاف درجه ای-متغیری که بیشترین فاکتور انشعاب را دارد در ابتدا انتخاب شود

اسلاید 21: 21انتساب رنگ قرمز به WA و در نتیجه حذف رنگ قرمز از دامنه ی نواحی هم جوار با WA یعنی NT و SA .بررسی پیشرو(ادامه1)

اسلاید 22: 22دامنه ی NT وSA شامل یک مقدار است.بررسی پیشرو(ادامه2)

اسلاید 23: 23با انتساب V=blue ،دامنه ی SA خالی می شود لذا بررسی پیشرو در می یابد که انتساب جزئی {WA=red,Q=green,V=blue} بامحدودیتهای مسئله سازگار نیست و الگوریتم فورا برگشت می کند.بررسی پیشرو(ادامه3)

اسلاید 24: 2413243241X1{1,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}بررسی پیشرو(مثال 4 وزیر)

اسلاید 25: 2513243241X1{1,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}بررسی پیشرو(مثال 4 وزیر-ادامه1)

اسلاید 26: 2613243241X1{1,2,3,4}X3{ ,2, ,4}X4{ ,2,3, }X2{ , ,3,4}بررسی پیشرو(مثال 4 وزیر-ادامه2)

اسلاید 27: 2713243241X1{1,2,3,4}X3{ ,2, ,4}X4{ ,2,3, }X2{ , ,3,4}بررسی پیشرو(مثال 4 وزیر-ادامه3)

اسلاید 28: 2813243241X1{1,2,3,4}X3{ , , , }X4{ ,2,3, }X2{ , ,3,4}بررسی پیشرو(مثال 4 وزیر-ادامه4)

اسلاید 29: 2913243241X1{ ,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}بررسی پیشرو(مثال 4 وزیر-ادامه5)

اسلاید 30: 3013243241X1{ ,2,3,4}X3{1, ,3, }X4{1, ,3,4}X2{ , , ,4}بررسی پیشرو(مثال 4 وزیر-ادامه6)

اسلاید 31: 3113243241X1{ ,2,3,4}X3{1, ,3, }X4{1, ,3,4}X2{ , , ,4}بررسی پیشرو(مثال 4 وزیر-ادامه7)

اسلاید 32: 3213243241X1{ ,2,3,4}X3{1, , , }X4{1, ,3, }X2{ , , ,4}بررسی پیشرو(مثال 4 وزیر-ادامه8)

اسلاید 33: 3313243241X1{ ,2,3,4}X3{1, , , }X4{1, ,3, }X2{ , , ,4}بررسی پیشرو(مثال 4 وزیر-ادامه9)

اسلاید 34: 3413243241X1{ ,2,3,4}X3{1, , , }X4{ , ,3, }X2{ , , ,4}بررسی پیشرو(مثال 4 وزیر-ادامه10)

اسلاید 35: 3513243241X1{ ,2,3,4}X3{1, , , }X4{ , ,3, }X2{ , , ,4}بررسی پیشرو(مثال 4 وزیر-ادامه11)

اسلاید 36: 36پخش محدودیتواژه ی کلی برای پخش الزام محدوديتهای يک متغير به متغيرهای ديگراست.مثال: پخش محدوديتهای WA و Q به NT و SA . وقتی WA قرمز و Q سبز است، NT وSA می خواهند آبی باشند،در حالی که همجوار هستند و نمی توانند یک رنگ باشند.

اسلاید 37: 37سازگاری یالاگر وقتی که برای پخش محدودیت ها صرف می کنیم بیشتر از جستجوی ساده باشد از میزان جستجو چندان کم نخواهد شد.روش سريعی برای پخش محدودارائه می کند که قويتر از بررسی پيشرواست. منظور ازيال؛ يال جهت دار در گراف محدوديتبررسی سازگاری يال به صورتهای زیر قابل اجراست:يک مرحله پيش پردازش، قبل از شروع جستجويک مرحله پخشی پس از هر انتساب در حين جستجو

اسلاید 38: 38مسائل ارضای محدوديت(مثال سازگاری یال)یال از SA به NSW ، وقتی سازگار است که برای هر مقدار X از SA ، مقداری مثل y برای NSW وجود دارد که با X سازگار است. SA  NSW سازگار است اگر SA=blue and NSW=red

اسلاید 39: 39بررسی سازگاری یال از NSW به SA : سازگار استNSW=red,SA=blue عدم سازگازی NSW=blue,SA=??? يال ميتواند سازگار شود با حذف blue از NSWمسائل ارضای محدوديت(مثال سازگاری یال-ادامه1)

اسلاید 40: 40 يال ميتواند سازگار شود با حذف blue از NSW حذف red از Vمسائل ارضای محدوديت(مثال سازگاری یال-ادامه2)

اسلاید 41: 41 يال ميتواند سازگار شود با حذف blue از NSW حذف red از Vمسائل ارضای محدوديت(مثال سازگاری یال-ادامه3)

اسلاید 42: 42سازگاری یالفرآیند حذف ناسازگاری ها باید مکررا انجام شود تا هیچ ناسازگاری باقی نماند.هر وقت مقداری از دامنه ی متغییری حذف شود تا ناسازگاری یال بر طرف گردد، ممکن است در یالی که به آن متغییر اشاره می کند ناسازگاری جدیدی ایجاد شود.الگوریتم کامل ناسازگاری یال (AC-3)یال هایی را که باید ناسازگاری آن ها بررسی شوند در یک صف قرار می دهد.اگر مقادیری از دامنه ی Xi حذف شود آنگاه هر یال که به Xi اشاره می کند دوباره به صف مذکور اضافه می شود تا سازگاری اش بررسی گردد. پیچیدگی زمانی در بدترین وضعیت O(n^2d^3) است. اثبات :Csp دودویی حداکثر(O(n^2یال دارد و هر یال فقط dبار می تواند در صف قرار گیرد و بررسی سازگاری یال می تواند در زمان( O(d^2صورت گیرد.

اسلاید 43: 43الگوریتم بررسی سازگاری کمان AC-3Function Ac-3 (csp) returns the csp,possibly with reduct domains Input : csp,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 (xi,xj) 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

اسلاید 44: 44سازگاری Kسازگاری يال تمام ناسازگاريهای ممکن را مشخص نميکندبا روش سازگاریK، شکلهای قويتری از پخش را ميتوان تعريف کرددر صورتی CSP سازگاریK است، که برای هر k-1 متغير و برای هر انتساب سازگار با آن متغيرها، يک مقدار سازگار، هميشه بتواند به متغير kام نسبت داده شود

اسلاید 45: 45بطور مثال:سازگاری1: هر متغير با خودش سازگار است(سازگاری گره)سازگاری2: مشابه سازگاری يال سازگاریk: بسط هر جفت از متغيرهای همجوار به سومين متغير همسايه(سازگاری مسير) گراف در صورتی قويا سازگارK است که:سازگارk باشدهمچنين سازگارk-1 و سازگارk-2 و... سازگار 1 باشددر اين صورت، مسئله را بدون عقبگرد ميتوان حل کردپيچيدگی زمانی آن O(nd) استسازگاری K (ادامه)

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

اسلاید 47: 47مسائل ارضای محدوديت(مثال 8 وزیر)راه حل دو مرحله ای برای مسئله 8وزير با استفاده از کمترين برخورددر هر مرحله، يک وزير برای انتساب مجدد در ستون خودش انتخاب ميگرددتعداد برخوردها در هر مربع نشان داده شده استالگوريتم وزير را به مربعي با کمترين برخورد انتقال ميدهد، بطوريکه گره ها را بطور تصادفی ميشکند